#287 Find the Duplicate Number

frequently reported atNVIDIA Amazon Bloomberg Google Microsoft

the problem

In plain words

An array nums holds n + 1 integers, each between 1 and n. Exactly one value appears more than once (it may appear many times). Return that value — without modifying nums, and using only constant extra space.

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

out 2

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

out 3

in nums = [3,3,3,3,3]

out 3

1 ≤ n ≤ 10⁵
nums.length == n + 1
1 ≤ nums[i] ≤ n
Exactly one value repeats (possibly many times)
Don't modify nums; use only O(1) extra space
Follow-up: linear time

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternFast & slow pointers Binary search on the answer

where this runsPollard's rho method for factoring large integers spots a repeat in a number sequence with this same tortoise-and-hare loop.

Read the array as a linked list: index i is a node whose next is nums[i]. Start at index 0 — no value is 0, so nothing points back to it. Two indices hold the duplicate, so two arrows enter the same node: that node is where a cycle begins. Floyd from LC 142 finds it in O(1) space.

solutions

From brute force to optimal

The first value that seen.add rejects is the duplicate.

Walk nums.
If seen.add(x) returns false, return x.

timeO(n)

One pass; set operations are O(1) average.

spaceO(n)

The set can hold n values — this breaks the O(1)-space rule.

javajava.util.*

1class Solution {2    public int findDuplicate(int[] nums) {3        Set<Integer> seen = new HashSet<>();4        for (int x : nums) {5            if (!seen.add(x)) return x; // add() is false the second time we meet x6        }7        return -1; // unreachable for valid input8    }9}

Count how many values are ≤ mid. If more than mid of them are, the repeat lives in 1..mid (pigeonhole); otherwise in mid + 1..n.

lo = 1, hi = n.
mid = lo + (hi − lo) / 2; count = values ≤ mid.
count > mid → hi = mid, else lo = mid + 1.
Return lo.

timeO(n log n)

About log₂ n rounds, each scanning all n + 1 values.

spaceO(1)

A few counters; nums is only read.

javajava.util.*

1class Solution {2    public int findDuplicate(int[] nums) {3        int lo = 1, hi = nums.length - 1; // the answer is a value in 1..n4        while (lo < hi) {5            int mid = lo + (hi - lo) / 2;6            int count = 0;7            for (int x : nums) if (x <= mid) count++;8            if (count > mid) hi = mid;    // more than mid values fit in 1..mid → a repeat lives there9            else lo = mid + 1;10        }11        return lo;12    }13}

Phase 1: slow = nums[slow], fast = nums[nums[fast]] until they meet. Phase 2: p from index 0 and slow from the meeting point, one hop each — they meet at the duplicate.

slow = nums[0], fast = nums[nums[0]].
While slow != fast: slow = nums[slow]; fast = nums[nums[fast]].
p = 0; while p != slow: p = nums[p]; slow = nums[slow].
Return p.

timeO(n)

Same argument as LC 142: each phase takes at most about n hops.

spaceO(1)

Three ints; the array is only read.

javajava.util.*

1class Solution {2    public int findDuplicate(int[] nums) {3        int slow = nums[0], fast = nums[nums[0]]; // index i "points to" index nums[i]4        while (slow != fast) {5            slow = nums[slow]; // one hop6            fast = nums[nums[fast]]; // two hops7        }8        int p = 0; // phase 2: restart from the head (index 0)9        while (p != slow) {10            p = nums[p];11            slow = nums[slow];12        }13        return p; // the cycle's entry = the value two indices point to14    }15}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int findDuplicate(int[] nums) {3        int slow = nums[0], fast = nums[nums[0]]; // index i "points to" index nums[i]4        while (slow != fast) {5            slow = nums[slow]; // one hop6            fast = nums[nums[fast]]; // two hops7        }8        int p = 0; // phase 2: restart from the head (index 0)9        while (p != slow) {10            p = nums[p];11            slow = nums[slow];12        }13        return p; // the cycle's entry = the value two indices point to14    }15}

in the room

How to say it in the interview

talk track

Say the constraints out loud: can't modify, O(1) space — that rules out sorting and a HashSet.
Then the reframe: "every index has exactly one next, nums[i]; the duplicate value has two incoming arrows, so it's where a cycle starts."
Code it exactly like Linked List Cycle II, with x = nums[x] instead of x = x.next.
If the reframe doesn't come to you, binary search on the value (O(n log n), O(1) space) is a strong answer too.

traps

Sorting nums or marking visited indices by negating values — both modify the array, which the problem forbids.
Starting phase 2 from nums[0] instead of index 0 — the head of this "list" is index 0.
Mixing up index and value: here a node is an index, and the entry's index d is the duplicate value d.

what they ask next

Follow-ups

Why must a duplicate exist at all?

Pigeonhole: n + 1 values drawn from only n possibilities — at least two must be equal.

What if you were allowed to modify the array?

Mark each seen value by negating nums[|x|]; meeting an already-negative slot reveals the duplicate. O(n) time, O(1) space — but it changes the input, so not here.

before you submit

Edge cases to test

n = 1: [1,1] → 1.
The duplicate appears many times: [3,3,3,3,3] → 3.
An index that points to itself off the walk's path, like nums[1] = 1 in [2,1,2].
nums must be unchanged after your call.

practise next