Seat Reservation Manager: Min-Heap Design Pattern

Seat Reservation Manager is LeetCode 1845. You need to design a class that manages n seats numbered 1 to n. It supports two operations: reserve() returns the smallest unreserved seat and marks it as taken, and unreserve(seatNumber) frees a previously reserved seat.

Why this problem matters

This problem teaches a fundamental design pattern: using a min-heap to always retrieve the smallest available element from a dynamic set. You see this pattern everywhere. Job schedulers pick the lowest-priority task. Memory allocators grab the first free block. Connection pools hand out the lowest-numbered idle connection.

The core challenge is that elements leave the set (via reserve) and come back (via unreserve), and you need to handle both operations efficiently. A sorted list would give you O(n) insertions. A min-heap gives you O(log n) for both operations.

The key insight

If you store all available seats in a min-heap, reserve() is just a heappop (which always returns the minimum), and unreserve() is a heappush. The heap maintains the ordering for you. You never need to scan through the seats or sort anything manually.

The heap property guarantees that the root is always the smallest element. That is exactly the invariant this problem needs: "give me the smallest available seat."

The solution

import heapq

class SeatManager:
    def __init__(self, n: int):
        self.heap = list(range(1, n + 1))

    def reserve(self) -> int:
        return heapq.heappop(self.heap)

    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.heap, seatNumber)

The constructor initializes the heap with seats 1 through n. Since list(range(1, n + 1)) is already sorted in ascending order, it is a valid min-heap without needing to call heapify. The reserve method pops the root (smallest seat), and unreserve pushes the freed seat back in.

That is the entire solution. Three methods, four lines of logic.

Visual walkthrough

Let's trace through a sequence of operations on a SeatManager with 5 seats. Watch how the heap reorganizes itself after each reserve and unreserve call.

Notice how unreserving seat 2 in step 4 pushes it back into the heap, and the very next reserve() call in step 5 correctly returns seat 2 because it is now the smallest available seat. The heap handles all of this ordering automatically.

Complexity analysis

Time: The constructor creates a list of n elements, which is O(n). Each reserve and unreserve call performs one heap operation, which is O(log n) because the heap has at most n elements.

Space: The heap stores at most n seat numbers, so space is O(n).

The building blocks

1. Min-heap for dynamic minimum retrieval

The core building block here is using a min-heap when you need to repeatedly extract the minimum element from a changing collection. This is the same pattern you see in Dijkstra's algorithm, task scheduling, and merge-k-sorted-lists problems.

import heapq

heap = [1, 2, 3, 4, 5]
smallest = heapq.heappop(heap)
heapq.heappush(heap, 2)

The heap gives you O(log n) insert and O(log n) extract-min. No other data structure matches this combination for dynamic sets where you need the minimum.

2. Lazy initialization vs eager initialization

In this problem, we eagerly fill the heap with all n seats upfront. An alternative is lazy initialization: start with a counter, and only use the heap for unreserved seats that were returned out of order.

import heapq

class SeatManager:
    def __init__(self, n: int):
        self.heap = []
        self.next_seat = 1

    def reserve(self) -> int:
        if self.heap:
            return heapq.heappop(self.heap)
        seat = self.next_seat
        self.next_seat += 1
        return seat

    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.heap, seatNumber)

This avoids the O(n) upfront cost and reduces memory when only a few seats are ever reserved. Both approaches are valid, but the eager version is simpler and the one interviewers typically expect.

Edge cases

• Reserve all seats, then unreserve one. After reserving all n seats, the heap is empty. Unreserving seat k pushes it back, and the next reserve returns k.
• Unreserve and re-reserve the same seat repeatedly. Each unreserve pushes the seat back, and each reserve pops it. The heap handles this correctly with no special logic.
• n = 1. A single seat. Reserve returns 1, unreserve puts it back. The heap works fine with one element.
• Unreserve seats in reverse order. If you unreserve seat 5, then 4, then 3, the heap reorders them so the next reserve returns 3. The heap property guarantees this.

From understanding to recall

This problem looks almost too simple once you see the heap-based solution. And that is exactly the trap. A month from now, will you remember to use range(1, n + 1) instead of range(n)? Will you remember that heappop returns the smallest element, not the largest? Will you remember that a sorted list is already a valid min-heap in Python?

These are small details, but they matter under interview pressure. Spaced repetition locks them in. You type the three-method class from scratch, and the system schedules your next review right before you would forget. After a few reps, the heap-based design class becomes muscle memory.

CodeBricks breaks this solution into its building blocks: the heap initialization, the pop-for-reserve pattern, and the push-for-unreserve pattern. Each piece gets drilled on its own schedule so the full solution comes together naturally.

Related posts

• Top K Frequent Elements - Uses heaps to maintain a bounded set of most-frequent items
• Kth Largest Element in an Array - Heap-based selection from a dynamic collection
• Find Median from Data Stream - Two heaps maintaining a running median

---

Design problems with heaps are a recurring interview theme. The pattern is always the same: identify the dynamic set, choose min-heap or max-heap based on what you need to extract, and let the heap handle the ordering.