42.Find the Duplicate Number

MediumLinked List · 8/11

Problem

Given an array nums of n + 1 integers where every value is in the range [1, n], there is exactly one repeated number (it may appear two or more times). Return that number.

You must solve it without modifying nums and using only constant extra space.

Examples

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

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

Input:  nums = [3, 3, 3, 3, 3]
Output: 3
Explanation: The duplicate can appear more than twice.

Constraints

1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer, which appears two or more times.

💡 Key Insight

Treat the array as a linked list: index i points to index nums[i]. Every value is a valid index in [1, n], and index 0 is never a target, so starting at 0 you walk into a structure that must loop. Two indices pointing to the same next index means the duplicate value is the entrance of the cycle — exactly what Floyd's cycle detection finds in O(n) time and O(1) space, without touching the array.

Sorting

TimeO(n log n)SpaceO(n)

Intuition

After sorting, equal values sit next to each other, so the duplicate is the first i with nums[i] == nums[i - 1]. This breaks the "do not modify" rule (or costs O(n) to copy), but it is the natural first idea.

Algorithm

Copy and sort nums.
Return the first sorted[i] equal to sorted[i - 1].

Visualization

nums   = [3, 1, 3, 4, 2]
sorted = [1, 2, 3, 3, 4]
                 ^  ^   equal neighbours -> 3

Code

java

import java.util.Arrays;

class Solution {
    public int findDuplicate(int[] nums) {
        int[] sorted = nums.clone(); // avoid modifying the input
        Arrays.sort(sorted);
        for (int i = 1; i < sorted.length; i++) {
            if (sorted[i] == sorted[i - 1]) {
                return sorted[i];
            }
        }
        return -1; // unreachable for valid input
    }
}

Complexity

Time: O(n log n) — sorting.
Space: O(n) — the copy (O(log n) if you sorted in place, at the cost of modifying nums).

Hash Set

TimeO(n)SpaceO(n)

Intuition

Scan once and remember what you have seen; the first value already present is the duplicate. Since values are in [1, n], a boolean[] works as the set.

Algorithm

Create seen = new boolean[n + 1].
For each num: if seen[num], return num; else mark it.

Visualization

nums = [1, 3, 4, 2, 2]
1 -> mark, 3 -> mark, 4 -> mark, 2 -> mark, 2 -> already marked -> return 2

Code

java

class Solution {
    public int findDuplicate(int[] nums) {
        boolean[] seen = new boolean[nums.length]; // values are in [1, n]
        for (int num : nums) {
            if (seen[num]) {
                return num;
            }
            seen[num] = true;
        }
        return -1; // unreachable for valid input
    }
}

Complexity

Time: O(n) — single pass.
Space: O(n) — the seen array.

Binary Search on the Value Range

TimeO(n log n)SpaceO(1)

Intuition

Pigeonhole principle: for a candidate mid, count how many elements are <= mid. With no duplicate in [1, mid], that count is at most mid. If the count exceeds mid, the duplicate must be in [1, mid]; otherwise it is in [mid + 1, n]. Binary search on values, not indices.

Algorithm

lo = 1, hi = n.
While lo < hi:
- mid = (lo + hi) / 2; count = #{ x in nums : x <= mid }.
- If count > mid, hi = mid; else lo = mid + 1.
Return lo.

Visualization

nums = [1, 3, 4, 2, 2], n = 4
lo=1 hi=4 mid=2: count(<=2) = 3 > 2  -> hi = 2
lo=1 hi=2 mid=1: count(<=1) = 1      -> lo = 2
lo=2 hi=2 -> return 2

Code

java

class Solution {
    public int findDuplicate(int[] nums) {
        int lo = 1, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for (int num : nums) {
                if (num <= mid) count++;
            }
            if (count > mid) {
                hi = mid;      // too many values in [1, mid]: duplicate is here
            } else {
                lo = mid + 1;  // duplicate is in [mid + 1, hi]
            }
        }
        return lo;
    }
}

Complexity

Time: O(n log n) — log n rounds, each counting over the whole array.
Space: O(1) — a few integers; the array is not modified.

Floyd's Cycle DetectionOptimal

TimeO(n)SpaceO(1)

Intuition

View i -> nums[i] as a next pointer. Starting from index 0, the walk must eventually cycle, and the duplicate value is the node with two incoming arrows — the cycle entrance. Floyd's algorithm runs in two phases: (1) slow/fast pointers meet somewhere inside the cycle; (2) restart one pointer from 0 and move both one step at a time — they meet exactly at the entrance. Phase 2 works because the distance from the start to the entrance equals the distance from the meeting point to the entrance (modulo the cycle length).

Algorithm

Phase 1: slow = nums[0], fast = nums[nums[0]]; while slow != fast: slow = nums[slow], fast = nums[nums[fast]].
Phase 2: slow2 = 0; while slow != slow2: slow = nums[slow], slow2 = nums[slow2].
Return slow.

Dry Run

For nums = [1, 3, 4, 2, 2] the index graph is:

flowchart LR
    I0["index 0"] --> I1["index 1"]
    I1 --> I3["index 3"]
    I3 --> I2["index 2"]
    I2 --> I4["index 4"]
    I4 -->|"nums[4] = 2"| I2

Phase 1 (slow 1 step, fast 2 steps, both starting from 0):
  slow: 0 -> 1 -> 3 -> 2 -> 4
  fast: 0 -> 3 -> 4 -> 4 -> 4      meet at index 4 (fast loops 4 -> 2 -> 4)
Phase 2 (both 1 step):
  from meet: 4 -> 2 -> 4 -> 2
  from 0:    0 -> 1 -> 3 -> 2      meet at 2  -> duplicate is 2

Code

java

class Solution {
    public int findDuplicate(int[] nums) {
        // Phase 1: find a meeting point inside the cycle
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: find the cycle entrance (the duplicate value)
        int slow2 = 0;
        while (slow != slow2) {
            slow = nums[slow];
            slow2 = nums[slow2];
        }
        return slow;
    }
}

Complexity

Time: O(n) — both phases take a linear number of steps.
Space: O(1) — two or three integer pointers; nums is untouched.

Complexity Comparison

Approach	Time	Space
Sorting	O(n log n)	O(n) (copy)
Hash Set	O(n)	O(n)
Binary Search on Values	O(n log n)	O(1)
Floyd's Cycle Detection	O(n)	O(1)

Common Pitfalls

Starting Phase 1 with slow == fast and a while (slow != fast) loop — it exits immediately; use do-while or pre-advance the pointers.
Returning the Phase 1 meeting point — it is somewhere in the cycle, not necessarily the entrance.
Starting the walk at an index other than 0; index 0 is guaranteed to be outside the cycle because no value equals 0.
Sorting in place or marking visited values with negation — both modify nums, which the problem forbids.
In binary search, comparing count > mid with indices instead of values.