🌱 Keegan's Digital Garden

287. Find the Duplicate Number

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- This isn't a linked list question, but it utilizes a common pattern/technique used to solve linked list problems.
- The key idea is using **slow and fast pointers**, similar to Floyd's Cycle Detection Algorithm.
- Given constraints:
  - **Cannot modify the array** (i.e., no sorting).
  - **Must use constant space** (i.e., no extra data structures like sets or maps).
  - **Must find the duplicate in O(n) time complexity**.

🤔What Did I Struggle With?

- Understanding why the cycle detection algorithm works in an array context.
- Mapping the problem to Floyd's Tortoise and Hare approach.
- Ensuring that the cycle is detected correctly.
- Understanding why moving both pointers at the same pace after detection finds the duplicate.

💡 Explanation of Solution

- Treat the array as a linked list where each index points to another index.
- Each element in the array can be viewed as a pointer to the next index, forming a directed graph.
- Since there are `n+1` numbers in the range `[1, n]`, there **must** be a cycle (Pigeonhole Principle).
- The cycle detection algorithm works in two phases:

  **Phase 1: Detect the Cycle**
  - Initialize `slow` and `fast` pointers at `nums[0]`.
  - Move `slow` one step at a time (`slow = nums[slow]`).
  - Move `fast` two steps at a time (`fast = nums[nums[fast]]`).
  - When `slow == fast`, a cycle is detected.

  **Phase 2: Find the Start of the Cycle (Duplicate Number)**
  - Reset `slow` to `nums[0]`, keep `fast` at the meeting point.
  - Move both one step at a time until they meet.
  - The meeting point is the **duplicate number**.

  This works because the distance from the start to the cycle entrance is equal to the distance from the meeting point to the entrance when moving at the same pace.

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];
 
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
 
        slow = nums[0];
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
 
        return slow;   
    }
};

Graph View