Seat Reservation Manager - Solution & Explanation
Problem Statement
Design a system that manages the reservation state of n seats that are numbered from 1 to n.
Implement the SeatManager class:
SeatManager(int n)Initializes aSeatManagerobject that will managenseats numbered from1ton. All seats are initially available.int reserve()Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.void unreserve(int seatNumber)Unreserves the seat with the givenseatNumber.
Example 1:
Input ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"] [[5], [], [], [2], [], [], [], [], [5]] Output [null, 1, 2, null, 2, 3, 4, 5, null] Explanation SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats. seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5]. seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2. seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3. seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4. seatManager.reserve(); // The only available seat is seat 5, so return 5. seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].
Constraints:
1 <= n <= 1051 <= seatNumber <= n- For each call to
reserve, it is guaranteed that there will be at least one unreserved seat. - For each call to
unreserve, it is guaranteed thatseatNumberwill be reserved. - At most
105calls in total will be made toreserveandunreserve.
Approach Overview
Problem Overview: You need to design a seat reservation system that always assigns the smallest available seat number. Two operations exist: reserve() returns the lowest-numbered free seat, and unreserve(seatNumber) makes a seat available again. The challenge is maintaining the smallest free seat efficiently as seats are reserved and returned.
Approach 1: Min-Heap for Available Seats (O(log n) per operation)
The most common solution uses a min-heap (priority queue) to track all currently available seat numbers. Initially, push all seats from 1 to n into the heap. When reserve() is called, remove the smallest element using heappop() or poll(), which guarantees the lowest-numbered seat. When unreserve(seatNumber) is called, push that seat number back into the heap so it becomes available again. Each heap push or pop costs O(log n) time and the heap stores up to O(n) elements. This approach works well because heaps are optimized for repeatedly extracting the smallest value.
Approach 2: TreeSet (Sorted Set) to Track Free Seats (O(log n) per operation)
A TreeSet or other balanced binary search tree can maintain seat numbers in sorted order. Insert all seat numbers from 1 to n into the set during initialization. The reserve() operation retrieves and removes the smallest element using first() and remove(). When unreserve(seatNumber) is called, insert that seat number back into the set. Because a TreeSet is backed by a self-balancing BST, both insertion and deletion take O(log n) time while maintaining sorted order. Space complexity is O(n). This method is clean and idiomatic in languages like Java or C# where sorted sets are built-in.
Both approaches fall under the design category because you are implementing a data structure with defined operations and performance guarantees. The key observation is that the smallest available seat must always be accessible quickly. Using either a heap or a balanced ordered set ensures that retrieving the minimum value remains efficient even as seats are returned to the pool.
Recommended for interviews: The min-heap solution is usually expected. It directly models the requirement of always retrieving the smallest available seat and keeps the implementation simple. The TreeSet solution demonstrates familiarity with ordered sets and balanced trees, which is useful in languages with strong standard libraries. Showing both approaches signals strong understanding of priority queues and ordered data structures.
Approach 1: Using a Min-Heap to Manage Seats
In this approach, we use a min-heap (priority queue) to efficiently manage and retrieve the smallest numbered unreserved seat.
- When we initialize the
SeatManager, we populate the heap with all seat numbers from 1 ton. - For the
reservemethod, we simply extract the minimum element from the heap, which is the smallest numbered available seat. - To
unreservea seat, we add back the seat number to the heap, maintaining the heap properties.
The Python solution uses the built-in heapq module to manage a min-heap representing the available seats. Initially, all seats are added to the heap. The reserve method pops the smallest item, while unreserve pushes a seat number back into the heap.
Complexity
Time Complexity: O(log n) for both reserve and unreserve operations. We have to push and pop elements into/from a heap which takes logarithmic time.
Space Complexity: O(n) because of the storage required for the heap.
Approach 2: Using a TreeSet (Sorted Set) to Manage Seats
Here, we use a data structure that maintains elements in sorted order, such as a TreeSet in Java and C# which keeps the seats sorted automatically.
- Seats are stored in a sorted set, so we can easily access the smallest available seat.
reserveoperation fetches and removes the first (smallest) element from the set.- In the
unreservemethod, we simply add back the seat number to the set.
The Java solution with TreeSet maintains a sorted set of available seats. The reserve method retrieves and removes the smallest element, while unreserve re-adds a seat number.
Complexity
Time Complexity: O(log n) for both reserve and unreserve operations because TreeSet operations like add, remove, and first take logarithmic time.
Space Complexity: O(n), as we store up to n seat numbers.
Approach 3: Priority Queue (Min-Heap)
We define a priority queue (min-heap) q to store all the available seat numbers. Initially, we add all seat numbers from 1 to n into q.
When calling the reserve method, we pop the top element from q, which is the smallest available seat number.
When calling the unreserve method, we add the seat number back into q.
In terms of time complexity, the initialization time complexity is O(n) or O(n times log n), and the time complexity of the reserve and unreserve methods is both O(log n). The space complexity is O(n).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using a Min-Heap to Manage Seats | Time Complexity: Space Complexity: |
| Using a TreeSet (Sorted Set) to Manage Seats | Time Complexity: Space Complexity: |
| Priority Queue (Min-Heap) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap (Priority Queue) | O(log n) per reserve/unreserve | O(n) | Best general solution when you need constant access to the smallest available seat |
| TreeSet / Sorted Set | O(log n) per operation | O(n) | Ideal in languages with built-in ordered sets like Java or C# |
Video Solution
Seat Reservation Manager - Leetcode 1845 - Python • NeetCode • 9,711 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Seat Reservation Manager easy or hard?
Seat Reservation Manager Python/Java solution
How to solve Seat Reservation Manager in O(n)?
What is the best approach for Seat Reservation Manager?
Is Seat Reservation Manager asked at Google/Amazon/Meta?
What data structure is used in Seat Reservation Manager?
What is the time complexity of Seat Reservation Manager?
Ready to solve this problem?
Practice Seat Reservation Manager with our built-in code editor and test cases.
Practice on FleetCode