1845. Seat Reservation Manager

medium

Design a seat-reservation system that always reserves the smallest unreserved seat. A clean min-heap design problem that tests how comfortable you are with lazy initialization.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-25

Problem

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.

Constraints

1 <= n <= 10^5
1 <= 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 that seatNumber will be reserved.
At most 10^5 calls in total will be made to reserve and unreserve.

Examples

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); seatManager.reserve(); // returns 1. seatManager.reserve(); // returns 2. seatManager.unreserve(2); // free seat 2. seatManager.reserve(); // returns 2. seatManager.reserve(); // returns 3. seatManager.reserve(); // returns 4. seatManager.reserve(); // returns 5. seatManager.unreserve(5); // free seat 5.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive: keep a boolean array, scan from index 1 to find the smallest free. O(n) per reserve — too slow under 10^5 calls.

Hint 2

You need 'smallest free seat' in O(log n). That's a min-heap.

Hint 3

Eager: heapify [1..n] up front. Each reserve pops, each unreserve pushes. Simple but O(n) constructor.

Hint 4

Lazy: store a counter 'next' starting at 1 and a heap of returned seats. reserve returns the heap's min if non-empty, else next++.

Solution approach

Reveal approach

Two designs work. (1) Eager: in the constructor, heapify the list [1..n] into a min-heap. reserve pops; unreserve pushes. Constructor is O(n) (heapify), each op O(log n). (2) Lazy: keep an integer 'next' starting at 1 plus a min-heap of returned seats (initially empty). reserve: if the heap is non-empty, pop and return its min; else return next, then increment. unreserve: push the seat number. Lazy beats eager when n is huge relative to actual reserve calls — you never materialize seats you don't use. Both meet the constraints easily; pick lazy in interviews to demonstrate you're thinking about memory and constructor cost.

Complexity

Time: O(log n) per op, O(1) lazy constructor
Space: O(n) eager, O(reserve count) lazy

Related patterns

heap
design

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

Amazon
Google
Microsoft