Find The Duplicate Number

MEDIUM✓ CHIP-TIMEDLC #287 — FULL STATEMENT ↗

The drill: An array of n+1 numbers drawn from 1..n hides exactly one value that shows up more than once — pin it down without sorting the array, and without a second array's worth of memory in the race line.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of n+1 integers, every value drawn from the range 1 through n, is handed over — with n+1 values packed into only n possible slots, at least one value has to repeat.

This course's contract guarantees exactly one value repeats, though it may appear more than twice, and every other value in 1..n shows up exactly once.

The job is to name that repeated value, without sorting the array and without spending an extra array's worth of memory in the fast solution — modifying the input array itself also isn't allowed.

EX 01

nums = [3, 1, 3, 2]

→ 3

EX 02

nums = [2, 2, 2, 2, 2]

→ 2

ONE VALUE REPEATED EVERY TIME

EX 03

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

→ 3

array holds n+1 integers, each drawn from 1 through n
exactly one value repeats, possibly more than twice
the array itself must stay unmodified in the fast solution
answer is the single repeated value, not its positions

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A set that remembers every value seen so far catches the repeat the instant it appears — simple and correct, at the cost of an extra array's worth of memory.

HINT 2 THE STRUCTURE

Treat each value as an arrow: index i points to index nums[i]. Because two different indices are forced to point at the duplicate's slot, that slot has two owners — which is exactly the shape of a cycle.

HINT 3 ONE STEP FROM THE ANSWER

Run Floyd's tortoise and hare on that pointer chain to land inside the cycle, then restart one pointer at the array's start and step both one index at a time — they meet exactly at the duplicate value.

COACH'S BOARD — THE PATTERN, STEP BY STEP

FLOYD ON THE VALUESPATTERN · CYCLE DETECTIONnums = [3, 1, 3, 2]

STEP 1

Array [3, 1, 3, 2] packs 4 values from 1..3 into 4 slots — a duplicate is forced. Treat index i as an arrow pointing at index nums[i].

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/find-the-duplicate-number.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow2 = nums[0]
        while slow2 != slow:
            slow2 = nums[slow2]
            slow = nums[slow]
        return slow

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 14 LN

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        seen = set()
        for v in nums:
            if v in seen:
                return v
            seen.add(v)
        return -1

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        int slow2 = nums[0];
        while (slow2 != slow) {
            slow2 = nums[slow2];
            slow = nums[slow];
        }
        return slow;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 17 LN

class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int v : nums) {
            if (!seen.add(v)) {
                return v;
            }
        }
        return -1;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 11 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED