Hash Map Example: Finding the Missing Seat Number With No Map at All

Seat numbers 1 to n with one missing and one doubled: each number's own position is its slot, so the array is its own hash map.

When every value lies in 1 to n, the array can be its own hash map: value v has a home slot at index v − 1, so no separate map is needed. A theatre row has seats numbered 1 to 5, and the five tickets sold read 3 1 5 3 2, so one seat number was printed twice and one never. A map of counts finds both in O(n) extra space. Cyclic sort, a pass that swaps each value into its home slot, finds them in O(n) time with O(1) extra space.

Which seat number is missing, and which is doubled?

Seat 4 is missing and seat 3 is doubled. The trace reaches the same answer without counting anything.

The rule at index i: if the value there, v, is not home and its home slot does not already hold a v, swap the two. Otherwise move i on. Every swap sends one value home for good, so there are at most n swaps, and i moves on n times: O(n) in all, though the loop looks as if it could run longer.

Cyclic sort on the tickets 3 1 5 3 2

Input3 1 5 3 2, seat numbers 1 to 5 at indices 0 to 4

Value 3 at index 0
1. 3i
2. 1
3. 5
4. 3
5. 2
3 belongs at index 2, which holds 5: swap them.
Value 5 at index 0
1. 5i
2. 1
3. 3
4. 3
5. 2
5 belongs at index 4, which holds 2: swap them.
Value 2 at index 0
1. 2i
2. 1
3. 3
4. 3
5. 5
2 belongs at index 1, which holds 1: swap them.
Value 1 at index 0
1. 1i
2. 2
3. 3
4. 3
5. 5
1 is home, so i moves on, and 2 and 3 are home as well.
Value 3 at index 3
1. 1
2. 2
3. 3
4. 3i
5. 5
3 belongs at index 2, which already holds a 3: this one is the copy, so i moves on. 5 is home.

ResultIndex 3 holds 3 instead of 4: seat 4 is missing and seat 3 is doubled

After the pass every value that can be home is home, so the first index whose value is not its own number names both answers: index 3 should hold 4 and holds the spare 3. The listing prints the array after each swap, line for line with the frames, and runs one edge case where the missing number is 1.

seat_numbers.pypy

def missing_and_doubled(seats: list[int]) -> tuple[int, int]:
    seats = list(seats)
    i = 0
    while i < len(seats):
        home = seats[i] - 1
        if seats[home] != seats[i]:
            seats[i], seats[home] = seats[home], seats[i]
            print("swap:", *seats)
        else:
            i += 1
    for index, seat in enumerate(seats):
        if seat != index + 1:
            return index + 1, seat
    raise ValueError("no seat is missing")


for seats in ([3, 1, 5, 3, 2], [2, 2]):
    missing, doubled = missing_and_doubled(seats)
    print(*seats, f"-> missing {missing}, doubled {doubled}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

swap: 5 1 3 3 2
swap: 2 1 3 3 5
swap: 1 2 3 3 5
3 1 5 3 2 -> missing 4, doubled 3
2 2 -> missing 1, doubled 2

Cyclic sort rearranges the array it is given, so the listing copies it first with list(seats), which brings the O(n) space back; when the caller allows the array to be changed, the copy can go. The cue that allows the pattern is a range of values tied to the length, 1 to n or 0 to n − 1. Seat numbers up to a thousand in a row of five tickets have no slot to go home to, and a map of counts is the answer there.

Hash Tables

← → move through sections and cards