Abstract / Summary

A program manages seats in an exam room by placing new students in seats that maximize distance to others.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 44% (100k+ submissions).

Typical patterns to solve this problem:

• Design
• Heap (Priority Queue)
• Ordered Set

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The ExamRoom class models a linear arrangement of seats numbered from 0 to n-1. It maintains the set of occupied seats in a sorted list and provides two operations: seat, which returns the position a new student should take to maximize the distance to the nearest occupied seat, and leave, which removes a student from a given seat. The implementation relies on simple integer arithmetic and a binary-insertion helper to keep the occupied seats ordered without costly re-sorting.

Initialization

def __init__(self, n: int):
    self.last  = n - 1          # right-most seat index
    self.used  = 0              # count of occupied seats
    self.seats = []             # sorted list of occupied positions

The constructor stores the index of the farthest seat, initializes a counter for the number of occupied seats, and creates an empty list that will hold the occupied seat numbers in ascending order.

Seating a Student

The seat method follows a deterministic sequence of checks to locate the optimal seat.

First Student

When self.used equals 0, the room is empty. The method places the first student at seat 0, updates the counter, stores the seat in the list, and returns the position.

if self.used == 0:
    self.used  = 1
    self.seats = [0]
    return 0

Left-End Candidate

If the room already contains students, the algorithm first evaluates the distance from the left wall to the first occupied seat. The distance is simply the index of the leftmost occupied seat, and the provisional result is set to seat 0.

distance = self.seats[0]
result   = 0

Interior Gaps

The method then iterates over each pair of consecutive occupied seats. For each gap, it computes the midpoint distance as integer division of the gap length by 2. When the computed distance exceeds the current best, the algorithm updates both the best distance and the candidate seat to the lower midpoint (the floor of the average). A guard clause skips gaps that contain no free seat (adjacent occupied seats).

for i in range(1, len(self.seats)):
    left  = self.seats[i - 1]
    right = self.seats[i]
    if left + 1 == right:
        continue
    current = (right - left) // 2
    if distance < current:
        distance = current
        result  = (right + left) // 2

Right-End Candidate

After processing interior gaps, the algorithm evaluates the distance from the rightmost occupied seat to the far wall. If this distance is larger than the best distance found so far, the rightmost seat (self.last) becomes the final choice.

current = self.last - self.seats[-1]
if distance < current:
    result = self.last

Insertion and Return

The selected seat is inserted into the sorted list using insort, which performs a binary search to locate the insertion point and shifts elements accordingly. This keeps self.seats ordered without a full resort. The occupied counter is incremented, and the chosen seat index is returned.

self.used += 1
insort(self.seats, result)
return result

Removing a Student

The leave method removes a seat number from the sorted list and decrements the occupied counter. The removal uses the list’s remove method, which finds the element by value and shifts subsequent elements leftward.

def leave(self, p: int) -> None:
    self.seats.remove(p)
    self.used -= 1

Edge Cases Handled

The implementation explicitly addresses several boundary conditions. When the room is empty, the first student is placed at the leftmost seat, guaranteeing a valid return value without further computation. The loop that scans interior gaps skips over adjacent occupied seats, preventing division by zero or negative distances. The left-end and right-end checks ensure that seats at the extremes are considered even when interior gaps are larger, preserving the rule that the farthest possible seat is chosen. The integer division used for midpoint calculation automatically rounds down, satisfying the requirement to select the lowest numbered seat when two positions are equally distant.

Performance Optimizations

A notable optimization is the use of a sorted list combined with the insort function from the bisect module. By maintaining order incrementally, the code avoids the overhead of sorting the entire collection after each insertion. The binary search performed by insort reduces the number of element moves needed to place a new seat, especially when the list grows large. The early continue statement inside the interior-gap loop eliminates unnecessary midpoint calculations for gaps that contain no free seats, saving arithmetic work. Storing the rightmost seat index (self.last) as a pre-computed value removes the need to recompute n-1 on each call, marginally reducing repeated attribute lookups.

Overall, the class provides a compact and efficient solution for dynamically allocating seats while preserving the maximal distance invariant.

Imagine a big room with a long row of chairs. Some chairs are empty and some are taken by friends. This code helps decide where someone should sit so they have the most space away from everyone else.

At the very start, the room is empty. When a new person wants to sit down, the code looks at three different spots. It looks at the very first chair on the left, the very last chair on the right, and all the gaps between the people already sitting.

To find the best spot, the code measures the distance between the neighbors. It wants the biggest gap possible so that everyone can have plenty of room. If the gap at the beginning or the end is the biggest one, the person will choose the end chair. If there is a big space in the middle between two friends, the person will pick the chair right in the middle of that gap.

Once the best spot is found, that person sits down and the code remembers that the chair is now full. If someone needs to leave the room, the code simply finds their chair and clears it, making the seat empty again for someone else.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++				Python	Java			TS
	WalkCCC	C++					Java
	leetcode.ca	C++				Python	Java		Go	TS
	LeetcodeHelp	C++				Python	Java
	Progiez	C++				Python	Java
github	black-shadows	C++
	charles-wangkai						Java
	everthis		JS
	fengvyi	C++
	JoshCrozier		JS
	lkwq007					Python
	MacJim	C++
	martianoff			Scala
	ruoru				Rust
	suxrobGM							C#
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
martianoff	Scala
ruoru	Rust
suxrobGM	C#
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality