Skip to main content

76. Find the Duplicate Number

mediumAsked at Datadog

Find 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 Alex Chen, 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^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

Examples

Example 1

Input
nums = [1,3,4,2,2]
Output
2

Example 2

Input
nums = [3,1,3,4,2]
Output
3

Approaches

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Find the Duplicate Number and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →