Find the Duplicate Number

cyclic-sorttwo-pointerslinked-list

Problem

Given an array of integers nums containing n + 1 integers, each in the range [1, n] inclusive, there is exactly ONE repeated number. Find it, without modifying the array and using only O(1) extra space.

Examples

Example 1

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

Output: 2

Explanation: 2 appears twice.

Example 2

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

Output: 3

Explanation: 3 appears twice.

Constraints

•1 <= n <= 10^5
•nums.length == n + 1
•1 <= nums[i] <= n

Hints

Hint 1

A hash set spotting the first repeated value works in O(n) time — but costs O(n) extra space, which the problem explicitly disallows.

Hint 2

Since every value is in [1, n], each value can be treated as a POINTER to an index — following these pointers repeatedly traces out a path.

Hint 3

Because there's a duplicate, that path must eventually loop back on itself — this is structurally identical to detecting a cycle in a linked list.

Solutions

public int findDuplicateHashSet(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) {
        if (!seen.add(n)) return n; // add() returns false if n was already present
    }
    throw new IllegalArgumentException("No duplicate found");
}

Time: O(n) · Space: O(n) — violates the problem's O(1) space requirement