algoadvance

Leetcode 287. Find the Duplicate Number

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 duplicate number in nums, return this duplicate number.

You must solve the problem without modifying the array nums and use only constant extra space.

Clarifying Questions

1. Can the given array contain more than one duplicate number?
   • No, the problem states there is exactly one duplicate number.
2. Is the input array guaranteed to have at least one duplicate number?
   • Yes, the problem guarantees that there is exactly one duplicate number.
3. Can the input array be empty or have less than two elements?
   • No, since the array contains n + 1 integers where each integer is in the range [1, n], the smallest array would have two elements (e.g., [1, 1]).
4. Do we need to handle the case where the input array is nullptr or contains invalid elements?
   • No, the input is guaranteed to be valid as per the problem statement.

Strategy

We will use Floyd’s Tortoise and Hare (Cycle Detection) algorithm to solve this problem in O(n) time complexity and O(1) space complexity. The idea is to interpret the array indices and values as nodes and their next pointers in a linked list and find the cycle.

• Phase 1: Detection of Cycle:
  • Use two pointers, slow and fast. Slow moves one step at a time while fast moves two steps at a time. If there is a cycle (i.e., a duplicate number), they will eventually meet.
• Phase 2: Finding the Entrance to the Cycle:
  • Once a cycle is detected, reset one pointer to the start of the array and move both pointers one step at a time. The point where they meet again will be the entrance to the cycle, which is the duplicate number.

Code

#include <vector>
#include <iostream>

class Solution {
public:
    int findDuplicate(std::vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];
        
        // Phase 1: Detecting the cycle
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // Phase 2: Finding the cycle entrance
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
};

int main() {
    Solution solution;
    std::vector<int> nums = {1, 3, 4, 2, 2};
    std::cout << "Duplicate number is: " << solution.findDuplicate(nums) << std::endl;  // Output: 2
    return 0;
}

Time Complexity

• Time Complexity: O(n), because in both the phases, each pointer traversal is O(n), hence the overall time complexity is linear.
• Space Complexity: O(1), as we only use a constant amount of extra space for the slow and fast pointers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?