Find the Duplicate Number

Mediumarraytwo-pointersbinary-search
Category: Linked List
Companies that ask this question:
AmazonMicrosoftFacebookGoogle
LeetCode →NeetCode →

Approach

Find the Duplicate Number

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 uses only constant extra space.

Examples

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

Intuition

Key Constraints:

  • n + 1 numbers in range [1, n]
  • Cannot modify array
  • Must use O(1) space

Brilliant Insight: Treat array as a linked list!

  • Index i → nums[i] (like next pointer)
  • Since values are in [1, n], they're valid indices
  • Duplicate creates a cycle in this "linked list"

Why there's always a cycle:

  • n + 1 numbers, only n possible values
  • Pigeonhole principle: at least one duplicate
  • Duplicate value = multiple nodes pointing to same node = cycle

Pattern Recognition

This is a Floyd's Cycle Detection (Tortoise & Hare) problem:

  • Phase 1: Detect cycle exists
  • Phase 2: Find cycle entrance (the duplicate)

Approach

Floyd's Cycle Detection (Optimal)

def findDuplicate(self, nums):
    # Phase 1: Find intersection point in cycle
    slow = fast = nums[0]

    while True:
        slow = nums[slow]      # Move 1 step
        fast = nums[nums[fast]]  # Move 2 steps
        if slow == fast:
            break

    # Phase 2: Find entrance to cycle (duplicate)
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

Why it works:

  1. Phase 1: Slow and fast meet inside cycle
  2. Phase 2: Distance from start to cycle entrance = distance from meeting point to cycle entrance
  3. Moving both at same speed finds the duplicate

Complexity Analysis

Floyd's Algorithm

  • Time: O(n)
    • Phase 1: O(n) to find meeting point
    • Phase 2: O(n) to find entrance
  • Space: O(1)
    • Only two pointers

Alternative Solutions

  • HashSet: O(n) time, O(n) space ❌ (violates space constraint)
  • Sorting: O(n log n) time, O(1) space ❌ (modifies array)
  • Binary Search: O(n log n) time, O(1) space ✓ (valid but slower)

Visual Example

For nums = [1,3,4,2,2]:

Array as "Linked List":
Index: 0  1  2  3  4
Value: 1  3  4  2  2

Pointers from index to nums[index]:
0 → 1 → 3 → 2 → 4 → 2 (cycle back to 2)

Phase 1: Find meeting point
slow: 0 → 1 → 3 → 2 → 4
fast: 0 → 3 → 4 → 3 → 2 → 2
Meet at index 2 (value 4)

Phase 2: Find entrance
slow: 0 → 1 → 3 → 2
fast: 4 → 2 → 4 → 2
Both reach index 2 → duplicate is 2

Edge Cases

  1. Duplicate at start: [2,1,2] → 2
  2. All same: [3,3,3,3,3] → 3
  3. Large array: Works efficiently for any size

Solution

java
1class Solution {
2    public int findDuplicate(int[] nums) {
3        // Floyd's Cycle Detection (Tortoise and Hare)
4
5        // Phase 1: Find intersection point in the cycle
6        int slow = nums[0];
7        int fast = nums[0];
8
9        do {
10            slow = nums[slow];           // Move 1 step
11            fast = nums[nums[fast]];     // Move 2 steps
12        } while (slow != fast);
13
14        // Phase 2: Find the entrance to the cycle (duplicate number)
15        slow = nums[0];
16        while (slow != fast) {
17            slow = nums[slow];
18            fast = nums[fast];
19        }
20
21        return slow;
22    }
23}
24
25
26// Alternative Solution 1: Binary Search on Answer Range
27class SolutionBinarySearch {
28    public int findDuplicate(int[] nums) {
29        int left = 1;
30        int right = nums.length - 1;
31
32        while (left < right) {
33            int mid = left + (right - left) / 2;
34
35            // Count how many numbers are less than or equal to mid
36            int count = 0;
37            for (int num : nums) {
38                if (num <= mid) {
39                    count++;
40                }
41            }
42
43            if (count > mid) {
44                // Duplicate is in [left, mid]
45                right = mid;
46            } else {
47                // Duplicate is in [mid + 1, right]
48                left = mid + 1;
49            }
50        }
51
52        return left;
53    }
54}
55
56
57// Alternative Solution 2: Marking with Negation (Modifies Array)
58class SolutionMarking {
59    public int findDuplicate(int[] nums) {
60        // Note: This modifies the array, violates constraint
61        for (int num : nums) {
62            int idx = Math.abs(num);
63            if (nums[idx] < 0) {
64                return idx;
65            }
66            nums[idx] = -nums[idx];
67        }
68
69        return -1;
70    }
71}
72
73
74// Alternative Solution 3: HashSet (Uses O(n) Space)
75class SolutionHashSet {
76    public int findDuplicate(int[] nums) {
77        // Note: This uses O(n) space, violates constraint
78        Set<Integer> seen = new HashSet<>();
79
80        for (int num : nums) {
81            if (seen.contains(num)) {
82                return num;
83            }
84            seen.add(num);
85        }
86
87        return -1;
88    }
89}
90
Loading visualizer...