Find the Duplicate Number

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

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 using only constant extra space.

Examples:

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

Output: 2

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

Output: 3

Input: nums = [1,1]

Output: 1

Constraints

1 <= n <= 10⁵
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.

Editorial

Intuition:

Treat the array as a linked list where each index points to the value at that index. The duplicate number creates a cycle. The entry point of the cycle is the duplicate. Using Floyd's Tortoise and Hare algorithm we can detect the cycle and find its entrance without extra space or modifying the array.

Approach:

Initialize two pointers, slow and fast, both starting at nums[0].
Move slow one step (slow = nums[slow]) and fast two steps (fast = nums[nums[fast]]) until they meet. This meeting point lies inside the cycle.
Reset slow to nums[0]. Then advance both pointers one step at a time. The node where they meet again is the duplicate number (the cycle's entrance).

#include <vector>
using namespace std;
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);
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}
class Solution:
    def find_duplicate(self, nums):
        slow = nums[0]
        fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow
class Solution {
    findDuplicate(nums) {
        let slow = nums[0];
        let fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow !== fast);
        slow = nums[0];
        while (slow !== fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

Complexity Analysis:

Time Complexity: O(n), where n is the number of elements (excluding the extra one). The two-pointer algorithm traverses the array a constant number of times.

Space Complexity: O(1), only a few integer variables are used regardless of input size.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories