Skip to main content

287. Find the Duplicate Number

mediumAsked at Intel

n+1 integers in [1, n] are placed in an array. Exactly one number is repeated. Find it WITHOUT modifying the array and using O(1) extra space. Intel loves this one because the only O(1)-space algorithm requires reframing array indices as a linked list and applying Floyd's cycle detection — a real 'aha' moment that separates senior IC from mid-level.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE-II onsite reports cite find-duplicate as a 30-minute Floyd's-trick round.
  • Levels.fyi (2025-09)— Intel SWE interview reports describe the O(1)-space Floyd's variant as the senior signal.
  • LeetCode discuss (2025-11)— Intel-tagged in the LC company-frequency listing.

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

Example 3

Input
nums = [3,3,3,3,3]
Output
3

Approaches

1. Hash set (brute)

Walk; if you've seen the value before, return it.

Time
O(n)
Space
O(n)
function findDuplicateHash(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) return x;
    seen.add(x);
  }
  return -1;
}

Tradeoff: Easy. Violates the explicit O(1)-space constraint.

2. Sort then scan (alternative)

Sort and find the first index where nums[i] === nums[i+1].

Time
O(n log n)
Space
O(1) — but modifies the array
function findDuplicateSort(nums) {
  nums.sort((a, b) => a - b);
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) return nums[i];
  }
  return -1;
}

Tradeoff: Violates the 'cannot modify' constraint. Drop it once you hear that constraint repeated.

3. Floyd's tortoise and hare (optimal)

Treat nums as a function f(i) = nums[i]. Because values are in [1, n] and there are n+1 of them, following nums[nums[nums[...]]] is a sequence that must repeat. The duplicate value is the entry point of the cycle.

Time
O(n)
Space
O(1)
function findDuplicate(nums) {
  let slow = nums[0];
  let fast = nums[0];
  // Phase 1: find a meeting point inside the cycle
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);
  // Phase 2: find the cycle entry (= duplicate value)
  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

Tradeoff: Linear time, constant space, no array modification. The aha: treating array indices as nodes in a graph where i -> nums[i] turns this into LC 142 (Linked List Cycle II). The duplicate is the cycle entry because two distinct indices both point to it.

Intel-specific tips

Intel interviewers will explicitly bait you into the wrong approach by NOT stating the constraints clearly upfront. Repeat them back: 'no modification, O(1) space.' Then narrate: 'Sum trick fails because there could be more than two duplicates. Bit manipulation fails because values are arbitrary. The constraint that values are in [1, n] and there are n+1 elements means index-to-value forms a function with a cycle.' That derivation IS the senior signal.

Common mistakes

  • Sorting the array — modifies it, violates the constraint.
  • Using the Gauss-sum trick — fails because the duplicate might appear MORE than twice, so n*(n+1)/2 - sum doesn't isolate the duplicate.
  • Phase 2 starting both pointers at nums[0] — wrong; the standard reset is slow back to nums[0], fast stays at the meeting point.
  • Looping with `while` instead of `do-while` in phase 1 — slow and fast both start at nums[0] so a strict-while would exit immediately.

Follow-up questions

An interviewer at Intel may pivot to one of these next:

  • Linked List Cycle II (LC 142) — same Floyd's-second-phase logic on an actual linked list.
  • Happy Number (LC 202) — Floyd's applied to the digit-square iteration.
  • Find All Duplicates in an Array (LC 442) — multiple duplicates; if you CAN modify, mark indices via sign flips.
  • What if you could modify the array? (Cyclic sort: place each value at its 'home' index nums[i] = i+1; the unplaced index is the duplicate.)

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 does treating nums as a function form a cycle?

f: index -> value, where i -> nums[i]. The image of f is in [1, n] but the domain is [0, n] (n+1 indices). By pigeonhole, two distinct indices i and j must map to the same value. That value is the cycle entry — both i and j point to it, so the chain from 0 enters the cycle there.

What's the cycle-entry formula derivation in phase 2?

If F is the steps from start to cycle entry and L is the cycle length, the meeting point M satisfies (slow has gone F + k, fast has gone 2(F + k)) and they're at the same modular position. Math works out so that walking F more steps from the meeting point lands on the entry — and walking F from start also lands on the entry. So one pointer restarts from start, both walk speed 1, they meet at the entry.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →