Skip to main content

20. Find the Duplicate Number

mediumAsked at Electronic Arts

Find a repeated number in an array using Floyd's cycle detection, demonstrating the pointer-manipulation skills EA values for memory-constrained game engine problems.

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

Problem

Given an array nums containing n+1 integers where each integer is in the range [1, n] inclusive, there is only one repeated number. Return that 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 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. Hash set

Track seen numbers with a Set; return the first number seen twice.

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

Tradeoff:

2. Floyd's cycle detection

Treat the array as a linked list where index points to nums[index]. The duplicate creates a cycle, and Floyd's tortoise-and-hare finds the cycle entry point in O(1) space. EA expects this for the 'no extra space' constraint variant.

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:

Electronic Arts-specific tips

EA interviews cover game development data structures, pathfinding (A*, BFS on grids), spatial algorithms, and simulation problems. Grid/matrix manipulation and BFS on 2D arrays are very common.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →