What is the time complexity of Find the Duplicate Number?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Find the Duplicate Number?

This problem uses Array, Two Pointers, Binary Search, Bit Manipulation. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Find the Duplicate Number?

Insight 1: The problem can be modeled as a linked list cycle detection problem. Insight 2: Each number in the array can be seen as a pointer to another number in the array (index). The presence of a duplicate creates a cycle.

Which companies ask LeetCode 287. Find the Duplicate Number in interviews?

This problem is frequently asked at Anduril, Citadel, Goldman Sachs, Google, IBM and 5 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find the Duplicate Number - LeetCode 287 Solution

Q: How to solve Find the Duplicate Number?

The provided solution uses Floyd's cycle-finding algorithm, also known as the tortoise and hare algorithm, to find the duplicate number. The array `nums` is treated as a linked list where `nums[i]` represents the next node from node `i`. Because there is a duplicate number, there will be a cycle in the linked list. The algorithm works in two phases: (1) find the meeting point of the slow and fast pointers, and (2) find the entry point of the cycle.

Find the Duplicate Number - Complete Solution Guide

Find the Duplicate Number is LeetCode problem 287, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums , return this repeated number . You must solve the problem without modifying the array nums and using only constant extra space. Example 1: Input: nums = [1,3,4,2,2] Output: 2 Example 2: Input: nums = [3,1,3,4,2] Output: 3 Example 3: Input: nums = [3,3,3,3,3] Output: 3 Constraints: 1 <= n <= 10 5 nums.length == n + 1 1 <= nums[i] <= n All the in

Detailed Explanation

The problem requires finding a duplicate number within an array `nums` of size `n + 1`, where each number is within the range `[1, n]`. There is exactly one repeated number, and the goal is to identify this repeated number without modifying the original array and using only constant extra space.

Solution Approach

The provided solution uses Floyd's cycle-finding algorithm, also known as the tortoise and hare algorithm, to find the duplicate number. The array `nums` is treated as a linked list where `nums[i]` represents the next node from node `i`. Because there is a duplicate number, there will be a cycle in the linked list. The algorithm works in two phases: (1) find the meeting point of the slow and fast pointers, and (2) find the entry point of the cycle.

Step-by-Step Algorithm

Step 1: Initialize two pointers, `slow` and `fast`, to the starting index 0.
Step 2: Move `slow` one step at a time (`slow = nums[slow]`) and `fast` two steps at a time (`fast = nums[nums[fast]]`).
Step 3: Continue moving the pointers until `slow` and `fast` meet. This guarantees they are in the cycle.
Step 4: Reset `finder` pointer to the starting index 0.
Step 5: Move both `finder` and `slow` one step at a time until they meet. The meeting point is the entry point of the cycle, which is the duplicate number.
Step 6: Return the value of `finder` (or `slow`), which is the duplicate number.

Key Insights

Insight 1: The problem can be modeled as a linked list cycle detection problem.
Insight 2: Each number in the array can be seen as a pointer to another number in the array (index). The presence of a duplicate creates a cycle.
Insight 3: Floyd's cycle-finding algorithm (tortoise and hare) is a suitable approach to detect and locate the cycle start, which corresponds to the duplicate number.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Binary Search, Bit Manipulation.

Companies

Asked at: Anduril, Citadel, Goldman Sachs, Google, IBM, Infosys, J.P. Morgan, Niantic, Nvidia, Zoho.

Find the Duplicate Number | LeetCode 287

Medium

Array Two Pointers Binary Search Bit Manipulation

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }
        
        int finder = 0;
        while (finder != slow) {
            finder = nums[finder];
            slow = nums[slow];
        }
        
        return finder;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 287: Find the Duplicate Number - Detailed explanation and solution approaches.

Topics

Array Two Pointers Binary Search Bit Manipulation

Companies

AndurilCitadelGoldman SachsGoogleIBMInfosysJ.P. MorganNiantic

Stats

Difficulty:Medium

Languages:4

Companies:10

Problem #:287

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize two pointers, `slow` and `fast`, to the starting index 0.
2
Step 2: Move `slow` one step at a time (`slow = nums[slow]`) and `fast` two steps at a time (`fast = nums[nums[fast]]`).
3
Step 3: Continue moving the pointers until `slow` and `fast` meet. This guarantees they are in the cycle.
4
Step 4: Reset `finder` pointer to the starting index 0.
5
Step 5: Move both `finder` and `slow` one step at a time until they meet. The meeting point is the entry point of the cycle, which is the duplicate number.
6
Step 6: Return the value of `finder` (or `slow`), which is the duplicate number.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The cycle detection phase takes at most n iterations because each element is visited and the 'fast' pointer cannot skip elements endlessly. The second phase (finding the entry point) also takes at most n iterations. Therefore, the overall time complexity is O(n). The algorithm uses only a constant amount of extra space for the pointers `slow`, `fast`, and `finder`, regardless of the input size. Hence, the space complexity is O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Binary Search

Perform binary search on the range of numbers from 1 to n. For each number 'mid' in the range, count how many numbers in 'nums' are less than or equal to 'mid'. If the count is greater than 'mid', then the duplicate number must be in the range [1, mid]. Otherwise, it must be in the range [mid + 1, n].

Time: O(n log n)Space: O(1)

Trade-offs: Binary search provides a good alternative, still fulfilling O(1) space complexity. However, it is slower than the Floyd's algorithm.

Sorting

Sort the array first. Then, iterate through the sorted array and find the first element that is equal to its neighbor. This element is the duplicate.

Time: O(n log n)Space: O(1) if in-place sorting is used, otherwise O(n)

Trade-offs: Sorting might modify the input array, which is against the problem constraint. Its time complexity is also higher than the Floyd's algorithm, with potential extra space depending on sorting implementation.

✨

Key Insights

1Insight 1: The problem can be modeled as a linked list cycle detection problem.
2Insight 2: Each number in the array can be seen as a pointer to another number in the array (index). The presence of a duplicate creates a cycle.
3Insight 3: Floyd's cycle-finding algorithm (tortoise and hare) is a suitable approach to detect and locate the cycle start, which corresponds to the duplicate number.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: `nums` contains only one element. This case doesn't violate the constraint, so code will still work.
Edge case 2: The duplicate is the first element. The algorithm will correctly identify the start of the cycle at index `0`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Modifying the original array. The problem explicitly states not to modify the input array.

✗Common mistake 2: Using extra space proportional to the input size. The problem restricts the solution to constant extra space.

✗Common mistake 3: Not understanding the cycle detection concept. It's crucial to grasp how the duplicate number creates a cycle in the linked-list representation of the array.

✗Common mistake 4: Assuming that the duplicate always starts from the beginning of the array. The duplicate can be located anywhere.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Memory management - Detecting memory leaks where the same memory address is allocated multiple times.

🏦Real-world scenario 2: Database integrity - Ensuring that a unique constraint is enforced, and identifying violating entries within a large dataset.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 16, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Find the Duplicate Number"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?