thesarfo

Reference

Find the Duplicate Number

Using Floyd's Tortoise and Hare cycle detection to find a duplicate in an array without modifying it or using extra space.

views 0

Given an array of integers nums where 1 <= nums[i] <= n (n is the size of the array), find the duplicate number in the array. There is only one duplicate number in the array, but it could be repeated multiple times. You must solve it without modifying the array and using O(1) extra space. (LeetCode)

Approach: This problem can be solved efficiently using Floyd’s Tortoise and Hare (Cycle Detection) algorithm. This technique is based on the fact that the array can be interpreted as a linked list, and since one number is duplicated, it creates a cycle in this list.

Key insight: the array contains integers in the range [1, n], so each number can be viewed as a pointer to another index in the array. Since there is only one duplicate, the array forms a cycle in terms of indices.

Algorithm (Floyd’s Tortoise and Hare):

  1. Phase 1 — Detecting the cycle: initialize tortoise (slow) and hare (fast). Move the tortoise by one step and the hare by two steps. If there’s a cycle (which there will be due to the duplicate), the tortoise and hare will eventually meet.
  2. Phase 2 — Finding the entrance to the cycle (the duplicate): once they meet, reset one pointer to the beginning of the array and keep the other pointer where they met. Move both pointers one step at a time. The point where they meet again is the start of the cycle, which is the duplicate number.
class Solution {
    public int findDuplicate(int[] nums) {
        // Phase 1: Detect cycle using two pointers (Tortoise and Hare)
        int slow = nums[0];  // Tortoise
        int fast = nums[0];  // Hare


        // Move the pointers until they meet
        do {
            slow = nums[slow];        // Move slow by one step
            fast = nums[nums[fast]];  // Move fast by two steps
        } while (slow != fast);       // Keep going until they meet


        // Phase 2: Find the entrance to the cycle (duplicate)
        slow = nums[0];  // Reset slow to the beginning of the array
        while (slow != fast) {  // Move both pointers one step at a time
            slow = nums[slow];
            fast = nums[fast];
        }


        return slow;  // The duplicate number
    }
}

For an input array like nums = [1, 3, 4, 2, 2], the cycle starts at index 2, and the number 2 is the duplicate. Time: O(n). Space: O(1), just the two pointers.