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 a SeatManager object that will manage n seats numbered from 1 to n. 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 given seatNumber.
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 <= nreserve, it is guaranteed that there will be at least one unreserved seat.unreserve, it is guaranteed that seatNumber will be reserved.105 calls in total will be made to reserve and unreserve.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.
In this approach, we use a min-heap (priority queue) to efficiently manage and retrieve the smallest numbered unreserved seat.
SeatManager, we populate the heap with all seat numbers from 1 to n.reserve method, we simply extract the minimum element from the heap, which is the smallest numbered available seat.unreserve a 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.
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.
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.
reserve operation fetches and removes the first (smallest) element from the set.unreserve method, 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.
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.
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).
| 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) | — |
| 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# |
Seat Reservation Manager - Leetcode 1845 - Python • NeetCode • 9,535 views views
Watch 9 more video solutions →Practice Seat Reservation Manager with our built-in code editor and test cases.
Practice on FleetCode