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). There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

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 algorithm leverages the fact that the duplicate number creates a cycle in the array when treated as a linked list.

1. Treat the array as a linked list: Each number nums[i] represents an index in the array. We can imagine each element pointing to the element at the index specified by its value (i.e., nums[i] points to nums[nums[i]]).

2. Detect the cycle (Tortoise and Hare): We use two pointers, a "slow" pointer (tortoise) and a "fast" pointer (hare). The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there's a cycle, they will eventually meet.

3. Find the cycle's entrance: Once the slow and fast pointers meet, reset the slow pointer to the beginning of the array. Now, move both pointers one step at a time. The point where they meet again is the entrance to the cycle, which represents the duplicate number.

Code (C#)

using System;

public class Solution {
    public int FindDuplicate(int[] nums) {
        // Floyd's Tortoise and Hare algorithm
        int slow = nums[0];
        int fast = nums[0];

        // Find the intersection point of the two pointers
        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 a few times.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store the slow and fast pointers. It does not modify the input array.