Find the Duplicate Number

You are given an array nums of length n + 1 in which every value is an integer between 1 and n inclusive. By the pigeonhole principle at least one value must repeat; here exactly one value repeats, though it may appear two or more times.

Return that repeated value.

Your solution must not modify nums and must use only O(1) extra memory. (Sorting the array or storing seen values in a set would break these rules.)

Example 1

Example 2

Example 3

Constraints

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• Exactly one value appears more than once; it may appear many times.

Pattern Path · Two Pointers · problem 23 of 169

Start simple

Compare every pair of elements, or count each candidate value with a full scan: O(n²) time and O(1) space.

The key idea

Read the array as a function on indices: from index i you move to index nums[i]. Every value lies in 1..n, so every step lands on a valid index, and the walk starting at index 0 continues forever. With only finitely many indices it must eventually enter a cycle, exactly like a linked list with a loop.

Where does the cycle start? The entry node is the one first reached from two different predecessors: one on the path leading in, one at the end of the loop. Two indices pointing to the same place means two positions holding the same value, i.e. the duplicate. (Index 0 cannot be the entry because no value is 0.)

Floyd's algorithm finds the entrance with two pointers. Phase 1: move slow one step and fast two steps until they meet inside the cycle. Phase 2: restart one pointer at 0 and move both one step at a time; the distance from the start to the entrance equals the distance from the meeting point to the entrance (modulo the cycle length), so they meet exactly at the entrance, which is the answer. The array is only read, and only two indices are stored.

Complexity

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

Python

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Treat i -> nums[i] as a linked list; the duplicate is where its cycle begins.
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # Phase 2: walkers from the start and from the meeting point meet at the cycle entrance.
        finder = 0
        while finder != slow:
            finder = nums[finder]
            slow = nums[slow]
        return finder

JavaScript

var findDuplicate = function(nums) {
  // Treat i -> nums[i] as a linked list; the duplicate is where its cycle begins.
  let slow = 0, fast = 0;
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  // Phase 2: walkers from the start and from the meeting point meet at the cycle entrance.
  let finder = 0;
  while (finder !== slow) {
    finder = nums[finder];
    slow = nums[slow];
  }
  return finder;
};

What the interviewer is checking

The real test is whether you can spot a hidden linked-list cycle in an array under tight constraints; binary search on the value range (counting elements ≤ mid) in O(n log n) is a strong alternative to mention.

Mistakes to avoid

• Sorting or marking values as negative in place, which modifies the input.
• Using a set or count array, which needs O(n) extra space.
• Assuming the duplicate appears exactly twice; sum or XOR tricks fail when it repeats more often.
• Starting Floyd's walk at index 1 or comparing values instead of positions, which can return the wrong node.

Follow-ups to expect

• Can you do it with binary search? (Count values ≤ mid: O(n log n).)
• Prove that a duplicate must exist. (Pigeonhole: n + 1 items, n values.)
• Detect a cycle in a linked list and find where it starts. (Same Floyd phases.)

In real software

Cycle detection with two pointers is used to find loops in pseudo-random number generators (Pollard's rho factoring) and to detect corrupted, looping pointer chains in memory or file-system structures.

Practice next