Coding Interview PatternsFind the Duplicate Number
MediumFast and Slow Pointers

Find the Duplicate Number

Explanation & Solution

Practice Problem

Description

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is exactly one repeated number. Find and return this duplicate number.

You must solve this problem without modifying the array nums and using only constant extra space.

Input:nums = [1, 3, 4, 2, 2]
0
1
1
3
2
4
3
2
4
2

Output: 2

Explanation: The number 2 appears twice, so it is the duplicate.

Constraints

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • There is only one repeated number in nums, but it could be repeated more than once.

Approach

Fast and Slow Pointers pattern

1. Model the Array as a Linked List

  • Treat each index i as a node and nums[i] as a pointer to the next node.
  • Since values are in the range [1, n] and the array has n + 1 elements, there must be a cycle (by the Pigeonhole Principle).
  • The entrance to the cycle corresponds to the duplicate number.

2. Phase 1 — Detect the Cycle

  • Initialize two pointers: slow = nums[0] and fast = nums[0].
  • Move slow one step at a time: slow = nums[slow].
  • Move fast two steps at a time: fast = nums[nums[fast]].
  • Continue until slow === fast. They are now guaranteed to meet inside the cycle.

3. Phase 2 — Find the Cycle Entrance

  • Reset slow back to nums[0].
  • Move both slow and fast one step at a time: slow = nums[slow], fast = nums[fast].
  • The point where they meet again is the entrance to the cycle, which is the duplicate number.

4. Return the Result

  • Return slow (or fast, since they are equal). This is the duplicate value.

🧠 Key Insight

  • This is Floyd’s Tortoise and Hare algorithm, originally designed for cycle detection in linked lists. By interpreting array values as pointers, the duplicate number becomes the entry point of a cycle, which can be found without modifying the array or using extra space.
Time
O(n)both phases traverse at most O(n) steps.
Space
O(1)only two pointer variables are used.

Visualization

Input:
[1, 3, 4, 2, 2]
1031422324
—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone
8 steps

Solution Code

Previous
Intersection of Two Linked Lists
Next
Circular Array Loop