Skip to main content

16. Find the Duplicate Number

mediumAsked at Flipkart

Find the duplicate in an array of n+1 integers in [1, n] without modifying it — Flipkart maps this to detecting double-charged COD orders in their payments pipeline.

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

Problem

Given an array nums of length n+1 with values in the range [1, n], at least one duplicate exists. Find it without modifying the array and using only constant extra space.

Constraints

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n

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 the array; first value seen twice is the answer.

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

Tradeoff:

2. Floyd cycle detection

Treat nums as a linked list where i -> nums[i]; the duplicate creates a cycle. Run tortoise/hare to find the cycle entrance. O(n) time, O(1) memory, array untouched.

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:

Flipkart-specific tips

Flipkart panels expect you to call out the index-as-pointer insight; bonus points for noting how this maps to their idempotency-key collisions on retried orders.

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

Practice these live with InterviewChamp.AI →