76. Find the Duplicate Number
mediumAsked at DatadogFind the single duplicate in an array of n+1 integers where each is in [1, n]. Datadog asks this for the Floyd-tortoise-on-implicit-cycle trick — finding a duplicate metric ID in O(n) time, O(1) memory.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Datadog loops.
- Glassdoor (2026-Q1)— Datadog onsite — cycle detection on implicit graph.
Problem
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space.
Constraints
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= nAll the integers in nums appear only once except for precisely one integer which appears two or more times.
Examples
Example 1
nums = [1,3,4,2,2]2Example 2
nums = [3,1,3,4,2]3Approaches
1. Hashset
First repeat in a Set.
- Time
- O(n)
- Space
- O(n)
// const seen = new Set(); for (const x of nums) if (seen.has(x)) return x; else seen.add(x);Tradeoff: Uses O(n) extra memory — violates constraint.
2. Floyd's cycle detection on f(i) = nums[i] (optimal)
Treat nums as a function: i -> nums[i]. Since two indices point to the same value, there's a cycle. Floyd finds the cycle entry = duplicate.
- Time
- O(n)
- Space
- O(1)
function findDuplicate(nums) {
let slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
slow = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}Tradeoff: O(n) time, O(1) memory, doesn't modify input. Datadog-canonical: this is the entire point of the question.
Datadog-specific tips
Datadog grades on whether you recognize this as cycle detection on an implicit graph. Without that framing, the solution looks magical. Articulate: 'Two indices pointing to the same value form a cycle; Floyd's finds the entry.'
Common mistakes
- Modifying nums (e.g., setting visited values to negative) — violates the no-modify constraint.
- Using binary search on the value space — works (O(n log n)) but Floyd is strictly better.
- Forgetting the phase 2 reset — the meeting point isn't the cycle start.
Follow-up questions
An interviewer at Datadog may pivot to one of these next:
- Find All Duplicates (LC 442) — with array modification allowed.
- First Missing Positive (LC 41) — related index-as-hash trick.
- Datadog-style: detect duplicate metric IDs in a stream with O(1) memory.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is there a cycle?
Two indices i and j both have nums[i] == nums[j]. Following f(k) = nums[k] from any start eventually lands on a value that has been visited twice — the duplicate.
Why reset slow to nums[0] in phase 2?
Standard Floyd's: distance from start to cycle entry equals distance from meeting point to cycle entry.