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(n^2).

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 solved efficiently using the Floyd's Tortoise and Hare algorithm (also known as cycle detection). The idea is to treat the array as a linked list where nums[i] points to the next node at index nums[i]. Since there are n+1 numbers in the range [1, n], there must be at least one duplicate. This duplicate creates a cycle in the linked list.

1. Cycle Detection: We use two pointers, slow and fast. slow moves one step at a time, and fast moves two steps at a time. If there's a cycle, they will eventually meet.

2. Finding the Cycle Start: Once the slow and fast pointers meet, reset slow to the beginning of the array (index 0). Keep fast where it is. Now, 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).

Code (C++)

#include <vector>

class Solution {
public:
    int findDuplicate(std::vector<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 start of 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 a constant number of times.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store the pointers.

This solution effectively leverages the properties of the input to find the duplicate in linear time and constant space, fulfilling all the constraints of the problem. The Floyd's Tortoise and Hare algorithm is a clever technique often used for cycle detection in various graph and linked list problems.