Coding · Two pointers
Find the Duplicate Number
- Reported once
- Medium
- Intern
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
An array nums holds n + 1 integers, each between 1 and n inclusive, and exactly one value is repeated (possibly many times). Return it without modifying the array and using only constant extra space. For [1,3,4,2,2] the answer is 2. The array can have up to 100,000 elements.
Restated in our own words, not a quote from Razorpay or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: is the length always n + 1 with every value in 1 to n? Is there exactly one repeated value, and may it appear three or more times? May I modify or sort the array? Is extra memory forbidden, or just discouraged? Do I need linear time?
I would assume the guarantees hold, so I never validate the input; the repeated value can appear any number of times; the array is read-only; and the target is O(1) extra space with O(n) time. If extra memory were allowed, a set would be the obvious answer, so the interesting problem is the constrained one.
Brute force
Say the obvious answer and why it is too slow.
There are three obvious routes. Compare every pair: O(n²) time, O(1) space, which for 100,000 elements is about five billion comparisons. Sort a copy and look for equal neighbors: O(n log n) time (with a numeric comparator in JavaScript) but O(n) extra space, and sorting the original breaks the read-only rule. Put values into a hash set until one repeats: O(n) time but O(n) space.
The only brute force that respects the space limit is the pair comparison, and it is too slow. The set solution is fast but breaks the memory rule, so none of the three satisfies both limits at once.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(1) extra
The pattern is cycle detection on an implicit linked list (Floyd's tortoise and hare). Treat the array as a function: from index i, jump to index nums[i]. Because every value is between 1 and n, no value points back to index 0, so index 0 is a start node that nothing leads to. Every node has exactly one outgoing edge, so a walk from 0 can never stop; with only n + 1 nodes it must eventually revisit one and run around a cycle.
Why the cycle entrance is the duplicate: the node where the walk first enters the cycle is reached by two different edges, one from the path before the cycle and one from inside it. Two edges into the same node means two indices hold the same value, and that value is the node number. Only the repeated value has two or more incoming edges, so the entrance is the answer.
Finding it takes two phases. In phase one a slow pointer moves one step and a fast pointer two steps until they meet inside the cycle. Say the entrance is a steps from the start and they meet b steps past it, with cycle length c. Slow has walked a + b, fast 2(a + b), and the extra a + b is a whole number of laps, so a + b = k · c. That means a steps from the meeting point also lands on the entrance. In phase two, restart one pointer at index 0 and move both one step at a time; they meet at the entrance.
Out loud: pretend the array is a linked list where i points to nums[i], and find where the cycle begins.
Walk it through
A dry run on the example, step by step.
| Phase | Step | slow | fast | Note |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | both at index 0 |
| 1 | 1 | 1 | 3 | slow +1, fast +2 |
| 1 | 2 | 3 | 4 | fast is ahead |
| 1 | 3 | 2 | 4 | fast circles the loop |
| 1 | 4 | 4 | 4 | met inside the cycle |
| 2 | 0 | 0 | 4 | slow back to index 0 |
| 2 | 1 | 1 | 2 | both move one step |
| 2 | 2 | 3 | 4 | still apart |
| 2 | 3 | 2 | 2 | met: duplicate is 2 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
With nums = [1,3,4,2,2] the walk from index 0 is 0, 1, 3, 2, 4, 2, 4, and so on, so the cycle is 2 and 4 and its entrance is 2. The trace table follows both phases.
Phase one: slow and fast both start at 0. After one round slow is 1 and fast is 3; after two, slow is 3 and fast is 4; after three, slow is 2 and fast is 4; after four, both are 4, so they meet inside the cycle. Phase two: slow goes back to 0 while fast stays at 4. One step each gives 1 and 2, another gives 3 and 4, a third gives 2 and 2. They meet at 2, the duplicate.
The code
Runnable JavaScript, checked against test cases.
function findDuplicate(nums) {
let slow = 0;
let fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
slow = 0;
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
The smallest valid input is [1,1]: the walk goes 0, 1, 1, so the cycle is a self-loop on index 1 and the answer is 1. A value repeated many times, such as [2,2,2,2,2], also works: index 0 leads to 2 and 2 points to itself.
The phase-one loop must run at least once, because both pointers start at the same place. That is why it is a do-while loop: a plain while loop would see slow equal to fast and skip phase one entirely.
The array is only read, never written. Because values start at 1, index 0 is never on the cycle, which is what guarantees the walk has a tail and the entrance is a real duplicate. If the input broke the guarantees, a value above n would send a pointer outside the array and a 0 would send the walk back to index 0, which the problem rules out.
Follow-ups to expect
Where the interviewer pushes next.
- If you were allowed to modify the array, how would cyclic sort or negation solve it in O(n) time?
- How would a binary search over the value range solve it, and what does that cost in time?
- Why must the walk start at index 0, and what would break if values could be 0?
- Can you prove that the second phase finds the cycle entrance?
- How would you also report the length of the cycle?
Where candidates slip
The mistakes this problem punishes.
The classic slip is stopping after phase one and returning the meeting point. The meeting point is somewhere inside the cycle, not necessarily the duplicate; phase two is what finds the entrance.
Others: using a plain while loop with both pointers starting at 0, so phase one never runs; starting the two pointers at different places in the two phases; treating values as zero-based indices; assuming the duplicate appears exactly twice and building a counting approach around that; and sorting or negating entries to mark visited ones, which breaks the do-not-modify rule. Mixing up a value and the index it points to is also frequent, so say out loud that the next position is nums[position].
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.