Skip to main content

287. Find the Duplicate Number

medium

Find the duplicate number in an array of n + 1 integers drawn from [1, n] — without modifying the array, and in constant extra space. The classic cycle-detection trick (Floyd's algorithm on an implicit linked list) shines here.

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

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Hash set or counting array are O(n) time and space — but the problem forbids modifying the array AND requires O(1) space.

Hint 2

Binary search: pick a value v in [1, n], count how many nums are <= v. By pigeonhole, the duplicate is in the half where the count exceeds the value. O(n log n) time, O(1) space.

Hint 3

Floyd's tortoise and hare: treat the array as a linked list where node i points to nums[i]. The duplicate creates a cycle. Find the cycle's entry.

Hint 4

Phase 1: slow = nums[0], fast = nums[0]; advance slow once and fast twice until they meet. Phase 2: reset slow = nums[0]; advance both one step at a time; the meeting point is the duplicate.

Solution approach

Reveal approach

Floyd's tortoise and hare on the implicit linked list where index i 'points to' nums[i]. Because there are n + 1 nodes mapping into [1, n], at least one value is reached twice — creating a cycle whose entry is the duplicate. Phase 1: slow = fast = nums[0]; loop slow = nums[slow], fast = nums[nums[fast]] until they meet inside the cycle. Phase 2: reset slow = nums[0]; while slow != fast, slow = nums[slow], fast = nums[fast]. They now meet at the cycle entry — the duplicate value. O(n) time, O(1) space, doesn't modify the array. Binary-search alternative: search v in [1, n]; count(nums <= v) > v means the duplicate is in [lo, v]. O(n log n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • cycle-detection
  • fast-slow-pointers
  • binary-search
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Find the Duplicate Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →