Skip to main content
Talentd

Exam Room - Solution & Explanation

MediumDesignHeap (Priority Queue)Ordered Set24 min readAsked at: Amazon, Apple, Samsung +3
Practice this problem

Problem Statement

There is an exam room with n seats in a single row labeled from 0 to n - 1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0.

Design a class that simulates the mentioned exam room.

Implement the ExamRoom class:

  • ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
  • int seat() Returns the label of the seat at which the next student will set.
  • void leave(int p) Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student sitting at seat p.

 

Example 1:

Input
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
Output
[null, 0, 9, 4, 2, null, 5]

Explanation
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.

 

Constraints:

  • 1 <= n <= 109
  • It is guaranteed that there is a student sitting at seat p.
  • At most 104 calls will be made to seat and leave.

Approach Overview

Problem Overview: You manage an exam room with n seats numbered 0 to n-1. Each arriving student chooses a seat that maximizes the distance to the closest occupied seat. If multiple seats give the same distance, the student picks the smallest index. You must implement seat() and leave(p) efficiently.

Approach 1: Sorted List of Occupied Seats (O(n) seat, O(n) leave)

This approach maintains a sorted list (or ordered set) of occupied seat indices. When a student calls seat(), iterate through the sorted seats and compute the largest possible distance between adjacent occupied seats. Also check the edges: the distance from seat 0 to the first student and from the last student to n-1. The best candidate seat is either the midpoint between two occupied seats or an edge seat. Insert the chosen seat into the sorted structure and maintain order.

The key idea is that the optimal seat always lies either at the midpoint of the largest gap or at a boundary. Computing the midpoint of each gap requires scanning the occupied list, which takes O(n) time. Insertion or deletion in a list also costs O(n). Space complexity is O(n) because you store all occupied seats. This approach is straightforward and easy to implement, especially in Python with a list or in C++ with an ordered container from Ordered Set.

Approach 2: Maximum Heap of Intervals (O(log n) seat, O(log n) leave)

A more scalable design models the room as intervals of empty seats. Each interval represents the gap between two occupied seats, such as (left, right). The best seat inside an interval is the midpoint that maximizes the distance to neighbors. Store intervals in a max heap ordered by their effective seating distance (largest first), with ties broken by smaller seat index.

When seat() runs, extract the largest interval from the heap. Compute the optimal seat inside it, then split the interval into two new intervals and push them back into the heap. When leave(p) runs, merge the two intervals adjacent to seat p into a larger interval and update the heap. Efficient merging usually requires hash maps that track interval boundaries.

This design relies on a Heap (Priority Queue) to always retrieve the largest gap in O(log n) time. Both seating and leaving operations maintain interval structure with heap updates. Space complexity remains O(n). The approach demonstrates strong Design skills because you model the room as dynamic segments rather than raw seat indices.

Recommended for interviews: Start by explaining the sorted list approach to show the greedy insight that students always sit in the largest gap. Then present the interval heap design as the optimized solution. Interviewers typically expect the heap-based design because it reduces repeated scans and keeps operations near O(log n), which scales well when many seat and leave operations occur.

Approach 1: Approach 1: Sorted List of Occupied Seats

This approach uses a sorted list to keep track of occupied seats. When a student enters the room, we calculate potential distances at each interval and choose the seat that maximizes the minimum distance to any occupied seat. If multiple seats provide the same distance, the earliest seat in terms of index is chosen. When a student leaves, we simply remove the seat from the list.

We maintain a sorted list of occupied seats, allowing us to compute potential seating distances dynamically. The bisect module helps insert the new student in a sorted manner. Distances are checked between each successive occupied seat, including the boundaries.

Code

PythonC++

Python

C++

Complexity

The time complexity is O(N) for the seat method, where N is the number of currently occupied seats. The leave method has a time complexity of O(N) due to list manipulation. The space complexity is O(N) for storing the list of occupied seats.

Try this approach in the editor →

Approach 2: Approach 2: Maximum Heap of Intervals

In this approach, we utilize a max-heap (priority queue) to manage seat intervals. Each interval is prioritized by its distance, allowing us to efficiently determine where to seat the next student. The order of seating follows the priority determined by the maximum possible distance in the available intervals. When a student leaves, the adjacent intervals are merged and updated in the heap.

In this Java implementation, a priority queue manages intervals defined by two endpoints. The queue is structured such that intervals with the largest possible seating distances are dequeued first. When a new student is seated, two new intervals are created based on the seated position. The priority queue allows efficient management of these operations.

Code

JavaJavaScript

Java

JavaScript

Complexity

Both seat and leave methods have a time complexity of O(logN), where N is the number of intervals in the room. This complexity arises from the operations in the priority queue. Space complexity is O(N), accounting for storing intervals in the queue.

Try this approach in the editor →

Approach 3: Ordered Set + Hash Table

Considering that each time we call seat(), we need to find the seat with the maximum distance, we can use an ordered set to store seat intervals. Each element of the ordered set is a tuple (l, r), indicating that the seats between l and r (excluding l and r) can be occupied by a student. Initially, the ordered set contains only one element (-1, n), indicating that the seats between (-1, n) can be occupied by a student.

Additionally, we use two hash tables left and right to maintain the left and right neighbors of each occupied seat, making it easier to merge two seat intervals when calling leave(p).

The time complexity is O(log n), and the space complexity is O(n). Here, n is the number of seats in the exam room.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorted List of Occupied Seats

The time complexity is O(N) for the seat method, where N is the number of currently occupied seats. The leave method has a time complexity of O(N) due to list manipulation. The space complexity is O(N) for storing the list of occupied seats.

Approach 2: Maximum Heap of Intervals

Both seat and leave methods have a time complexity of O(logN), where N is the number of intervals in the room. This complexity arises from the operations in the priority queue. Space complexity is O(N), accounting for storing intervals in the queue.

Ordered Set + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorted List of Occupied Seatsseat(): O(n), leave(): O(n)O(n)Good for simple implementations or when the number of operations is small
Maximum Heap of Intervalsseat(): O(log n), leave(): O(log n)O(n)Best for large numbers of operations; maintains the largest seating gap efficiently

Video Solution

855. Exam Room (LeetCode) • hakunamatasq • 4,478 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Exam Room easy or hard?
Exam Room is rated Medium but leans toward design-heavy reasoning. The greedy insight about choosing the largest gap is straightforward, but implementing the interval heap structure with correct merges requires careful handling of edge cases.
Exam Room Python or Java solution?
Python implementations often use a sorted list with binary insertion for the simpler approach or heapq with custom interval logic for the optimized solution. Java implementations typically rely on PriorityQueue and TreeSet structures to maintain ordered seats and interval boundaries.
How to solve Exam Room in O(log n)?
Model the exam room as intervals of empty seats and store them in a max heap ordered by seating distance. When a student arrives, pop the largest interval, place the student at the optimal midpoint, then split the interval into two smaller ones and push them back. Heap operations keep each update at O(log n).
What is the best approach for Exam Room?
The interval-based design using a max heap (priority queue) is considered the best approach. It stores empty seat ranges and always selects the interval that maximizes distance to the nearest student. Both seat() and leave() operations run in O(log n) time, which is more efficient than scanning all occupied seats.
Is Exam Room asked at Google/Amazon/Meta?
Exam Room is a classic design-style interview problem that appears in large tech company preparation lists. Variations of seat allocation or interval scheduling have been reported in interviews at companies like Google, Amazon, and Meta. The problem tests data structure design, priority queues, and edge-case reasoning.
What data structure is used in Exam Room?
Common implementations use either a sorted set of occupied seats or a max heap storing empty intervals. The optimized design also uses hash maps to quickly merge adjacent intervals when a student leaves. Together these structures allow efficient seat selection and interval updates.
What is the time complexity of Exam Room?
Using a sorted list of occupied seats leads to O(n) time for seat() because you scan all gaps to find the maximum distance. The optimized heap-based interval solution reduces operations to O(log n) time. Space complexity in both designs is O(n) since you track occupied seats or intervals.

Ready to solve this problem?

Practice Exam Room with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximize Distance to Closest Person