Skip to main content

287. Find the Duplicate Number

mediumAsked at JPMorgan

Given an array of n+1 integers in the range [1, n], find the one duplicate without modifying the array and in O(1) extra space. JPMorgan asks this on SDE onsites to test whether you spot the linked-list cycle interpretation — the Floyd's tortoise-and-hare answer is the canonical optimal.

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

Source citations

Public interview reports confirming this problem appears in JPMorgan loops.

  • Glassdoor (2026-Q1)— JPMorgan SDE onsite write-ups cite this as a 'classic constraint-driven trick'.
  • LeetCode (2026-Q1)— Tagged JPMorgan on the LeetCode company tag page.
  • Blind (2025-12)— JPMC senior SDE write-up calls this the 'most asked single-constraint problem on the loop'.

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 use 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 = [1,1]
Output
1

Approaches

1. Hash set (rejects 'O(1) space' constraint)

Walk the array; on first sight of a repeat, return it. Uses O(n) memory in violation of the stated constraint but is the fastest to code.

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

Tradeoff: Easiest to write and the answer most candidates produce first. Use as a baseline only; the interviewer is grading whether you can satisfy the constant-space constraint.

2. Sort and scan

Sort, then return the first nums[i] == nums[i-1].

Time
O(n log n)
Space
O(1) if sort in place
function findDuplicateSort(nums) {
  const a = nums.slice().sort((x, y) => x - y);
  for (let i = 1; i < a.length; i++) {
    if (a[i] === a[i - 1]) return a[i];
  }
  return -1;
}

Tradeoff: Compromise approach. Mutates a copy (still violates the strict in-place rule, though some interviewers waive it). Slower than the hash version asymptotically but smaller constants and zero memory growth if you mutate the input.

3. Floyd's tortoise and hare (optimal)

Interpret each element as a pointer i -> nums[i]. Because two indices map to the same value, the implied linked list contains a cycle whose entrance is the duplicate. Find it with Floyd's algorithm.

Time
O(n)
Space
O(1)
function findDuplicate(nums) {
  let slow = nums[0];
  let 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: The canonical answer — O(n) time and strictly O(1) extra space, never mutates the input. The cycle-detection insight is what JPMorgan interviewers want to see; if you cannot derive it, lead with the binary-search-on-value approach as an alternative.

4. Binary search on value (no cycle insight needed)

Binary-search the answer in [1, n]. For each midpoint m, count how many array elements are <= m. The duplicate lies in the half with > m matches.

Time
O(n log n)
Space
O(1)
function findDuplicateBS(nums) {
  let lo = 1, hi = nums.length - 1;
  while (lo < hi) {
    const m = (lo + hi) >> 1;
    let cnt = 0;
    for (const n of nums) if (n <= m) cnt++;
    if (cnt > m) hi = m;
    else lo = m + 1;
  }
  return lo;
}

Tradeoff: More intuitive than Floyd's but O(n log n) instead of O(n). Acceptable when you cannot remember Floyd's; JPMorgan interviewers explicitly note that landing this version still scores well on senior loops.

JPMorgan-specific tips

JPMorgan SDE interviewers ask this to distinguish 'memorised LeetCode' from 'pattern-recognising engineer'. The strongest answer narrates the three approaches in order — hash, sort, then either Floyd's or binary-search — and explains which constraint each one violates or satisfies. The interviewer often waits for you to ask 'are you OK with mutating the array?' before producing the cycle answer; asking explicitly is part of the grade.

Common mistakes

  • Reading 'cannot modify the array' and reaching for the hash set anyway — the constant-space constraint is the whole point of the question.
  • Initialising slow = 0 in Floyd's — must start at nums[0] because index 0 is not a valid value in [1, n] but the algorithm walks values as next-indices.
  • Returning fast at the end of phase 1 — phase 1 only locates a node in the cycle, not the entrance; phase 2 is required.
  • Mis-counting in binary search: the test must be 'count <= m > m', not 'count of m'.

Follow-up questions

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

  • What if multiple duplicates exist? (LC 442 — different problem; use index marking.)
  • What if the array can be modified? (Index marking in O(n) time, O(1) extra space.)
  • Prove correctness of Floyd's on this particular graph (why does the entrance equal the duplicate?).
  • What is the smallest n for which Floyd's outperforms the hash set in practice?

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 the cycle-detection interpretation work?

Treat the array as a function f(i) = nums[i]. Since two indices p and q both produce the same value v (the duplicate), they both point to the same successor. That means the implied graph has two predecessors meeting at one node — the textbook signature of a cycle in a linked list. The duplicate value is exactly the entrance of that cycle, and Floyd's two-phase algorithm finds it in O(n) time with O(1) memory.

What if the interviewer says 'I do not know Floyd's — can you do better than n log n without it?'

Honest answer: not in general. The binary-search-on-value approach is the simplest O(n log n) solution that respects the no-modify constraint. If they push for O(n), Floyd's is the only known answer without modifying the array.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →