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.

Find the Duplicate Number - LeetCode Solution

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).

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

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. First, detect the cycle by moving slow and fast pointers until they meet. Then, initialize a second pointer at the start and move both pointers one step at a time until they meet again; this meeting point is the duplicate number.

Optimal Approach

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.

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.

Solution

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

1class Solution {
  public int findDuplicate(int[] nums) {
      int slow = 0;
      int fast = 0;
5
      while (true) {
          slow = nums[slow];
          fast = nums[nums[fast]];
          if (slow == fast) {
              break;
          }
      }
13
      int slow2 = 0;
      while (true) {
          slow = nums[slow];
          slow2 = nums[slow2];
          if (slow == slow2) {
              return slow;
          }
      }
  }
23}

Step-by-Step Solution

1

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.

2

Locate Cycle Entry Point to Identify Duplicate Number

10slow2 = 0
11while True:
12    slow = nums[slow]
13    slow2 = nums[slow2]
14    if slow == slow2:
15        return slow

Objective

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

Key Insight

After detecting the cycle, initializing a second pointer at the start and moving both pointers one step at a time leverages the property that the distance from the start to the cycle entry equals the distance from the meeting point to the cycle entry. Their meeting point reveals the duplicate number without modifying the array or using extra space.

Interview Quick-Check

Core Logic

Move slow and slow2 one step at a time until they meet; the meeting index is the duplicate number.

State & Boundaries

The loop continues until slow equals slow2, ensuring the cycle entry is found.

Common Pitfalls & Bugs

Not resetting slow2 to 0 before the second loop or moving pointers incorrectly can cause failure to find the duplicate.

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.

Line 15 Critical

return slow

Return the duplicate number found at cycle entry.

Returning slow (or slow2) provides the duplicate number without modifying the array or using extra space.

Line 5 Core

slow = nums[slow]

Move slow pointer one step forward.

Advancing slow by one step simulates traversal through the linked list representation of the array, essential for Floyd's cycle detection.

Line 12 Core

slow = nums[slow]

Move slow pointer one step forward.

Advancing slow one step at a time from the meeting point aligns with slow2 to find the cycle entry.

Line 13 Core

slow2 = nums[slow2]

Move slow2 pointer one step forward.

Moving slow2 one step from the start ensures both pointers traverse equal distances to the cycle entry.

Line 3 Core

slow, fast = 0, 0

Initialize slow and fast pointers at index 0.

Starting both pointers at the beginning of the array sets up the cycle detection process by treating the array as a linked list with indices as nodes.

Line 8 Core

break

Break the loop upon cycle detection.

Exiting the loop after detection allows the algorithm to proceed to locating the cycle's entry point.

Line 10 Core

slow2 = 0

Initialize a second pointer slow2 at index 0.

Starting slow2 at the beginning prepares to find the cycle entry point by moving it in tandem with slow.

Line 4 Standard

while True:

Begin an infinite loop to detect cycle intersection.

The loop continues until the slow and fast pointers meet, which confirms the presence of a cycle caused by the duplicate number.

Line 11 Standard

while True:

Begin an infinite loop to find the cycle entry.

This loop continues until slow and slow2 meet at the cycle entry, which corresponds to the duplicate number.

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?

Because the distance from the start to the cycle entry equals the distance from the meeting point to the cycle entry along the cycle, moving both pointers at the same speed guarantees they meet at the cycle entry, which corresponds to the duplicate number.

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`

1	`class Solution {`
2	`public int findDuplicate(int[] nums) {`
3	`int slow = 0;`
4	`int fast = 0;`
5
6	`while (true) {`
7	`slow = nums[slow];`
8	`fast = nums[nums[fast]];`
9	`if (slow == fast) {`
10	`break;`
11	`}`
12	`}`
13
14	`int slow2 = 0;`
15	`while (true) {`
16	`slow = nums[slow];`
17	`slow2 = nums[slow2];`
18	`if (slow == slow2) {`
19	`return slow;`
20	`}`
21	`}`
22	`}`
23	`}`

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