← Algorithmic Patterns
mediumLinked List

Find the Duplicate Number

An array of n+1 values contains integers from 1 through n. Exactly one distinct value repeats, possibly more than twice. Find it without modifying the array and using constant extra space.

LeetCode ↗

Work through the cases

3 examples

Input notation

Space-separated integers on line 1.

Expected result

The repeated value.
Case 1

Input

1 4 3 2 2

Expected output

2
Case 2

Input

3 1 3 4 2

Expected output

3
Case 3

Input

1 1

Expected output

1

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

We cannot mutate the array or use a hash table. By pigeonhole, if more than x values lie in [1,x], the duplicate is there. Binary-search the value range: count how many entries are ≤ mid; if that count exceeds mid, search the left half, otherwise the right.

We can observe that if the number of elements in [1,..x] is greater than x, then the duplicate number must be in [1,..x], otherwise the duplicate number must be in [x+1,..n].

Therefore, we can use binary search to find x, and check whether the number of elements in [1,..x] is greater than x at each iteration. This way, we can determine which interval the duplicate number is in, and narrow down the search range until we find the duplicate number.

The time complexity is O(n × log n), where n is the length of the array nums. The space complexity is O(1).

class Solution {
    public int findDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int v : nums) {
                if (v <= mid) {
                    ++cnt;
                }
            }
            if (cnt > mid) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.