LeetCode 1845 - Seat Reservation Manager

LeetCode Problem 1845

Difficulty: 🟡 Medium
Topics: Design, Heap (Priority Queue)

Solution

Problem Understanding

The problem requires designing a system to manage seat reservations for n seats numbered from 1 to n. You need to implement a SeatManager class with two main operations: reserve and unreserve. The reserve operation must always allocate the smallest-numbered available seat, while unreserve releases a previously reserved seat so it becomes available again.

The input for initialization is a single integer n, specifying the total number of seats. Calls to reserve return an integer indicating the seat number allocated. Calls to unreserve take a seat number as input and free that seat. The constraints guarantee that each reserve call will find at least one available seat, and each unreserve call will reference a seat that is currently reserved.

Key considerations include efficiently tracking the lowest available seat and handling up to 10^5 operations. Naive approaches like scanning all seats for availability on every reserve would be too slow. The problem guarantees valid inputs, so we do not need to handle invalid seat numbers or over-reservation.

Important edge cases to consider are when all seats are reserved, when a seat is immediately unreserved after reservation, and when only one seat remains available.

Approaches

A brute-force approach is to maintain an array or list representing seat availability. For reserve, iterate through the list to find the first unreserved seat and mark it as reserved. For unreserve, mark the seat as available. While correct, this approach has O(n) time complexity per reserve, which is too slow for n and operation count up to 10^5.

The key insight for an optimal solution is to use a min-heap (priority queue). By keeping all unreserved seats in a min-heap, reserve can pop the smallest seat in O(log n) time, and unreserve can push a seat back into the heap in O(log n) time. This ensures we always get the minimum-numbered available seat efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per reserve	O(n)	Scans the seat array to find smallest available seat
Optimal	O(log n) per reserve/unreserve	O(n)	Uses min-heap to efficiently track available seats

Algorithm Walkthrough

1. Initialize a min-heap with all seat numbers from 1 to n. This represents all seats initially available.
2. When reserve is called, pop the smallest seat number from the heap and return it. This guarantees the smallest available seat is allocated.
3. When unreserve is called with seatNumber, push the seat back into the min-heap. This restores it as an available seat for future reserve operations.
4. The heap property ensures that the smallest element is always at the top, so the reserve operation always retrieves the correct seat efficiently.

Why it works: The heap invariant guarantees that the smallest-numbered available seat is always accessible in O(1) as the root, and the push/pop operations maintain the heap property. This ensures correctness and efficiency.

Python Solution

import heapq

class SeatManager:

    def __init__(self, n: int):
        self.available_seats = list(range(1, n + 1))
        heapq.heapify(self.available_seats)

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

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

In the Python implementation, the __init__ method creates a min-heap of all seat numbers. reserve pops the smallest element, and unreserve pushes a seat number back. The heapq module maintains the heap property automatically.

Go Solution

package main

import (
	"container/heap"
)

type SeatManager struct {
	minHeap *IntHeap
}

func Constructor(n int) SeatManager {
	h := &IntHeap{}
	for i := 1; i <= n; i++ {
		*h = append(*h, i)
	}
	heap.Init(h)
	return SeatManager{minHeap: h}
}

func (this *SeatManager) Reserve() int {
	return heap.Pop(this.minHeap).(int)
}

func (this *SeatManager) Unreserve(seatNumber int) {
	heap.Push(this.minHeap, seatNumber)
}

// IntHeap implements heap.Interface
type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

The Go solution uses container/heap and defines a custom IntHeap type. Reserve pops the smallest seat, and Unreserve pushes it back. The main difference is the need to explicitly define the heap interface in Go.

Worked Examples

Input: SeatManager(5)

Operations: reserve(), reserve(), unreserve(2), reserve(), reserve(), reserve(), reserve(), unreserve(5)

Operation	Heap State	Returned Value
init	[1,2,3,4,5]	null
reserve	[2,3,4,5]	1
reserve	[3,4,5]	2
unreserve(2)	[2,3,4,5]	null
reserve	[3,4,5]	2
reserve	[4,5]	3
reserve	[5]	4
reserve	[]	5
unreserve(5)	[5]	null

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n) per operation	Both reserve and unreserve perform heap push/pop
Space	O(n)	Heap stores all available seats

The time complexity is efficient because each heap operation is O(log n), and the space complexity is proportional to the number of seats.

Test Cases

# Basic functionality
sm = SeatManager(5)
assert sm.reserve() == 1  # First seat reserved
assert sm.reserve() == 2  # Second seat reserved
sm.unreserve(2)
assert sm.reserve() == 2  # Seat 2 reallocated
assert sm.reserve() == 3
assert sm.reserve() == 4
assert sm.reserve() == 5
sm.unreserve(5)
assert sm.reserve() == 5  # Seat 5 reallocated

# Edge case: only one seat
sm1 = SeatManager(1)
assert sm1.reserve() == 1
sm1.unreserve(1)
assert sm1.reserve() == 1

# Large n
sm2 = SeatManager(100000)
assert sm2.reserve() == 1
assert sm2.reserve() == 2
sm2.unreserve(1)
assert sm2.reserve() == 1

Test	Why
Basic functionality	Checks that reservation and unreservation work as expected
Only one seat	Ensures the code handles the minimum number of seats
Large n	Ensures scalability for maximum constraints

Edge Cases

One edge case is when all seats are reserved, followed by an immediate unreservation. The heap ensures that unreserved seats are reinserted and immediately available for reserve.

Another edge case is having n = 1. The algorithm must still correctly reserve and unreserve the only seat. The heap operations handle this trivially.

A third edge case is performing multiple unreserve operations out of order, e.g., unreserving seats 5, then 3, then 2. The min-heap ensures that reserve always picks the smallest available number, regardless of the order of unreservations. This prevents errors that could arise in a naive array-based approach.