Find the Duplicate Number

Find the Duplicate Number looks like an array problem. But the famous solution treats the array like a linked list with a loop. That surprise framing is exactly why interviewers love it. So we put it in the linked-list set, because the real trick is cycle detection.

🎯 The Problem

You get an array and must find the one number that repeats. Here are the rules.

• The array holds n + 1 numbers.
• Every number is between 1 and n.
• So with that many numbers in that small a range, at least one number must repeat.
• You cannot change the array.
• You must use only a tiny, fixed amount of extra memory.

Say the array is [1, 3, 4, 2, 2]. Here n is 4, and the numbers run from 1 to 4. The number 2 appears twice. So the answer is 2.

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

Explanation: the value 2 appears more than once

Here is the array drawn as index-to-value jumps. Reading a value tells you the next index to visit.

🐢 Approach 1: Sort Then Scan (Brute Force)

The idea in one line: sort the numbers so the duplicate sits next to its twin.

The idea:

• After sorting, two equal numbers become neighbors.
• Walk once and compare each number to the one before it.
• The first match is the duplicate.

Why it is weak:

• Sorting changes the array. The problem forbids that.
• Sorting a copy uses O(n) extra memory. That breaks the other rule.
• So it is fine as a warm-up answer only.

Here is the sort-then-scan code:

def find_duplicate(nums):
    nums = sorted(nums)
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return nums[i]

🐇 Approach 2: Hash Set (Better)

The idea in one line: remember every number you have seen, then catch the first repeat.

The idea:

• A hash set remembers items and tells you instantly if it has seen one.
• Walk the array. For each number, ask the set if it is already there.
• If yes, that number is the duplicate.

How it works:

• For a new number, add it to the set.
• For a seen number, return it right away.

Why it is weak:

• The set can grow to the size of the array.
• So it uses O(n) extra memory.
• That breaks the tiny-memory rule.

Here is the hash-set code:

def find_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)

⚡ Approach 3: Floyd’s Cycle Detection (Best)

The idea in one line: read the array as a linked list, then find where it loops.

The idea:

• Read each value as a pointer to the next index.
• From index i, jump to index nums[i]. Then jump again.
• Because some value repeats, two indexes point to the same place.
• So the path of jumps must loop. The loop entry is the duplicate.

How it works:

• Phase one uses two pointers. Slow jumps one step. Fast jumps two steps.
• The path loops, so fast meets slow inside the loop.
• Phase two moves one pointer back to the start.
• Then both move one step at a time. They meet at the loop entry.
• That entry value is the duplicate.

Why it is fast:

• It walks the values a constant number of times. So it is O(n).
• It keeps only two pointers. So it is O(1) space.
• It never touches the array. So it obeys both rules.

Here is the two-phase pointer walk that finds the answer.

Steps to Solve

1. Start both slow and fast at index zero.
2. Move slow one jump and fast two jumps, again and again, until they land on the same value.
3. Move one pointer back to the start. Leave the other at the meeting value.
4. Move both pointers one jump at a time until they meet again.
5. That meeting value is the duplicate number. Return it.

#include <stdio.h>

int findDuplicate(int nums[], int n) {
    // phase 1: find a meeting point inside the cycle
    int slow = nums[0];
    int fast = nums[0];
    do {
        slow = nums[slow];          // one jump
        fast = nums[nums[fast]];    // two jumps
    } while (slow != fast);

    // phase 2: find the entry of the cycle
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

int main(void) {
    int nums[] = {1, 3, 4, 2, 2};
    int n = 5;
    printf("%d\n", findDuplicate(nums, n));
    return 0;
}

2

#include <iostream>
#include <vector>
using namespace std;

int findDuplicate(vector<int>& nums) {
    // phase 1: find a meeting point inside the cycle
    int slow = nums[0];
    int fast = nums[0];
    do {
        slow = nums[slow];          // one jump
        fast = nums[nums[fast]];    // two jumps
    } while (slow != fast);

    // phase 2: find the entry of the cycle
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

int main() {
    vector<int> nums = {1, 3, 4, 2, 2};
    cout << findDuplicate(nums) << endl;
    return 0;
}

2

public class FindDuplicate {
    static int findDuplicate(int[] nums) {
        // phase 1: find a meeting point inside the cycle
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];          // one jump
            fast = nums[nums[fast]];    // two jumps
        } while (slow != fast);

        // phase 2: find the entry of the cycle
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 3, 4, 2, 2 };
        System.out.println(findDuplicate(nums));
    }
}

2

def find_duplicate(nums):
    # phase 1: find a meeting point inside the cycle
    slow = nums[0]
    fast = nums[0]
    while True:
        slow = nums[slow]            # one jump
        fast = nums[nums[fast]]      # two jumps
        if slow == fast:
            break

    # phase 2: find the entry of the cycle
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow


nums = [1, 3, 4, 2, 2]
print(find_duplicate(nums))

2

function findDuplicate(nums) {
  // phase 1: find a meeting point inside the cycle
  let slow = nums[0];
  let fast = nums[0];
  do {
    slow = nums[slow];           // one jump
    fast = nums[nums[fast]];     // two jumps
  } while (slow !== fast);

  // phase 2: find the entry of the cycle
  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

const nums = [1, 3, 4, 2, 2];
console.log(findDuplicate(nums));

2

Let us walk through the Python version line by line and see why each part is there.

The lines slow = nums[0] and fast = nums[0] start both pointers at the same place. Index zero is the entry to our pretend linked list. We read values as the addresses to jump to.

The first while True loop is phase one. Inside it, slow = nums[slow] takes one jump. The value at the current spot tells us where to land next. The line fast = nums[nums[fast]] takes two jumps in one move, reading the value, then reading the value at that spot. The fast pointer moves twice as fast as slow. So inside the loop the fast one catches the slow one. When slow == fast, they have met, and we break.

Note this meeting point is somewhere inside the cycle. It is not yet the duplicate. So we need phase two.

The line slow = nums[0] resets the slow pointer back to the start. The fast pointer stays at the meeting spot. The second loop moves both one jump at a time with slow = nums[slow] and fast = nums[fast]. The math of Floyd’s algorithm guarantees they meet exactly at the entry of the cycle. And that entry value is the number two different indexes pointed at, which is the duplicate. So we return slow.

⏱️ Time and Space Complexity

The sorting way is O(n log n) time and changes the array. The hash set way is O(n) time but uses O(n) extra memory. Floyd’s cycle detection walks the values a constant number of times, so it is O(n) time, and it only keeps two pointers, so it is O(1) space. It also never touches the array. So it is the only approach that obeys both rules.

🧩 Key Takeaways

• ✅ With n + 1 numbers in the range 1 to n, at least one number must repeat.
• ✅ Read each value as a jump to the next index, and the path must form a cycle.
• ✅ The entry of that cycle is the duplicate number.
• ✅ Floyd’s tortoise and hare finds the cycle entry using only two pointers.
• ✅ It runs in O(n) time and O(1) space and never changes the array.

🚀 What’s Next?

• Copy List with Random Pointer
• Reorder List