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, but it could be repeated more than once. Return the duplicate number.

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

Clarifying Questions

  1. What is the range of values for n?
    • Typically, 1 <= n <= 10^5.
  2. Can the input array contain multiple duplicate numbers, or is there always exactly one number that repeats?
    • There is always exactly one number that repeats, but it could appear more than once.
  3. Do we need to handle edge cases like an empty array or an array where no numbers are repeated?
    • No, the problem guarantees that there will be a duplicate, and the array is of size n+1 where 1 <= n <= 10^5.

Strategy

We will use Floyd’s Tortoise and Hare (Cycle Detection) Algorithm to solve this problem. This algorithm leverages the idea that if you treat the array as a linked list where the value at each index points to the next index, the duplicate number will form a cycle.

  1. Phase 1: Finding the Intersection Point
    • Initialize two pointers, both starting at the beginning of the array.
      • The “tortoise” moves one step at a time.
      • The “hare” moves two steps at a time.
    • Move both pointers until they meet. This meeting point is guaranteed to be within the cycle.
  2. Phase 2: Finding the Cycle Entrance
    • To find the start of the cycle, initialize another pointer from the beginning of the array and keep the tortoise at the meeting point.
    • Move both pointers one step at a time until they meet. The meeting point now will be the duplicate number.

Code

Here’s the implementation of the strategy in Java:

public class Solution {
    public int findDuplicate(int[] nums) {
        // Phase 1: Finding the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];

        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Phase 2: Finding the entrance to the cycle.
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }

        return hare;
    }
}

Time Complexity

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