☕ DSA Java Articles

Topics › Arrays › Medium

Find the Duplicate Number

Medium TUF ID 465 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums of n + 1 integers, each between 1 and n inclusive. By the pigeonhole principle at least one value repeats; the problem guarantees that exactly one value repeats, though it may appear more than twice. Return that value.

The full version adds two restrictions that shape the solution: do not modify the array, and use only constant extra space.

Constraints: 1 ≤ n ≤ 10^5, nums.length == n + 1, 1 ≤ nums[i] ≤ n.

Example 1

nums = [1, 3, 4, 2, 2]
answer = 2

Example 2

nums = [3, 3, 3, 3, 3]
answer = 3          // the duplicate may occur many times

Approach 1: Brute force, sort a copy

Intuition. After sorting, equal values sit next to each other, so the duplicate is the first value equal to its left neighbour. Sorting in place would modify the input, so we sort a copy, which breaks the space restriction instead. Comparing every pair would avoid the copy, but at O(n^2) time.

Algorithm.

  1. Copy and sort the array.
  2. Return the first a[i] with a[i] == a[i - 1].
static int bruteForce(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    for (int i = 1; i < a.length; i++) {
        if (a[i] == a[i - 1]) return a[i];
    }
    return -1;
}

Complexity. Time O(n log n) for the sort. Space O(n) for the copy.

Approach 2: Better, remember what you have seen

Intuition. Scan once and mark every value in a lookup table. The first value that is already marked is the duplicate. Because values lie in 1..n, a boolean array of size n + 1 works as the table; a HashSet would work for arbitrary values.

Algorithm.

  1. Create seen of size n + 1.
  2. For each value v: if seen[v], return v; otherwise set seen[v] = true.
static int better(int[] nums) {
    boolean[] seen = new boolean[nums.length];   // values are in [1, n] and nums.length = n + 1
    for (int v : nums) {
        if (seen[v]) return v;
        seen[v] = true;
    }
    return -1;
}

Complexity. Time O(n), a single pass. Space O(n) for the table, which violates the constant-space requirement.

A tempting fix is to store the marks inside nums itself, for example by negating nums[v]. That is O(1) extra space, but it modifies the array, which the problem forbids.

Approach 3: Optimal, Floyd’s cycle detection

Intuition. Read the array as a linked list: index i points to index nums[i]. Every index 0..n has exactly one outgoing pointer, and every pointer lands on a valid index because values are in 1..n.

Start walking from index 0. No value is 0, so nothing points back to index 0: it is the head of the list, never inside a loop. Since there are only n + 1 indices, the walk must eventually revisit one, so the path has the shape of the Greek letter rho: a tail leading into a cycle.

Now look at the node where the tail enters the cycle. It has two incoming pointers: one from the last tail node and one from the last cycle node. Two different indices i and j with nums[i] == nums[j] equal to that node’s index means the node’s index is the duplicated value. So the problem becomes: find the entrance of the cycle in a linked list, using O(1) space. That is exactly what Floyd’s tortoise-and-hare algorithm does.

Phase 1, meet inside the cycle. Move slow one step and fast two steps at a time. Once both are in the cycle, the gap between them shrinks by one each step, so they must meet.

Phase 2, find the entrance. Let a be the tail length and c the cycle length. At the meeting point, slow has taken k steps and fast 2k, and the extra k steps are whole laps, so k is a multiple of c. If slow now goes back to the head while fast stays, and both move one step at a time, after a steps the restarted pointer is at the entrance, and the other has made k + a steps in total, which is a steps plus whole laps: also the entrance. They meet exactly there.

Algorithm.

  1. slow = fast = 0. Repeat slow = nums[slow], fast = nums[nums[fast]] until they are equal.
  2. Reset slow = 0. Move both one step at a time until they are equal.
  3. Return slow.
static int optimal(int[] nums) {
    int slow = 0, fast = 0;                      // index 0 is the head: no value points back to it
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = 0;                                    // phase 2: both move one step until they meet
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;                                 // the cycle entrance is the duplicated value
}

Dry run on nums = [1, 3, 4, 2, 2]. The list is 0 → 1 → 3 → 2 → 4 → 2 → ..., a tail 0, 1, 3 and the cycle 2 → 4 → 2.

phase step slow fast
1 start 0 0
1 1 1 3
1 2 3 4
1 3 2 4
1 4 4 4 (meet)
2 start 0 4
2 1 1 2
2 2 3 4
2 3 2 2 (meet)

They meet at index 2, the duplicated value.

Complexity. Time O(n): phase 1 ends within a bounded number of laps after slow enters the cycle, and phase 2 takes a ≤ n steps. Space O(1). The array is only read, never written.

Another approach that satisfies both restrictions is binary search on the value: for a candidate x, count how many elements are ≤ x. If the count exceeds x, the duplicate is at most x. That costs O(n log n) time, so Floyd’s method is preferred.

Edge cases and pitfalls