Find the Duplicate Number medium

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] (inclusive), prove that at least one duplicate number must exist. Find the duplicate number.

You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array; it could be repeated more than once.

Example 1:

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

Example 2:

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

Steps and Explanation

This problem can be efficiently solved using Floyd's Tortoise and Hare algorithm (also known as the cycle detection algorithm). The idea is to treat the array as a linked list where each element nums[i] points to the element at index nums[i]. The presence of a duplicate number creates a cycle in this linked list.

1. Finding the Cycle: The Tortoise and Hare algorithm uses two pointers, slow and fast. slow moves one step at a time, while fast moves two steps at a time. If there's a cycle, they will eventually meet.

2. Finding the Cycle Entrance: Once the slow and fast pointers meet, reset slow to the beginning of the array. Move both slow and fast one step at a time. The point where they meet again is the entrance to the cycle (which represents the duplicate number).

Code (Java)

class Solution {
    public int findDuplicate(int[] nums) {
        // Find the intersection point of the two runners.
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Find the "entrance" to the cycle.
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

Complexity Analysis

• Time Complexity: O(n). The algorithm iterates through the array at most twice.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space (for the slow and fast pointers).

This solution elegantly addresses the constraints of the problem by utilizing a well-known algorithm for cycle detection in a constant space and linear time. It avoids modifying the input array and meets all the specified requirements.