Find the Duplicate Number — The Bunk Bed Mystery

Boss 8: The Bunk Bed Mystery

This boss doesn't look like it belongs in this dungeon. There's an array, some numbers, no ListNode anywhere. That's the point. The deepest test of whether you own a pattern is recognizing it out of costume, and this problem wears the best costume in the catalog.

It's also the Night Watchman's promised second act: not just detecting the loop, but finding its entrance.

The story

Summer camp, first night. The cabin has beds numbered 1 through n. The roster lists n+1 campers, each assigned a bed:

roster = [1, 3, 4, 2, 2]      (5 campers, beds 1..4)

Camper 0 → bed 1. Camper 1 → bed 3. Camper 2 → bed 4. Camper 3 → bed 2. Camper 4 → bed 2.

More campers than beds, so somebody's sharing, that's the pigeonhole principle wearing pajamas. Here beds 2 got assigned twice. The director wants the shared bed number, with rules that sound arbitrary until you meet the constraints they encode:

• The roster is laminated: read-only, no sorting, no crossing out.
• Your notebook is gone: no set of seen beds, O(1) memory only.
• Be quick about it: better than quadratic.

No sorting, no hash set, no nested loop. Every obvious tool, confiscated.

The problem, dressed up properly

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.

LeetCode 287, and those two constraints at the end are what promote it to this dungeon.

The naive attempts, each dying on a constraint

Sort and scan for neighbors: O(n log n), but sorting modifies the laminated roster. Dead.

Hash set of seen beds: O(n) time, but O(n) memory. The notebook is gone. Dead.

For each camper, scan for a twin: O(1) memory, read-only, and O(n²) time. The director retires before you finish. Dead.

Three corpses. The constraints have herded you, deliberately, toward something stranger.

The weapon: the roster is secretly a linked list

Here's the squint. Treat each roster entry as a node, and the value written there as a pointer: "entry i points to entry nums[i]".

Stand at entry 0. It says 1, walk to entry 1. It says 3, walk to entry 3. It says 2, walk to entry 2. It says 4, walk to entry 4. It says 2, walk to entry 2. It says 4...

0 → 1 → 3 → 2 → 4 → 2 → 4 → 2 → ...
              └───────┘
               the loop

You're the night watchman again. And the trail must loop: there are only n+1 entries, so any walk of n+2 steps repeats one, and every step out of a repeated entry repeats forever after.

Now the beautiful part, the reason this problem exists. Why does the loop start exactly at the duplicate? An entry is the loop's entrance if and only if two different trails lead into it, meaning two different entries point at it, meaning two campers wrote the same bed number. The duplicate value isn't just in the cycle, it is the cycle's front door. (And entry 0 can never be in the loop, since bed numbers run 1..n, nothing ever points back to 0. A guaranteed clean starting line.)

So the job is: find the entrance of a cycle. Floyd's algorithm has a second phase for exactly this.

Phase 1 — tortoise and hare, as in Boss 3, until they meet somewhere inside the loop.

Phase 2 — send a second tortoise from the start. Both tortoises now walk one step at a time. They meet exactly at the loop's entrance.

Why phase 2 works, in one paragraph: call the distance from start to entrance a, and say the meeting point sits b steps past the entrance inside a loop of length c. The hare walked exactly twice the tortoise's distance, so a + b + kc = 2(a + b) for some whole number of extra laps k, which rearranges to a = kc − b. Read that right side as directions: starting at the meeting point, walking a steps means walking −b (back to the entrance) plus whole laps, landing on the entrance. So the walker from the start and the walker from the meeting point, both taking exactly a steps, arrive at the entrance together. Neither knows what a is, and neither needs to: they just walk until they meet.

Watching it work

roster = [1, 3, 4, 2, 2]

phase 1 (slow = nums[slow], fast = nums[nums[fast]], both from 0):
tick   slow   fast
1      1      3
2      3      4
3      2      4
4      4      4      MEET inside the loop

phase 2 (walker from 0, walker from meeting point, both x1):
tick   walker1   walker2
0      0         4
1      1         2
2      3         4
3      2         2      MEET → duplicate is bed 2

Bed 2. Two campers, one mattress, mystery closed.

The code

def find_duplicate(nums: list[int]) -> int:
    # phase 1: find a meeting point inside the cycle
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
 
    # phase 2: walk two pointers at equal speed to the entrance
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Read it again slowly: the array is never written, and the extra memory is two integers. Both constraints, satisfied by an algorithm designed for a data structure this problem doesn't even admit to containing.

Gotchas

1. Phase 1's meeting point is not the answer. The runners meet somewhere in the loop, bed 4 in our trace, and the duplicate was bed 2. Submitting the phase-1 meeting point passes some inputs by luck and fails the rest. Both phases, always.

2. Starting phase 1 with a broken do-while. slow and fast both start at 0, so a while slow != fast loop exits instantly, before anyone moves. You need move-then-check semantics: while True with a break, or a do-while in languages that have one.

3. Binary-searching or bit-counting instead. Both exist (search on answer over bed numbers, O(n log n); bit-by-bit counting, O(32n)) and both respect the constraints. Fine answers! But if you're in this dungeon, the expected follow-up is "can you do O(n) with O(1) space?", and Floyd is the only resident of that box.

4. Assuming the duplicate appears exactly twice. The problem says one repeated number, but it may appear three or more times. Floyd doesn't care (more campers pointing at the same bed just means more trails into the same entrance), but solutions built on "sum minus expected sum" arithmetic die here. Beware the cute formula.

Complexity

Phase 1 is O(n) as argued in Boss 3, phase 2 walks at most the full trail once.

Time: O(n). Space: O(1). Roster unmarked, notebook unneeded.

Boss down. XP gained.

Bed 2's occupants get the spare cot from storage, and the director quietly fixes the roster for next summer.

What you walked away with:

• Values-as-indices means hidden linked list, the costume worth memorizing
• Pigeonhole guarantees the cycle; the duplicate is the entrance, because two entries point at it
• Floyd phase 2: equal-speed walkers from the start and the meeting point converge at the entrance, and a = kc − b is why
• Constraints are hints: read-only plus O(1) space is practically Floyd's calling card

Next up: Boss 9 — The Food Truck Fridge. A tiny fridge, relentless lunch rush, and one rule: when it's full, whatever's been ignored longest gets tossed. Every lookup and every restock must run in O(1), which takes a hash map and a doubly linked list holding hands. The dungeon's first real data-structure design fight, and a top-three interview question worldwide.