How do you solve Find the Duplicate Number?

Use two pointers starting at index 0. Move slow by one step and fast by two steps until they meet inside the cycle. Then, start a new pointer from the beginning and move it and slow one step at a time until they meet. The meeting index corresponds to the duplicate number. This approach uses O(1) space and O(n) time without modifying the array.

Find the Duplicate Number

Q: What is the time complexity of Find the Duplicate Number?

O(n). Each pointer traverses the array at most a constant number of times. The first loop detects the cycle in O(n), and the second loop finds the cycle entry in O(n).

Q: What pattern does Find the Duplicate Number use?

The Pattern: Fast & Slow Pointers (Cycle Detection in Array as Linked List) The Heuristic: When an array contains a duplicate that creates a cycle in the implicit linked list formed by indices and values, use two pointers moving at different speeds to detect the cycle and find its entry point without modifying the array or using extra space.

Medium Fast & Slow Pointers

Problem

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), return the duplicate number. You must not modify the array and must use only constant extra space.

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ n (where n = nums.length - 1)
Only one duplicate number exists but it could be repeated more than once

Example

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

Output: 2

The array contains numbers from 1 to 4 with one duplicate. The algorithm treats the array as a linked list where each index points to the value at that index. Starting with slow and fast pointers at index 0, slow moves one step at a time (slow = nums[slow]) and fast moves two steps at a time (fast = nums[nums[fast]]). Eventually, slow and fast meet inside the cycle created by the duplicate number, confirming the presence of a cycle.

Approach

Straightforward Solution

A brute-force approach would use extra space like a hash set to detect duplicates or sort the array, both violating the space or modification constraints. These approaches are either O(n) space or O(n log n) time.

Core Observation

The array can be interpreted as a linked list where each element points to the index of the next element. Because there is a duplicate number, this linked list contains a cycle.

Path to Optimal

Preview

Recognizing the problem as cycle detection in a linked list allows the use of Floyd's Tortoise and Hare algorithm. The key insight is that the duplicate number corresponds to the entry point of the cycle…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers starting at index 0. Move slow by one step and fast by two steps until they meet inside the cycle…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each pointer traverses the array at most a constant number of times. The first loop detects the cycle in O(n), and the second loop finds the cycle entry in O(n).

Space

O(1)

Only a fixed number of pointers are used, and no additional data structures are allocated, satisfying the constant extra space requirement.

Pattern Spotlight

Fast & Slow Pointers (Cycle Detection in Array as Linked List)

When an array contains a duplicate that creates a cycle in the implicit linked list formed by indices and values, use two pointers moving at different speeds to detect the cycle and find its entry point without modifying the array or using extra space.

Solution

Python

1class Solution:
  def findDuplicate(self, nums: list[int]) -> int:
      slow, fast = 0, 0
      while True:
          slow = nums[slow]
          fast = nums[nums[fast]]
          if slow == fast:
              break
      
      slow2 = 0
      while True:
          slow = nums[slow]
          slow2 = nums[slow2]
          if slow == slow2:
              return slow

Step-by-Step Solution

Advance Slow and Fast Pointers to Detect Cycle Intersection

3slow, fast = 0, 0
4while True:
5    slow = nums[slow]
6    fast = nums[nums[fast]]
7    if slow == fast:
8        break

Objective

To move slow and fast pointers through the array to find a point inside the cycle created by the duplicate number.

Key Insight

Treating the array as a linked list where each value points to the next index, the duplicate number creates a cycle. Moving slow by one step and fast by two steps ensures that if a cycle exists, the pointers will eventually meet inside it. This is the classic Floyd's Tortoise and Hare cycle detection technique adapted to arrays.

Interview Quick-Check

Core Logic

Slow moves one step (slow = nums[slow]) and fast moves two steps (fast = nums[nums[fast]]) until they meet, confirming a cycle.

State & Boundaries

The loop continues indefinitely until slow equals fast, guaranteeing detection of the cycle.

Common Pitfalls & Bugs

Failing to move fast pointer two steps or mixing up indices and values can cause incorrect cycle detection or infinite loops.

Locate Cycle Entry Point to Identify Duplicate Number

To find the starting point of the cycle, which corresponds to the duplicate number in the array.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 6 Critical

fast = nums[nums[fast]]

Move fast pointer two steps forward.

Moving fast two steps accelerates it relative to slow, ensuring that if a cycle exists, the two pointers will eventually meet inside it.

Line 7 Critical

if slow == fast:

Check if slow and fast pointers have met.

Detecting equality between slow and fast pointers confirms the cycle's presence, which is caused by the duplicate number.

Line 14 Critical

if slow == slow2:

Check if slow and slow2 pointers have met at cycle entry.

When slow equals slow2, the cycle entry is found, revealing the duplicate number.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does moving a pointer from the start and the meeting point one step at a time lead to the duplicate number?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find the Duplicate Number from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find the Duplicate Number drill

or drill a free problem

1	`class Solution:`
2	`def findDuplicate(self, nums: list[int]) -> int:`
3	`slow, fast = 0, 0`
4	`while True:`
5	`slow = nums[slow]`
6	`fast = nums[nums[fast]]`
7	`if slow == fast:`
8	`break`
9
10	`slow2 = 0`
11	`while True:`
12	`slow = nums[slow]`
13	`slow2 = nums[slow2]`
14	`if slow == slow2:`
15	`return slow`

3	`slow, fast = 0, 0`
4	`while True:`
5	`slow = nums[slow]`
6	`fast = nums[nums[fast]]`
7	`if slow == fast:`
8	`break`