LeetCode 287 · Linked List

Find the Duplicate Number, explained with a picture

Boxes with notes pointing to other boxes.

MediumLinked List
▶ Watch it step by step

The problem

A list of n + 1 numbers contains only values from 1 to n, so at least one value repeats. Find the repeated number without changing the list and using only constant extra space.

Input:  [1, 3, 4, 2, 2]
Output: 2

Picture it

Picture numbered boxes 0 … n. Inside each box is a note saying which box to visit next (the value at that position). Following notes from box 0 forms a path. Two boxes contain notes pointing to the same box (the duplicate), so the path must loop, and the loop starts exactly at the duplicate. We find that loop entrance with the tortoise and hare.

How to recognise it

  • An array of length n + 1 holds values from 1 to n, so by the pigeonhole principle (more items than boxes) some value repeats.
  • You may not modify the array and may use only O(1) extra space. That rules out sorting, a set, and marking seen values by flipping signs.
  • Every value is a valid index, so you can read the array as "from index i, go to index nums[i]". That turns the array into a linked list hidden inside an array.
  • "Each position has exactly one next position, find where the walk loops" is the setting for Floyd's cycle detection (fast and slow pointers).
  • n goes up to 10^5, so comparing every pair is too slow.

Start with brute force

Compare every pair of positions and return the first value that appears twice.

def find_duplicate_brute(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return nums[i]

It respects both rules (no changes, O(1) space), but time is O(n²). For n = 10^5 that is about 5 × 10^9 comparisons. Sorting a copy (O(n log n)) or a set (O(n)) is fast but uses O(n) extra space.

From brute force to the idea

  1. Read values as links. Index i links to index nums[i]. Every index has exactly one outgoing link, and every link lands inside the array.
  2. A walk must loop. Start at index 0 and keep following links. There are only n + 1 indices, so some index is eventually visited twice, and from then on the walk goes round a cycle.
  3. The loop's entrance is the duplicate. No value is 0, so nothing links back to index 0: it lies on the "tail" leading into the cycle. The index where the tail joins the cycle has two incoming links, one from the tail and one from inside the cycle. Two links into the same index means two positions hold that same value.
  4. Phase 1: detect the cycle. slow takes one link per step and fast two (nums[nums[fast]]). Inside the cycle fast gains one step per round, so they meet.
  5. Phase 2: find the entrance. Put slow back at 0 and move both one link per step. The distance from 0 to the entrance equals the distance from the meeting point to the entrance (plus whole laps), so they meet exactly at the entrance.

This is the key idea: treat nums[i] as a next pointer, then the duplicate is where the cycle begins.

The key idea

Treat values as “next” pointers; the duplicate is the start of a cycle. Floyd’s algorithm finds it in O(n) time, O(1) space.

Python solution

def find_duplicate(nums):            # box i holds a note: "go to box nums[i]"
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = 0
    while slow != fast:
        slow, fast = nums[slow], nums[fast]
    return slow                         # two notes point here: the duplicate

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): every pair of positions is comparedO(1): two indices
Floyd's cycle detection (shown code)O(n): each phase takes at most a few multiples of n stepsO(1): two indices, the array is only read

Edge cases

  • Smallest input ([1, 1]): both pointers go to index 1, which links to itself, and the code returns 1.
  • Value repeated many times ([2, 2, 2, 2, 2]): returns 2. The proof only needs the entrance to have two incoming links; more is fine.
  • Duplicate at the start ([3, 1, 3, 4, 2]): returns 3.
  • Cycles that do not contain the duplicate: values that form their own loop (in [2, 1, 2], index 1 links to itself) are never reached from index 0, which is why the walk must start there.
  • Input is not modified: the shown code only reads nums.
  • Values outside 1 to n: the problem forbids them. A 0 would break the "nothing links to index 0" argument, and a value above n can raise IndexError.

Common mistakes

  • Returning the first meeting point. It is somewhere in the cycle, not necessarily its entrance: for [1, 3, 4, 2, 2] it is 4, not 2.
  • Starting the walk at any index other than 0. A start inside another loop finds the wrong cycle.
  • Moving fast two steps in phase 2. Both pointers must move one step at a time to meet at the entrance.
  • Sorting the input or marking visited values with minus signs, which breaks the "do not modify" rule.
Your turn: happy numbers

Start with a positive number and repeatedly replace it with the sum of the squares of its digits. The number is "happy" if this reaches 1 (19 → 82 → 68 → 100 → 1). Otherwise it loops forever without reaching 1. Decide whether n is happy using O(1) extra memory. Describe your approach, then write it if you like.

Compare with our answer

Each number has exactly one next number, so this is again a walk along hidden links that must either reach 1 (which maps to itself) or loop. Run Floyd's fast and slow walk and stop when fast reaches 1 or the two meet.

def is_happy(n):
    def step(x):
        return sum(int(d) ** 2 for d in str(x))
    slow, fast = n, step(n)
    while fast != 1 and slow != fast:
        slow, fast = step(slow), step(step(fast))
    return fast == 1

is_happy(19) is True and is_happy(2) is False. The numbers quickly drop below a few hundred, so each call takes only a small number of steps. Space O(1).

A strong answer mentions: seeing the sequence as a linked list, why it must reach 1 or cycle, Floyd's meeting test instead of a set, and that 1 is a fixed point.

Check what stuck

1. A read-only table has n + 1 entries, each holding the index (1 to n) of the next entry to visit. Starting at entry 0, find the first entry visited twice, using O(1) memory. Which approach fits best?

2. Why must the shown code start both walks at index 0?

3. A learner skips phase 2 and returns the value where slow and fast first meet. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.