Course4all
Join us on telegram
Home/dsa/Two Pointers/Find the Duplicate Number

Find the Duplicate Number

Master this topic with zero to advance depth.

Find the Duplicate Number

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, return this repeated number. You must solve the problem without modifying the array nums and use only constant extra space.

Array: [1, 3, 4, 2, 2] Index: 0 1 2 3 4 Treat values as pointers: 0 -> 1 -> 3 -> 2 -> 4 -> 2... (Cycle!) ^----|
Medium

Examples

Input: nums = [1,3,4,2,2]
Output: 2
Input: nums = [3,1,3,4,2]
Output: 3
Approach 1

Level I: Sorting

Intuition

If we sort the array, the duplicate number will be adjacent to itself. This modifies the input array, which is usually not ideal, but it's a simple first approach.

⏱ O(N log N)💾 O(1) (or O(N) depending on sort implementation)

Detailed Dry Run

Input: [1, 3, 4, 2, 2]

  1. Sorted: [1, 2, 2, 3, 4]
  2. nums[1] == nums[2]? YES. Return 2.
java
public int findDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i-1]) return nums[i];
    }
    return -1;
}

⚠️ Common Pitfalls & Tips

Modifies the input array, which may violate problem constraints.

Approach 2

Level II: HashSet / Visited Array

Intuition

As we iterate through the array, keep track of numbers we've seen. If we see a number again, it's the duplicate.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: [1, 3, 4, 2, 2]

  1. Seen: {1, 3, 4, 2}
  2. Next is 2. 2 is in Seen. Return 2.
java
public int findDuplicate(int[] nums) {
    boolean[] seen = new boolean[nums.length];
    for (int n : nums) {
        if (seen[n]) return n;
        seen[n] = true;
    }
    return -1;
}

⚠️ Common Pitfalls & Tips

Uses O(N) space, violating the constant space constraint.

Approach 3

Level III: Floyd's Cycle Finding (Tortoise and Hare)

Intuition

Since the array contains values in the range [1, n] and has n+1 elements, we can treat the array values as pointers to indices. A duplicate value will cause multiple indices to point to the same next index, creating a cycle. We can use Floyd's algorithm to find the entrance of this cycle, which is our duplicate number.

  1. Find Intersection: Use a slow (1 step) and fast (2 steps) pointer. Move them until they meet in a cycle.
  2. Find Entrance: Reset another pointer to the start of the array. Move both pointers one step at a time. The point where they meet is the start of the cycle (the duplicate number).
⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [1, 3, 4, 2, 2] indices: 0->1->2->3->4 values: 1, 3, 4, 2, 2 Linked List: 0 -> 1 -> 3 -> 2 -> 4 -> 2...

  1. Phase 1: slow at 1, fast at 3. Then slow at 3, fast at 4. Then slow at 2, fast at 2. MEET!
  2. Phase 2: p1=0, p2=2 (meeting point).
  • Loop 1: p1 = nums[0] = 1, p2 = nums[2] = 4
  • Loop 2: p1 = nums[1] = 3, p2 = nums[4] = 2
  • Loop 3: p1 = nums[3] = 2, p2 = nums[2] = 4... Meeting at 2.
java
public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
}

⚠️ Common Pitfalls & Tips

This only works if the array values are in the range [1, n]. If there's a 0, the pointer logic might get stuck at index 0.

← Previous QuestionReverse Words in a String
Next Question →Trapping Rain Water