Difficulty: MediumLinked List

Find the Duplicate Number

Problem in Plain English

You are given an array of n plus one integers drawn from one to n with exactly one repeated value. Return the repeated number without modifying the array and with constant extra space.

Problem Statement

Given an integer array nums of length $n+1$ , whose values are between $1$ and $n$ inclusive, return the only distinct value that occurs more than once. That value may occur more than twice; some other values may be absent.

The required solution must leave the array unchanged and use constant extra space. The hash-set approach below is a teaching baseline that relaxes the space requirement; the optimal approach satisfies both requirements.

Constraints

$1 \le n \le 10^5$
nums has $n+1$ elements.
Every value lies between $1$ and $n$ inclusive.
Exactly one distinct value occurs two or more times; every other value occurs at most once.

Examples

Example 1

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

The value 2 appears twice, so the answer is 2.

Example 2

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

Value 3 occurs at two different positions. Following links from index 0 gives 0 → 3 → 4 → 2 → 3, whose loop entrance is 3.

Example 3

Input: nums = [3, 3, 3, 3, 3]
Output: 3

Only the distinct value 3 repeats, although it occurs five times. Values 1, 2 and 4 may be absent. The walk 0 → 3 → 3 enters a self-loop at the repeated value.

Example 4

Input: nums = [1, 1]
Output: 1

The smallest valid array has two entries but only one allowed value. Both entries are 1; the implicit walk enters the self-loop at index 1.

Intuition

Treat each array index as a node and its stored value as the index of the next node. Example 1 produces the walk 0 → 1 → 3 → 2 → 4 → 2, so the walk enters a loop at index 2. Index 0 cannot be revisited because no value is zero. The first loop node has two incoming links, making its index the repeated value. Floyd's slow and fast pointers find that entrance using only index variables and reads from the array.

Approaches

Hash Set

Solution Details

Reveal Hash Set: intuition, complexity, and code

Intuition

A set records which values have already appeared, so membership before insertion detects the first repeated occurrence. Uniqueness of the repeated distinct value makes that occurrence the answer. This baseline leaves the input unchanged but allocates linear memory, so it does not satisfy the required constant-space restriction.

Step-by-Step Logic

Initialize an empty set and scan the array in its original order. Example 1 uses the array shown above.
Before inserting each current value, test membership in the set. A miss means this is its first occurrence; insert it and advance to the next position.
On a membership hit, return the current value immediately. The Example 1 table records the complete prefix and the hit.
The fallback return is defensive and unreachable under the guaranteed repeated-value contract.

Why It Works

Before processing each element, seen contains exactly the distinct values in the processed prefix. Membership means this value also occurred at an earlier position, so returning it is sound. Otherwise inserting the value preserves the invariant. A repeated value is guaranteed, so the scan eventually finds a second occurrence; because only one distinct value repeats, that value is the required answer. The defensive negative return cannot occur on a valid input.

Dry Run

Hash Set: variable states at each step
position before → after	current value	seen before	action / seen after
0 → 1	1	{}	insert; {1}
1 → 2	3	{1}	insert; {1,3}
2 → 3	4	{1,3}	insert; {1,3,4}
3 → 4	2	{1,3,4}	insert; {1,3,4,2}
4 → return	2	{1,3,4,2}	membership hit; return 2

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Here n is one less than the array length. At most n + 1 membership checks and n insertions give O(n) expected time with expected constant-time hash operations. The set allocates up to n distinct entries and its hash table, so auxiliary space is O(n), violating the required space bound. No array copy is made and no element is changed.

Code

Solution.java

1import java.util.HashSet;2
3class Solution {4    public int findDuplicate(int[] nums) {5        HashSet<Integer> seen = new HashSet<>();6        for (int num : nums) {7            if (seen.contains(num)) {8                return num;9            }10            seen.add(num);11        }12        return -1;13    }14}

Hints

Hint 1

A set-based scan finds the answer but breaks the constant-space rule, so treat it only as a starting point.

Hint 2

View index i as a node whose next node is nums[i]: with n + 1 values in [1, n], two nodes share a target and a cycle is guaranteed.

Hint 3

Run the two-phase cycle hunt: race the pointers to a meeting point, reset one to the start, then walk both together to the duplicate.

Edge Cases

The minimum input [1,1] starts directly on the self-loop; the race must still execute once and the reset phase needs no hop.
The repeated value may occur more than twice, as in [3,3,3,3,3]; absent nonduplicate values do not invalidate the input.
An entrance can equal nums[0], or a long incoming path can lead to a short loop. The meeting-to-entrance distance depends on both phases.
A repeated value at the largest allowed index remains a valid target; the array has one more slot than the maximum value.

Common Mistakes and Interview Tips

Mixing start conventions: this code starts both racers at nums[0] and resets to nums[0]. Starting and resetting both at index zero is also valid; mixing the conventions breaks the distance proof.
Testing equality before the first race hop returns the shared starting node without detecting a cycle.
Returning the first meeting as the answer can return an interior cycle node. Run the entrance phase.
Sorting, sign-marking or overwriting entries violates input preservation; a set violates constant auxiliary space.
Assuming every nonduplicate value must appear or that the duplicate occurs exactly twice excludes valid inputs.
Using arbitrary out-of-range or zero values destroys the guaranteed valid-index walk; Floyd here relies on the stated input contract.

Key Takeaway

When values fall inside the index range, follow them as links: a forced cycle turns array duplicates into a linked-list entrance hunt.