How do you solve Exam Room on LeetCode?

Exam Room (LeetCode #855) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(n) space complexity. Key insight: Using a priority queue allows efficient management of gaps between occupied seats.

What is the brute force solution for Exam Room?

The brute force approach for Exam Room is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we check every seat to find the one that maximizes the distance to the nearest student. This is straightforward but inefficient, especially as the number of seats increases. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Exam Room?

Exam Room uses the following concepts: Design, Heap (Priority Queue), Ordered Set. The recommended patterns to study are: Heap, Binary Search, Sorted Set.

What are the interview tips for Exam Room?

Explain your thought process clearly; don't just jump into coding. Discuss edge cases and how you would handle them. Be prepared to optimize your solution after the initial brute-force approach.

What are common mistakes when solving Exam Room?

Not considering edge cases like the first student entering. Failing to efficiently manage seat occupancy and gaps.

#855

Exam Room

Medium

DesignHeap (Priority Queue)Ordered SetHeapBinary SearchSorted Set

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(1)	O(n)

💡

Intuition

Time O(log n)Space O(n)

The optimal solution uses a priority queue (or max-heap) to efficiently track the largest gaps between occupied seats. This allows us to quickly find the best seat for the next student without checking every seat.

⚙️

Algorithm

3 steps

1Step 1: Use a priority queue to store the gaps between occupied seats, along with their positions.
2Step 2: When a student wants to sit, pop the largest gap from the queue, calculate the best seat based on the gap, and push the new gaps created by this seating back into the queue.
3Step 3: When a student leaves, update the gaps in the queue accordingly.

solution.py31 lines

1import heapq
2
3class ExamRoom:
4    def __init__(self, n: int):
5        self.n = n
6        self.seats = []
7        self.free_intervals = []
8        heapq.heappush(self.free_intervals, (-n, 0))
9
10    def seat(self) -> int:
11        length, start = heapq.heappop(self.free_intervals)
12        length = -length
13        if start == 0:
14            seat = 0
15        elif start + length == self.n:
16            seat = start + length - 1
17        else:
18            seat = start + (length - 1) // 2
19        self.seats.append(seat)
20        if seat > 0:
21            heapq.heappush(self.free_intervals, (-(seat - start), start))
22        if seat + 1 < self.n:
23            heapq.heappush(self.free_intervals, (-(start + length - seat - 1), seat + 1))
24        return seat
25
26    def leave(self, p: int) -> None:
27        self.seats.remove(p)
28        self.seats.sort()
29        left = self.seats[self.seats.index(p) - 1] if self.seats.index(p) > 0 else -1
30        right = self.seats[self.seats.index(p) + 1] if self.seats.index(p) < len(self.seats) - 1 else self.n
31        heapq.heappush(self.free_intervals, (-(right - left - 1), left + 1))

ℹ

Complexity note: The time complexity is O(log n) for both seat and leave operations due to the use of a balanced tree structure (like a sorted set) to maintain the occupied seats.

1Using a priority queue allows efficient management of gaps between occupied seats.
2Maintaining a sorted structure of occupied seats enables quick calculations of distances.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.