LeetCode 855: Exam Room

Problem Restatement

We need to design an ExamRoom class.

There are n seats in one row, labeled:

0, 1, 2, ..., n - 1

When a student enters, they choose the seat that maximizes the distance to the closest occupied seat.

If several seats give the same distance, the student chooses the smallest seat number.

If the room is empty, the student sits at seat 0.

We need to support two operations:

For leave(p), the problem guarantees that a student is currently sitting at seat p.

Input and Output

Class shape:

class ExamRoom:

    def __init__(self, n: int):
        ...

    def seat(self) -> int:
        ...

    def leave(self, p: int) -> None:
        ...

Examples

Example:

examRoom = ExamRoom(10)

examRoom.seat()   # returns 0
examRoom.seat()   # returns 9
examRoom.seat()   # returns 4
examRoom.seat()   # returns 2
examRoom.leave(4)
examRoom.seat()   # returns 5

Walk through it.

At first, the room is empty, so the first student sits at 0.

Occupied seats:

[0]

The next student wants to be farthest from seat 0, so they sit at 9.

Occupied seats:

[0, 9]

The next student sits in the middle, at 4.

Occupied seats:

[0, 4, 9]

The next student compares the gaps:

Both give distance 2, so choose the smaller seat index, 2.

Occupied seats:

[0, 2, 4, 9]

Then seat 4 leaves.

Occupied seats:

[0, 2, 9]

The best open seat is now 5, between 2 and 9.

So the next seat() returns:

5

First Thought: Track Occupied Seats

The main thing we need to know is where students are currently sitting.

If we keep the occupied seats in sorted order, then every possible best seat comes from one of three places:

1. Seat 0, before the first occupied seat
2. A midpoint between two adjacent occupied seats
3. Seat n - 1, after the last occupied seat

So for each seat() call, we can scan the sorted occupied seats and compute the best candidate.

This is simple and reliable.

In Python, we can store occupied seats in a sorted list and use bisect.insort to insert new seats while keeping the list sorted.

Key Insight

Suppose two adjacent occupied seats are:

left
right

The best seat between them is the midpoint:

(left + right) // 2

The distance to the closest occupied seat is:

(right - left) // 2

For the left edge, before the first occupied seat, the best candidate is seat 0.

Its distance is:

first_occupied - 0

For the right edge, after the last occupied seat, the best candidate is seat n - 1.

Its distance is:

(n - 1) - last_occupied

We choose the candidate with the largest distance.

If distances tie, we keep the smaller seat index.

Scanning from left to right helps with ties, because smaller candidates appear earlier.

Algorithm

Maintain:

self.students

as a sorted list of occupied seats.

For seat():

1. If no seats are occupied:
   1. Insert 0
   2. Return 0
2. Start with candidate seat 0.
3. Its distance is the distance to the first occupied seat.
4. For every adjacent pair of occupied seats:
   1. Compute the midpoint.
   2. Compute its distance to the closest occupied seat.
   3. If this distance is larger than the current best, update the answer.
5. Check seat n - 1.
6. Insert the chosen seat into the sorted list.
7. Return it.

For leave(p):

1. Remove p from the sorted list.

Correctness

When the room is empty, the rule says the student must sit at seat 0, and the algorithm does exactly that.

Now suppose the room is not empty.

Any empty seat belongs to one of three regions: before the first occupied seat, between two adjacent occupied seats, or after the last occupied seat.

In the left region, seat 0 is farthest from the first occupied seat, so it is the best candidate for that region.

In the right region, seat n - 1 is farthest from the last occupied seat, so it is the best candidate for that region.

Between two adjacent occupied seats left and right, the seat that maximizes the minimum distance to both sides is the midpoint (left + right) // 2. If there are two central choices, the smaller index is correct because ties must choose the smaller seat.

Therefore, checking these candidates covers the best possible seat in every region.

The algorithm chooses the candidate with the largest distance. It only updates when it finds a strictly larger distance, so when distances tie, the earlier smaller candidate remains selected.

Thus, seat() always returns the seat required by the problem.

The leave(p) operation removes an occupied seat. Since the problem guarantees p is occupied, removing it restores the correct occupied-seat set.

Complexity

Let k be the number of currently occupied seats.

For the LeetCode constraints, this sorted-list approach is accepted and much simpler than an interval tree.

Implementation

from bisect import insort

class ExamRoom:

    def __init__(self, n: int):
        self.n = n
        self.students = []

    def seat(self) -> int:
        if not self.students:
            self.students.append(0)
            return 0

        best_seat = 0
        best_dist = self.students[0]

        for i in range(1, len(self.students)):
            left = self.students[i - 1]
            right = self.students[i]

            seat = (left + right) // 2
            dist = min(seat - left, right - seat)

            if dist > best_dist:
                best_dist = dist
                best_seat = seat

        last_seat = self.n - 1
        right_dist = last_seat - self.students[-1]

        if right_dist > best_dist:
            best_seat = last_seat

        insort(self.students, best_seat)
        return best_seat

    def leave(self, p: int) -> None:
        self.students.remove(p)

Code Explanation

The constructor stores the number of seats and starts with no occupied seats:

def __init__(self, n: int):
    self.n = n
    self.students = []

When the first student enters, the room is empty:

if not self.students:
    self.students.append(0)
    return 0

The first candidate is seat 0:

best_seat = 0
best_dist = self.students[0]

If the first occupied seat is at index 7, then seat 0 has distance 7.

Next, we inspect every gap between adjacent occupied seats:

for i in range(1, len(self.students)):
    left = self.students[i - 1]
    right = self.students[i]

The best seat in this gap is the midpoint:

seat = (left + right) // 2

Its distance to the closest occupied seat is:

dist = min(seat - left, right - seat)

If this distance is better than the best one found so far, we update:

if dist > best_dist:
    best_dist = dist
    best_seat = seat

We use > rather than >=.

That preserves the smaller seat index in a tie.

After checking middle gaps, we check the right edge:

last_seat = self.n - 1
right_dist = last_seat - self.students[-1]

If the right edge gives a strictly better distance, choose it:

if right_dist > best_dist:
    best_seat = last_seat

Finally, insert the selected seat while keeping the list sorted:

insort(self.students, best_seat)

For leaving:

self.students.remove(p)

This removes the occupied seat p.

Testing

def test_exam_room():
    room = ExamRoom(10)

    assert room.seat() == 0
    assert room.seat() == 9
    assert room.seat() == 4
    assert room.seat() == 2
    room.leave(4)
    assert room.seat() == 5

    room = ExamRoom(5)
    assert room.seat() == 0
    assert room.seat() == 4
    assert room.seat() == 2
    assert room.seat() == 1
    assert room.seat() == 3

    room.leave(0)
    assert room.seat() == 0

    room = ExamRoom(3)
    assert room.seat() == 0
    assert room.seat() == 2
    room.leave(0)
    assert room.seat() == 0

    print("all tests passed")

test_exam_room()

Test meaning: