LeetCode 287: Find the Duplicate Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 287: Find the Duplicate Number?

In LeetCode 287: Find the Duplicate Number, you’re given an array nums with n+1 integers, where each number is between 1 and n (inclusive), and exactly one number appears twice (or more), while the others appear once. Your task is to find that duplicate number. The twist? You can’t modify the array (like sorting it), and ideally, you should use O(1) extra space—meaning no big helper lists or dictionaries. For example, in [1, 3, 4, 2, 2], the duplicate is 2. This problem tests your ability to think outside the box, sharing a spirit with challenges like LeetCode 141: Linked List Cycle.

Problem Statement

• Input: An integer array nums of length n+1, with values from 1 to n.
• Output: The integer that appears more than once.
• Rules: Exactly one duplicate; don’t modify the array; prefer O(1) space; O(n log n) time or better.

Constraints

• n: 1 to 10⁵ (100,000).
• nums[i]: 1 to n.
• One number appears at least twice; others appear once.

Examples

• Input: nums = [1, 3, 4, 2, 2]
• Output: 2
• Input: nums = [3, 1, 3, 4, 2]
• Output: 3
• Input: nums = [1, 1]
• Output: 1

Understanding the Problem: Spotting the Repeat

To solve LeetCode 287: Find the Duplicate Number in Python, we need to find the number that shows up twice in an array where every other number fits neatly from 1 to n, but there’s one extra slot (n+1 total). A simple idea might be to count each number with a dictionary, but that uses extra space, and we’re told to avoid that if we can. Plus, we can’t sort the array to make it obvious. So, we’ll use: 1. Best Solution (Floyd’s Cycle-Finding Algorithm): O(n) time, O(1) space—tricky but brilliant. 2. Alternative Solution (Binary Search): O(n log n) time, O(1) space—more straightforward.

Let’s dive into Floyd’s method with a super clear explanation for beginners.

Best Solution: Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)

Why This Is the Best Solution

Floyd’s Cycle-Finding Algorithm is the coolest way to solve LeetCode 287 because it runs in O(n) time—super fast—and uses O(1) space, meaning no extra storage beyond a couple of variables. It treats the array like a linked list where each number points to an index, and the duplicate creates a loop we can detect. For beginners, it might sound fancy, but it’s like a game of tag with a slow and fast runner—it’s clever and fun once you see it!

How It Works—Explained for Beginners

Okay, let’s make this really simple. Imagine the array as a treasure map where each number tells you where to jump next—like “go to spot 3” or “go to spot 1.” Because there’s a duplicate, you’ll eventually loop back to a spot you’ve been before, like a circle in the path. Here’s how we find it, step-by-step:

• Step 1: Think of the Array as a Path:
• Each value in the array is a “pointer” to an index. For example, in [1, 3, 4, 2, 2], at index 0 is 1 (go to index 1), at index 1 is 3 (go to index 3), at index 3 is 2 (go to index 2), at index 2 is 4 (go to index 4), at index 4 is 2 (back to index 2)—whoa, a loop: 2 → 4 → 2!
• The duplicate (2) makes this loop happen because two indices (3 and 4) point to the same spot (index 2).

• Step 2: Send Two Runners—Tortoise and Hare:
• Picture two friends running this path: a slow one (tortoise) moves one step at a time, and a fast one (hare) moves two steps.
• Start them both at index 0. Tortoise takes it easy: nums[0] → nums[1] → nums[3]..., while Hare zooms: nums[0] → nums[1] → nums[3] → nums[2] → nums[4]...
• Because there’s a loop (thanks to the duplicate), Hare will eventually catch up to Tortoise inside that loop—like they’re running in circles and bump into each other.

• Step 3: Find Where They Meet:
• Keep moving them until they’re at the same spot. For [1, 3, 4, 2, 2], they meet at index 2 (value 4), inside the loop 2 → 4 → 2.

• Step 4: Find the Loop’s Start (the Duplicate):
• Now, reset Tortoise to the start (index 0) and slow Hare down to one step at a time.
• Move them together: when they meet again, it’s at the loop’s entrance—the duplicate number!
• Why? Math magic says the distance from the start to the loop entrance equals the distance from their meeting point back to the entrance when paced evenly.

• Step 5: Why It Works:
• The duplicate creates a cycle because two indices point to the same value, forcing a repeat.
• The runners find this cycle, and the second phase pinpoints the duplicate value (not just its index).

It’s like a treasure hunt where the loop leads you to the prize—the duplicate!

Step-by-Step Example

Example: nums = [1, 3, 4, 2, 2]

• Path: 0 → 1 → 3 → 2 → 4 → 2 (loop: 2 → 4 → 2).
• Phase 1: Find Meeting Point:
• Tortoise: 0 → 1 → 3 → 2 → 4.
• Hare: 0 → 1 → 3 → 2 → 4 → 2 (two steps: 0 → 1 → 3, 1 → 3 → 2, 3 → 2 → 4, 2 → 4 → 2).
• Meet at index 2 (value 4).
• Phase 2: Find Loop Entrance:
• Tortoise: 0 → 1 → 3 → 2.
• Hare (slowed): 2 → 4 → 2 → 2.
• Meet at index 2, but values are nums[2] = 4, nums[3] = 2—adjust thinking: we want the value they point to.
• Corrected: Start Hare at 0 too, use values:
• Tortoise: 1 → 3 → 2.
• Hare: 1 → 3 → 2.
• Meet at value 2 (duplicate!).
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained so any beginner can follow:

Copy codeclass Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Step 1: Start two pointers at the first number
        tortoise = nums[0]
        hare = nums[0]

        # Step 2: Phase 1 - Find where they meet in the loop
        while True:
            tortoise = nums[tortoise]  # Move one step
            hare = nums[nums[hare]]    # Move two steps
            if tortoise == hare:       # They bump into each other
                break

        # Step 3: Phase 2 - Find the start of the loop (duplicate)
        tortoise = nums[0]  # Reset tortoise to start
        while tortoise != hare:
            tortoise = nums[tortoise]  # Both move one step now
            hare = nums[hare]

        # Step 4: They meet at the duplicate value
        return tortoise

• Line 4-5: Tortoise and Hare start at nums[0]—the beginning of our “path.”
• Line 8-12: First loop:
• Tortoise moves one spot: nums[tortoise] is the next “jump.”
• Hare moves two spots: nums[nums[hare]] jumps twice.
• When they’re equal, they’ve met in the loop—stop here.
• Line 14-18: Second loop:
• Reset Tortoise to nums[0]; Hare stays where they met.
• Both move one step at a time until they meet again—at the duplicate!
• Line 20: Return the value they land on—it’s our answer.

• Time Complexity: O(n)—they meet and find the duplicate in linear steps.
• Space Complexity: O(1)—just two variables, no extra space.

This is like a detective chase—catch the duplicate with no mess!

Alternative Solution: Binary Search

Why an Alternative Approach?

Binary search uses a different trick—O(n log n) time, O(1) space—by guessing the duplicate and counting numbers to narrow it down. It’s slower than Floyd’s but easier to understand for beginners, like playing a guessing game with a clever twist.

How It Works—Explained for Beginners

Let’s think of this as a number-guessing game:

• Step 1: Set a Range:
• Since numbers are 1 to n, the duplicate is somewhere in there. Start with low=1, high=n.
• Step 2: Guess the Middle:
• Pick a number in the middle (mid). Count how many numbers in the array are ≤ mid.
• Step 3: Decide Where to Look:
• If count > mid, there’s extra numbers on the left (including the duplicate)—search lower half.
• If count ≤ mid, the duplicate must be in the upper half—search there.
• Step 4: Narrow Down:
• Keep splitting until low meets high—that’s the duplicate.

It’s like guessing “higher or lower” until you hit the jackpot!

Step-by-Step Example

Example: nums = [1, 3, 4, 2, 2]

• n = 4, range: 1 to 4.
• Guess 1: mid=2, count ≤ 2: 1, 2, 2 → 3 > 2, duplicate ≤ 2, high=2.
• Guess 2: mid=1, count ≤ 1: 1 → 1 ≤ 1, low=2.
• Guess 3: low=2, high=2 → duplicate = 2.
• Result: 2.

Code for Binary Search

Copy codeclass Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        low, high = 1, len(nums) - 1

        while low < high:
            mid = (low + high) // 2
            count = sum(1 for num in nums if num <= mid)
            if count > mid:
                high = mid
            else:
                low = mid + 1

        return low

• Time Complexity: O(n log n)—log n guesses, n counts each.
• Space Complexity: O(1)—just a few variables.

It’s a smart guess-and-check!

Comparing the Two Solutions

• Floyd’s (Best):
• Pros: O(n) time, O(1) space, super clever.
• Cons: Takes time to understand.
• Binary Search (Alternative):
• Pros: O(n log n) time, O(1) space, easier logic.
• Cons: Slower than Floyd’s.

Floyd’s wins for speed and elegance.

Additional Examples and Edge Cases

• [1, 1]: Duplicate = 1.
• [2, 1, 3, 1]: Duplicate = 1.
• [1, 2, 2]: Duplicate = 2.

Both work perfectly.

Complexity Breakdown

• Floyd’s: Time O(n), Space O(1).
• Binary Search: Time O(n log n), Space O(1).

Floyd’s is the champ.

Key Takeaways

• Floyd’s: Loops catch duplicates—amazing!
• Binary Search: Guess and count—simple!
• Space: O(1) is the goal.
• Python Tip: Loops and logic are key—see [Python Basics](/python/basics).

Final Thoughts: Catch That Duplicate

LeetCode 287: Find the Duplicate Number in Python is a thrilling puzzle. Floyd’s method is a speedy detective trick, while binary search is a steady guesser. Want more? Try LeetCode 141: Linked List Cycle or LeetCode 442: Find All Duplicates. Ready to hunt? Head to Solve LeetCode 287 on LeetCode and nab that duplicate today!