Algorithm Day101 - Find the Duplicate Number

🧩 Problem

LeetCode 287 - Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is only one repeated number but it could be repeated more than once.
Return the duplicate number. You must solve the problem without modifying the array and use only constant extra space (O(1) space).

Example:

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

---

💡 Idea

Treat the array as a linked list where the value at index i points to nums[i]. Because numbers are in [1, n], this mapping creates a cycle due to the duplicate. We can use Floyd’s Tortoise and Hare (cycle detection) algorithm to find the entrance to the cycle, which corresponds to the duplicate number.

Steps (Floyd’s algorithm):

1. Use two pointers tortoise and hare; move tortoise by one step and hare by two steps until they meet.
2. Reset one pointer to the start (index 0) and move both one step at a time; the meeting point is the duplicate (cycle start).

This approach does not modify the input and uses O(1) extra space.

---

🔢 Java Code (Floyd’s Tortoise and Hare)

class Solution {
    public int findDuplicate(int[] nums) {
        // Phase 1: find intersection point of two runners
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);
        
        // Phase 2: find entrance to the cycle
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }
        return hare;
    }
}

Alternative: Binary Search on Value (O(n log n), O(1) space)

Binary search on the value range [1, n]: count how many numbers <= mid. If count > mid, duplicate lies in left half; otherwise right half. This doesn’t modify the array and uses O(1) space but costs O(n log n) time.

---

⏱ Complexity Analysis

• Floyd’s algorithm:

  • Time: O(n)
  • Space: O(1)

• Binary search on value:

  • Time: O(n log n)
  • Space: O(1)

---

✍️ Summary

• Model the array as a functional graph and use cycle detection to locate the duplicate’s value.
• Floyd’s Tortoise and Hare gives O(n) time with constant space and doesn’t mutate the array — ideal for this problem.