Daily LeetCode Problems: Problem 287. Find the Duplicate Number

Unraveling the Duplicate Dilemma: Solving LeetCode Problem 287

Introduction:

Welcome to another exciting journey into problem-solving! Today, we’re delving into problem 287 from LeetCode, titled “Find the Duplicate Number.” In this challenge, we’re presented with an array of integers and tasked with identifying the duplicated number. The catch? We must find the duplicate without altering the original array and using only a constant amount of extra space. Let’s dive into the problem statement, discuss an optimal approach, analyze the complexity, and present a step-by-step solution.

Problem Statement:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There's precisely one repeated number in nums. Our goal is to identify and return this duplicated number while adhering to the constraints of not modifying the array and utilizing only a constant amount of extra space.

Approach:

To address this problem effectively while abiding by the constraints, we’ll employ the concept of cycle detection in a linked list. The array can be treated as a sequence of indices, where each value corresponds to the next index. Since there’s only one repeated number, a cycle is formed in this sequence.

We’ll use Floyd’s Tortoise and Hare algorithm to detect this cycle. It works by having two pointers, one slow (tortoise) and one fast (hare). If there’s a cycle, these pointers will eventually meet.

Pseudocode:

def findDuplicate(nums):
    # Phase 1: Detect the intersection point of the two runners.
    tortoise = nums[0]
    hare = nums[0]

    # Keep advancing 'tortoise' by one step and 'hare' by two steps until they meet inside the loop.
    while True:
        tortoise = nums[tortoise]
        hare = nums[nums[hare]]

        if tortoise == hare:
            break

    # Phase 2: Find the "entrance" to the cycle.
    ptr1 = nums[0]
    ptr2 = tortoise

    # Keep advancing both pointers until they meet at the entrance of the cycle.
    while ptr1 != ptr2:
        ptr1 = nums[ptr1]
        ptr2 = nums[ptr2]

    return ptr1

Complexity Analysis:

Let’s analyze the complexity of our solution:

• Time complexity: O(n) — The cycle detection takes O(n) time.
• Space complexity: O(1) — We only use a constant amount of extra space.

Step-by-Step Solution:

1. Initialize two pointers, tortoise and hare, both starting at the first index of the array.
2. Move the tortoise one step forward and the hare two steps forward until they meet at some index within the cycle.
3. Once they meet, reset one pointer to the beginning and move both pointers one step at a time until they meet again. This meeting point is the start of the cycle.
4. Return this meeting point, which corresponds to the duplicated number.

Full Solution

Python

class Solution:
  def findDuplicate(self, nums: List[int]) -> int:
    slow = nums[nums[0]]
    fast = nums[nums[nums[0]]]

    while slow != fast:
      slow = nums[slow]
      fast = nums[nums[fast]]

    slow = nums[0]

    while slow != fast:
      slow = nums[slow]
      fast = nums[fast]

    return slow

Java

class Solution {
  public int findDuplicate(int[] nums) {
    int slow = nums[nums[0]];
    int fast = nums[nums[nums[0]]];

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

    slow = nums[0];

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

    return slow;
  }
}

C++

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

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

    slow = nums[0];

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

    return slow;
  }
};

Conclusion:

In this article, we delved into problem 287, “Find the Duplicate Number,” and successfully tackled it using the Floyd’s Tortoise and Hare algorithm. By understanding the problem, devising an effective approach, and implementing the solution, we were able to identify the duplicated number without modifying the array and using only a constant amount of extra space. Happy problem-solving!