Skip to main content

14. Find the Duplicate Number

mediumAsked at Confluent

Find the repeated number in an n+1 array of values [1..n] using O(1) space — Confluent uses it because cycle-detection on an implicit graph mirrors offset duplication checks in a Kafka log.

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

Problem

Given an array nums of n+1 integers each in [1..n] with one repeated value (possibly more than twice), return the repeated number. Don't modify nums and use O(1) extra space.

Constraints

  • 1 <= n <= 10^5
  • nums.length == n+1
  • Exactly one duplicate value

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

Walk and add to a set; first repeat is the duplicate.

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

Tradeoff:

2. Floyd's tortoise and hare

Treat indices as a linked list f(i) = nums[i]. The duplicate forces a cycle; find the entry node with tortoise/hare meeting and a second pointer from index 0.

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:

Confluent-specific tips

Confluent grades the cycle-detection explanation more than the code — call out that this same trick detects duplicate offset processing across a consumer-group rebalance when exactly-once semantics need verifying.

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 Confluent interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →