Seat Reservation Manager LeetCode 1845

Seat Reservation Manager (LeetCode 1845) asks you to design a data structure that manages n seats numbered 1 to n. You must support two operations: reserve(), which returns the smallest available seat number and marks it as reserved, and unreserve(seatNumber), which marks a previously reserved seat as available again.

The challenge is efficiency. A naive approach using a sorted array and linear scan gives O(n) per reserve and O(n) per unreserve due to insertion sorting. With up to 10^5 calls, a linear approach will time out. The goal is O(log n) per operation.

This problem belongs to the data structure design family on LeetCode — problems where you implement a class with specific methods. The key insight is recognizing which data structure naturally maintains a sorted order with fast extraction of the minimum element.

A min-heap is the ideal data structure for this problem. It maintains a collection of elements such that the minimum is always accessible at the top. Extraction of the minimum (heappop) runs in O(log n) time, and insertion (heappush) also runs in O(log n) time.

The mapping to this problem is direct: store all available seat numbers in the min-heap. To reserve a seat, call heappop — this removes and returns the smallest available seat in O(log n). To unreserve a seat, call heappush with the seat number — this inserts it back into the heap in O(log n), restoring its availability.

A SortedSet (available in Java via TreeSet) also works: pollFirst() extracts the minimum and add() inserts back, both O(log n). However, a min-heap is simpler to implement in Python with the built-in heapq module and carries lower constant factors. Both approaches satisfy the time complexity requirement.

The eager approach initializes the min-heap in the constructor by pushing all seat numbers 1 through n onto the heap. In Python: self.heap = list(range(1, n + 1)) followed by heapq.heapify(self.heap). The heapify call converts the list to a valid heap in O(n) linear time, which is better than pushing one by one (O(n log n)).

After construction, the heap contains all n seats in min-heap order. Every subsequent reserve or unreserve call runs in O(log n). The total memory used is O(n) to store all seat numbers, which is unavoidable since all seats must be tracked.

An alternative is the lazy initialization approach, which avoids the O(n) constructor cost. Instead of pushing all seats, maintain a counter starting at 1 that tracks the next natural seat to hand out. This trades constructor time for slightly more logic per operation.

The lazy approach avoids pushing all n seats at construction time. Instead, maintain a counter starting at 1 and an empty min-heap for returned seats. In reserve(): if the heap is empty, return counter and increment it (next natural seat); otherwise, heappop from the heap (a previously returned seat that may be smaller than counter).

In unreserve(seatNumber): always push seatNumber onto the heap. The heap stores only seats that have been returned via unreserve — not all available seats. The counter handles the tail of available seats that have never been returned.

This approach uses O(1) constructor time and O(k) memory where k is the number of currently unreserved-but-not-yet-reserved-again seats. For workloads with few unreserve calls or large n, this is significantly more memory-efficient than the eager approach.

Consider SeatManager(5): seats 1-5 are available. Using the eager approach, the heap starts as [1, 2, 3, 4, 5]. The first reserve() call pops 1 → heap = [2, 3, 4, 5], returns 1. The second reserve() pops 2 → heap = [3, 4, 5], returns 2.

Now unreserve(2): push 2 back → heap = [2, 3, 4, 5]. The next reserve() pops 2 again (it is the smallest) → heap = [3, 4, 5], returns 2. Then reserve() → pops 3, returns 3. After all operations: heap = [4, 5].

Using the lazy approach: counter starts at 1, heap empty. reserve() → counter=1, return 1, counter becomes 2. reserve() → heap empty, return 2, counter becomes 3. unreserve(2) → push 2, heap=[2]. reserve() → heap non-empty, pop 2, return 2. reserve() → heap empty, return 3, counter becomes 4. State: counter=4, heap=[].

Python (eager, heapq): in __init__, self.heap = list(range(1, n+1)); heapq.heapify(self.heap). reserve(): return heapq.heappop(self.heap). unreserve(seatNumber): heapq.heappush(self.heap, seatNumber). Python (lazy): __init__ sets self.heap = [] and self.counter = 1. reserve(): return heapq.heappop(self.heap) if self.heap else (self.counter := self.counter + 1) - 1. unreserve(): heapq.heappush(self.heap, seatNumber). Both run in O(log n) per call.

Java (eager, PriorityQueue): PriorityQueue<Integer> pq = new PriorityQueue<>(). In constructor, for (int i = 1; i <= n; i++) pq.offer(i). reserve(): return pq.poll(). unreserve(int seatNumber): pq.offer(seatNumber). Java (lazy): int counter = 1; PriorityQueue<Integer> pq = new PriorityQueue<>(). reserve(): return pq.isEmpty() ? counter++ : pq.poll(). unreserve(): pq.offer(seatNumber).

Time complexity for both languages and both approaches: O(log n) per reserve and unreserve call. Space: O(n) for eager, O(k) for lazy where k is the heap size at any point. The Java PriorityQueue is a min-heap by default, matching Python's heapq behavior.

Smallest Number in Infinite Set (LeetCode 2336) is a direct cousin: maintain the smallest integer available from an infinite set starting at 1, with popSmallest() and addBack() operations. The lazy counter + min-heap technique from this problem applies there identically — counter for next natural number, heap for added-back numbers.

Kth Largest Element in a Stream (LeetCode 703) uses a min-heap of size k to maintain the k largest elements seen so far. Stock Price Fluctuation (LeetCode 2034) uses both a min-heap and max-heap to track price extremes. These problems share the theme of maintaining order statistics dynamically using heap operations.

The data structure design family on LeetCode often rewards recognizing which abstract data type maps cleanly to the problem. For "smallest available" queries, min-heap or TreeSet is the answer. For "k-th largest", a min-heap of size k suffices. Building intuition for these mappings is more valuable than memorizing solutions.