DAY 108 - Find Duplicate

Hey Guys! Welcome back to another 100DaysOf Code day.
We are going to do another daily leetcode question today.

Question: Find Duplicate

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.

Examples:

Example 1:

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

Example 2:

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

Understanding the Problem

Before diving into the code, let's break down the problem and understand what's expected:

• You are given an array nums containing n + 1 integers.

• Each integer in the array is between 1 and n (inclusive).

• There is only one integer that appears more than once in the array.

• Your task is to find and return this duplicate integer.

The Approach

To efficiently solve this problem, we can use the Floyd's Tortoise and Hare algorithm, which is also known as the cycle detection algorithm. Here's how it works:

1. We initialize two pointers, slow and fast, both initially pointing to the first element of the array.

2. We use a loop to advance these pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. This simulates two runners racing along the array.

3. If there is a duplicate number in the array, the pointers will eventually enter a cycle, meaning they will meet at the same position.

4. Once the pointers meet inside the cycle, we reset one of the pointers, let's say fast, to the beginning of the array, while keeping the other pointer (slow) inside the cycle.

5. We then advance both pointers at the same rate (one step at a time). When they meet again, it will be at the entrance of the cycle.

6. The position where the two pointers meet for the second time is the location of the duplicate number.

7. We return this duplicate number as our result.

Code:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];

        } while(slow != fast);

        fast = nums[0];

        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
    return slow;
    }
};

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

• Time Complexity: The Floyd's Tortoise and Hare algorithm runs in O(N) time, where N is the length of the array. This is because both pointers move through the array at different speeds, but the fast pointer covers the cycle at most twice.

• Space Complexity: We use only a constant amount of extra space to store the slow and fast pointers. Therefore, the space complexity is O(1).