We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Duplicate Number

Difficulty: Medium

Problem Description

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.

Key Insights

  • The array contains n + 1 integers, which guarantees that at least one number must be duplicated due to the pigeonhole principle.
  • The integers are within the range [1, n], which allows for utilizing the values of the array as indices.
  • A two-pointer approach can be employed to detect the cycle formed by the duplicate number.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use the Floyd's Tortoise and Hare (Cycle Detection) algorithm. This approach is based on the idea that the duplicate number will create a cycle in the array when viewed as a linked list where each value points to the index of the next number. We will use two pointers (slow and fast) to detect this cycle.

  1. Initialize two pointers, slow and fast. The slow pointer moves one step at a time while the fast pointer moves two steps at a time.
  2. They will eventually meet inside the cycle.
  3. Once a cycle is detected, we can find the entry point of the cycle, which corresponds to the duplicate number.

Code Solutions

def findDuplicate(nums):
    # Initialize the two pointers
    slow = nums[0]
    fast = nums[0]
    
    # Phase 1: Finding the intersection point
    while True:
        slow = nums[slow]  # Move slow by 1 step
        fast = nums[nums[fast]]  # Move fast by 2 steps
        if slow == fast:
            break  # Cycle detected
    
    # Phase 2: Find the entrance to the cycle
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]  # Move slow by 1 step
        fast = nums[fast]  # Move fast by 1 step
    
    return slow  # The duplicate number
← Back to All Questions