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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Duplicate Number

Number: 287

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Bloomberg, Citadel, TikTok, Anduril, Meta, Oracle, Nvidia, IBM, Adobe, Apple, Yahoo, Goldman Sachs, Zoho, Uber, PhonePe

Problem Description

Given an array of n+1 integers where each integer is in the range [1, n] inclusive, there is only one repeated number present in the array. The goal is to find and return this duplicate number without modifying the array and using only constant extra space.

Key Insights

  • Since there are n+1 elements with values only from 1 to n, by the pigeonhole principle at least one number must be repeated.
  • The problem can be approached by mapping the array values to indices, forming a cycle structure.
  • Floyd’s Tortoise and Hare algorithm (cycle detection) can be applied to find the duplicate number in linear time and constant space.
  • There is no need for extra data structures like hash sets or alterations to the original array, satisfying the space and array-modification constraints.

Space and Time Complexity

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

Solution

The solution leverages Floyd's Tortoise and Hare cycle detection algorithm. Think of each array element as a pointer to another index, forming a linked list with a cycle (the duplicate number creates the cycle). The algorithm works in two phases:

  1. Detect a meeting point within the cycle by having two pointers (tortoise and hare) move at different speeds.
  2. Find the cycle entrance by resetting one pointer to the start and moving both pointers at the same speed. The meeting point reveals the duplicate number.

This approach provides an elegant solution that satisfies both linear runtime and constant space requirements.

Code Solutions

# Function to find the duplicate number using Floyd's Tortoise and Hare algorithm.
def findDuplicate(nums):
    # Phase 1: Find the intersection point inside the cycle.
    tortoise = nums[0]  # Initialize tortoise pointer.
    hare = nums[0]      # Initialize hare pointer.
    while True:
        tortoise = nums[tortoise]         # Move tortoise one step.
        hare = nums[nums[hare]]           # Move hare two steps.
        if tortoise == hare:              # If pointers meet, cycle is detected.
            break

    # Phase 2: Find the entrance to the cycle.
    pointer = nums[0]  # Initialize a new pointer from the start.
    while pointer != tortoise:
        pointer = nums[pointer]         # Move pointer one step.
        tortoise = nums[tortoise]       # Move tortoise one step.
    return pointer  # The duplicate number.

# Example usage:
if __name__ == "__main__":
    sample = [1, 3, 4, 2, 2]
    print(findDuplicate(sample))  # Expected output: 2
← Back to All Questions