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 Sam K., 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

More Math practice problems

See all Math problems →