Find the duplicate in an array of N+1 integers

Problem Overview

The problem "Find the Duplicate Number" is a popular question on LeetCode that falls under the topic of Arrays. The challenge is to identify a duplicate number in an array where numbers appear more than once. The constraints on the problem state that only one number is repeated more than once and that the numbers are within a specific range, which adds an additional layer to the problem-solving strategy.

Understanding the Problem

Problem Statement:

You are given an array of n + 1 integers where each integer is between 1 and n (inclusive). There is only one repeated number in the array, but it could be repeated more than once. You need to return this duplicate number.

Example:

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

Constraints:

• You must solve the problem using only constant extra space.
• The solution's runtime complexity must be less than O(n^2).

Key DSA Concepts and Theory

At its core, this problem involves the following key concepts:

1. Cycle Detection in Linked Lists:

   • This problem can be mapped to finding a cycle in a linked list-like structure. Using two-pointer technique (Floyd's Tortoise and Hare Algorithm) helps in detecting cycles and finding the entrance to the cycle, which corresponds to the duplicate number in this problem.

2. Binary Search on Answer:

   • Another approach is to treat this problem akin to finding the “smallest bad version” using binary search on possible values (from 1 to n).

3. Array as Hash Map:

   • Exploiting the properties of numbers and their indices to use the array itself as a hashmap (though not applicable here due to constraints).

Solution Approach

The most efficient way to solve this problem given the constraints is to apply Floyd's Tortoise and Hare algorithm. This method guarantees a solution with O(n) time complexity and O(1) space complexity, which meets the constraints perfectly.

Floyd's Tortoise and Hare (Cycle Detection)

This approach leverages the cycle detection technique used in linked lists but is uniquely adapted for arrays in this problem. The basic idea is to treat each number as a node in a linked list, where the next node is determined by the value it holds. The array thus forms a cycle due to the presence of a duplicate number.

Steps:

1. Initialization:

   • Create two pointers: tortoise and hare. Initialize both with the starting point (i.e., the first element of the array).

2. First Phase (Finding the intersection point):

   • Move tortoise one step at a time and hare two steps at a time.
   • Continue until they meet, which confirms the presence of a cycle.

3. Second Phase (Finding the entry point of the cycle):

   • Reset one pointer to the start of the array, then move both one step at a time.
   • The meeting point now is the duplicate number.

C++ Implementation:

#include <vector>
using namespace std;

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // Phase 1
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);
        
        // Phase 2
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }
        
        return hare;
    }
};

Java Implementation:

class Solution {
    public int findDuplicate(int[] nums) {
        // Phase 1
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Phase 2
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }
        
        return hare;
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(n). Both pointers move linearly, ensuring linear time complexity.
• Space Complexity: O(1). Apart from a few pointers, no additional space is used, adhering to the constant space requirement.

Common Mistakes to Avoid

1. Misunderstanding the Cycle Detection: It is crucial to recognize that the array’s values, treated as pointers to array indices, form a repeating cycle due to the duplicate.
2. Boundary Conditions: Ensure all edge cases and constraints specified are considered, especially the range and repetition of numbers within [1, n].

Similar Problems on LeetCode

1. Linked List Cycle - LeetCode 141
2. Linked List Cycle II - LeetCode 142

Additional Resources and References

1. Floyd's Cycle Detection Algorithm
2. Neetcode’s explanation video on "Find the Duplicate Number"
3. Detailed blog post on cycle detection in linked lists.

This article provides a concise yet comprehensive coverage of the problem, its constraints, and efficient methods to solve it using both understanding and practical implementation.