Find the Duplicate Number | LeetCode 287

In this blog, we will solve LeetCode Coding Problem “Find the Duplicate Number”. We will use tortoise and hare algorithm to solve this coding problem.

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.

Constraints

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Example

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

Output: 2

Solution

Since we are given an array of size n containing numbers ranging from 1 to n + 1, we’ll use the “tortoise and hare” algorithm to identify any duplicate numbers.

First, We will iterate through the array using two pointers, one moving at double the speed of the other. This strategy helps us detect any cycles within the array. Dry run of this step with given example is as follows.

We will backtrack to find the starting point of the cycle, which pinpoints the duplicate number in the array. Dry run of this step with given example is as follows.

C++ implementation of above solution is as follows.

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 Complexity

O(n) where n = number of elements in nums array.

Space Complexity

O(1) since we are not using any additional space.

Thanks for reading and have a nice day.