855. Exam Room

MediumDesignOrdered SetHeap (Priority Queue)

Problem Description

This problem asks you to simulate an exam room with n seats arranged in a single row, numbered from 0 to n - 1. The key challenge is managing seat assignments based on a specific social distancing rule.

When a student enters the room, they must choose their seat according to these rules:

Maximum Distance Rule: The student must sit in the seat that maximizes the distance to the closest person already seated
Tie-Breaking Rule: If multiple seats have the same maximum distance to the closest person, choose the seat with the lowest number
Empty Room Rule: If the room is empty, the student sits at seat 0

You need to implement a class ExamRoom with three methods:

ExamRoom(int n): Initialize the exam room with n seats
int seat(): Find and return the seat number where the next student should sit (following the rules above)
void leave(int p): Mark that the student at seat p is leaving the room

The solution uses an ordered set to maintain intervals of available seats. Each interval (l, r) represents that seats between l and r (exclusive) are available. The intervals are sorted by:

The distance they provide (larger distances come first)
The starting position (smaller positions come first for tie-breaking)

The distance calculation differs based on the interval position:

For intervals at the boundaries (-1, r) or (l, n): distance is r - l - 1
For internal intervals (l, r): distance is (r - l) / 2 (since a student would sit in the middle)

Two hash tables left and right track the neighboring intervals for each occupied seat, enabling efficient interval merging when a student leaves.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is to think about this problem in terms of intervals rather than individual seats. When students are seated, they create gaps or intervals between them where new students can potentially sit.

Consider what happens when we have students at seats 2 and 7. This creates three intervals:

(-1, 2): representing seats 0 and 1
(2, 7): representing seats 3, 4, 5, 6
(7, n): representing seats from 8 to n-1

When a new student arrives, they want to maximize distance to others. For each interval (l, r):

If it's at the boundary (starting at -1 or ending at n), the student would sit at the edge (seat 0 or seat n-1), giving distance r - l - 1
If it's an internal interval, the student would sit in the middle at position (l + r) / 2, giving distance (r - l) / 2 to the nearest person

We need to quickly find the interval with the maximum distance. This suggests using a sorted data structure. Since intervals change dynamically as students arrive and leave, we need an ordered set that can efficiently insert and remove intervals while maintaining sorted order.

The sorting criteria becomes clear: sort intervals by their "effective distance" (the actual distance a student would get if they sat in that interval), with ties broken by choosing the leftmost interval.

When a student sits down, they split one interval into two smaller ones. For example, if a student sits at position p in interval (l, r), it becomes two intervals: (l, p) and (p, r).

When a student leaves, we need to merge intervals. If a student at position p leaves, and they had neighbors at l and r, we merge (l, p) and (p, r) back into (l, r). To efficiently find these neighbors, we maintain hash tables left and right that map each position to its left and right interval boundaries.

This interval-based approach transforms the problem from tracking individual seats to managing a dynamic set of intervals, making the solution both elegant and efficient.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The implementation uses an ordered set (SortedList) to maintain seat intervals and two hash tables to track interval relationships.

Data Structures

Ordered Set (ts): Stores intervals as tuples (l, r) sorted by:
- Primary: Negative distance (larger distances come first)
- Secondary: Left boundary (smaller positions come first)
The distance function is defined as:
```
def dist(x):
    l, r = x
    return r - l - 1 if l == -1 or r == n else (r - l) >> 1
```
- For boundary intervals (l == -1 or r == n): distance = r - l - 1
- For internal intervals: distance = (r - l) >> 1 (equivalent to (r - l) // 2)
Hash Tables (left and right):
- left[p]: stores the left boundary of the interval ending at position p
- right[p]: stores the right boundary of the interval starting at position p

Initialization

def __init__(self, n: int):
    # Initialize with one interval covering the entire room
    self.add((-1, n))

The room starts with a single interval (-1, n), representing all seats from 0 to n-1 are available.

Seat Assignment

def seat(self) -> int:
    s = self.ts[0]  # Get the best interval (first in sorted order)
    p = (s[0] + s[1]) >> 1  # Default: middle position
  
    # Handle boundary cases
    if s[0] == -1:
        p = 0  # Left boundary: sit at seat 0
    elif s[1] == self.n:
        p = self.n - 1  # Right boundary: sit at last seat
  
    # Split the interval
    self.delete(s)
    self.add((s[0], p))
    self.add((p, s[1]))
    return p

The algorithm:

Takes the first interval from the sorted set (highest priority)
Calculates the seat position based on interval type
Removes the original interval
Adds two new intervals split by the chosen seat

Student Leaving

def leave(self, p: int) -> None:
    l, r = self.left[p], self.right[p]  # Find neighboring boundaries
    self.delete((l, p))  # Remove left interval
    self.delete((p, r))  # Remove right interval
    self.add((l, r))     # Add merged interval

When a student leaves seat p:

Use hash tables to find the intervals (l, p) and (p, r)
Remove both intervals
Merge them into a single interval (l, r)

Helper Methods

def add(self, s):
    self.ts.add(s)
    self.left[s[1]] = s[0]   # Map right boundary to left boundary
    self.right[s[0]] = s[1]  # Map left boundary to right boundary

def delete(self, s):
    self.ts.remove(s)
    self.left.pop(s[1])
    self.right.pop(s[0])

These methods maintain consistency between the ordered set and hash tables whenever intervals are added or removed.

Time Complexity

seat(): O(log n) for ordered set operations
leave(p): O(log n) for ordered set operations
Space complexity: O(n) for storing intervals and hash tables

The solution elegantly handles the dynamic nature of the problem by treating available seats as intervals rather than individual positions, allowing efficient queries for the best seat and updates when students arrive or leave.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with an exam room of 10 seats (n = 10).

Initial State:

Room has seats numbered 0-9
Interval: (-1, 10) representing all seats are empty
Ordered set: [(-1, 10)]

Step 1: First student enters (seat())

Best interval: (-1, 10) (only one available)
Since this is a left boundary interval (l == -1), student sits at seat 0
Split interval: Remove (-1, 10), add (-1, 0) and (0, 10)
Ordered set: [(0, 10), (-1, 0)] (sorted by distance: 9 vs 0)
Return: 0

Step 2: Second student enters (seat())

Best interval: (0, 10) (distance = 9)
Since this is a right boundary interval (r == 10), student sits at seat 9
Split interval: Remove (0, 10), add (0, 9) and (9, 10)
Ordered set: [(0, 9), (-1, 0), (9, 10)] (distances: 4, 0, 0)
Return: 9

Step 3: Third student enters (seat())

Best interval: (0, 9) (distance = 4, as (9-0)/2 = 4)
This is an internal interval, so student sits in middle: (0+9)/2 = 4
Split interval: Remove (0, 9), add (0, 4) and (4, 9)
Ordered set: [(0, 4), (4, 9), (-1, 0), (9, 10)] (distances: 2, 2, 0, 0)
Return: 4

Step 4: Fourth student enters (seat())

Best interval: (0, 4) (distance = 2, leftmost among ties)
Internal interval, sit in middle: (0+4)/2 = 2
Split interval: Remove (0, 4), add (0, 2) and (2, 4)
Ordered set: [(4, 9), (0, 2), (2, 4), (-1, 0), (9, 10)]
Return: 2

Step 5: Student at seat 4 leaves (leave(4))

Using hash tables: left[4] = 2, right[4] = 9
Remove intervals: (2, 4) and (4, 9)
Add merged interval: (2, 9)
Ordered set: [(2, 9), (0, 2), (-1, 0), (9, 10)] (distances: 3, 1, 0, 0)

Step 6: Fifth student enters (seat())

Best interval: (2, 9) (distance = 3)
Internal interval, sit in middle: (2+9)/2 = 5
Split interval: Remove (2, 9), add (2, 5) and (5, 9)
Return: 5

The hash tables throughout maintain the relationships:

After step 3: left = {0: -1, 4: 0, 9: 4, 10: 9}, right = {-1: 0, 0: 4, 4: 9, 9: 10}
After step 5: left = {0: -1, 2: 0, 9: 2, 10: 9}, right = {-1: 0, 0: 2, 2: 9, 9: 10}

This example demonstrates how the algorithm maintains maximum distance between students while handling both arrivals and departures efficiently.

Solution Implementation

1from sortedcontainers import SortedList
2
3class ExamRoom:
4    def __init__(self, n: int):
5        """
6        Initialize the exam room with n seats numbered from 0 to n-1.
7      
8        Args:
9            n: Total number of seats in the exam room
10        """
11        def calculate_distance(segment):
12            """
13            Calculate the maximum distance a student can sit from others in a segment.
14          
15            For segments at the boundaries (starting at -1 or ending at n),
16            the distance is the full length minus 1.
17            For internal segments, the distance is half the segment length (sitting in middle).
18            """
19            left, right = segment
20            if left == -1 or right == n:
21                # Boundary segment: student sits at edge (0 or n-1)
22                return right - left - 1
23            else:
24                # Internal segment: student sits in the middle
25                return (right - left) >> 1
26      
27        self.n = n
28        # SortedList maintains segments sorted by:
29        # 1. Maximum distance (descending, hence negative)
30        # 2. Left boundary (ascending, for tie-breaking)
31        self.sorted_segments = SortedList(key=lambda segment: (-calculate_distance(segment), segment[0]))
32      
33        # Maps to track segment boundaries
34        self.left_boundary = {}   # Maps right boundary -> left boundary
35        self.right_boundary = {}  # Maps left boundary -> right boundary
36      
37        # Initially, the entire room is one empty segment from -1 to n
38        self._add_segment((-1, n))
39  
40    def seat(self) -> int:
41        """
42        Assign a seat to a student maximizing distance from others.
43      
44        Returns:
45            The seat position assigned to the student
46        """
47        # Get the segment with maximum available distance
48        best_segment = self.sorted_segments[0]
49      
50        # Calculate where to place the student
51        position = (best_segment[0] + best_segment[1]) >> 1  # Default: middle of segment
52      
53        # Handle boundary cases
54        if best_segment[0] == -1:
55            # Left boundary: sit at position 0
56            position = 0
57        elif best_segment[1] == self.n:
58            # Right boundary: sit at position n-1
59            position = self.n - 1
60      
61        # Remove the original segment
62        self._delete_segment(best_segment)
63      
64        # Add two new segments created by placing the student
65        self._add_segment((best_segment[0], position))
66        self._add_segment((position, best_segment[1]))
67      
68        return position
69  
70    def leave(self, p: int) -> None:
71        """
72        Remove a student from seat p and merge the adjacent segments.
73      
74        Args:
75            p: The seat position being vacated
76        """
77        # Find the segments on both sides of position p
78        left_neighbor = self.left_boundary[p]
79        right_neighbor = self.right_boundary[p]
80      
81        # Remove the two segments adjacent to position p
82        self._delete_segment((left_neighbor, p))
83        self._delete_segment((p, right_neighbor))
84      
85        # Add the merged segment
86        self._add_segment((left_neighbor, right_neighbor))
87  
88    def _add_segment(self, segment):
89        """
90        Add a segment to the data structures.
91      
92        Args:
93            segment: Tuple (left, right) representing an empty segment
94        """
95        self.sorted_segments.add(segment)
96        self.left_boundary[segment[1]] = segment[0]
97        self.right_boundary[segment[0]] = segment[1]
98  
99    def _delete_segment(self, segment):
100        """
101        Remove a segment from the data structures.
102      
103        Args:
104            segment: Tuple (left, right) representing an empty segment
105        """
106        self.sorted_segments.remove(segment)
107        self.left_boundary.pop(segment[1])
108        self.right_boundary.pop(segment[0])
109
110
111# Your ExamRoom object will be instantiated and called as such:
112# obj = ExamRoom(n)
113# param_1 = obj.seat()
114# obj.leave(p)
115

1class ExamRoom {
2    // TreeSet to store intervals sorted by distance (descending) and start position (ascending)
3    private TreeSet<int[]> intervals = new TreeSet<>((a, b) -> {
4        int distance1 = calculateDistance(a);
5        int distance2 = calculateDistance(b);
6        // If distances are equal, sort by start position
7        return distance1 == distance2 ? a[0] - b[0] : distance2 - distance1;
8    });
9  
10    // Map to store the left neighbor of each position
11    private Map<Integer, Integer> leftNeighbor = new HashMap<>();
12  
13    // Map to store the right neighbor of each position
14    private Map<Integer, Integer> rightNeighbor = new HashMap<>();
15  
16    // Total number of seats in the exam room
17    private int totalSeats;
18
19    /**
20     * Initialize exam room with n seats numbered from 0 to n-1
21     * @param n the total number of seats
22     */
23    public ExamRoom(int n) {
24        this.totalSeats = n;
25        // Initially, add the entire room as one empty interval
26        // Using -1 and n as boundaries to handle edge cases
27        addInterval(new int[] {-1, n});
28    }
29
30    /**
31     * Find the best seat to maximize distance from others and occupy it
32     * @return the seat number that was occupied
33     */
34    public int seat() {
35        // Get the interval with maximum distance
36        int[] largestInterval = intervals.first();
37      
38        // Calculate the position to sit
39        // Default: sit in the middle of the interval
40        int position = (largestInterval[0] + largestInterval[1]) >> 1;
41      
42        // Special case: if interval starts at -1, sit at position 0
43        if (largestInterval[0] == -1) {
44            position = 0;
45        } 
46        // Special case: if interval ends at n, sit at position n-1
47        else if (largestInterval[1] == totalSeats) {
48            position = totalSeats - 1;
49        }
50      
51        // Remove the original interval
52        removeInterval(largestInterval);
53      
54        // Add two new intervals split by the seated position
55        addInterval(new int[] {largestInterval[0], position});
56        addInterval(new int[] {position, largestInterval[1]});
57      
58        return position;
59    }
60
61    /**
62     * Mark a seat as empty when a student leaves
63     * @param p the seat number to be vacated
64     */
65    public void leave(int p) {
66        // Find the left and right boundaries of intervals adjacent to position p
67        int leftBoundary = leftNeighbor.get(p);
68        int rightBoundary = rightNeighbor.get(p);
69      
70        // Remove the two intervals that have p as boundary
71        removeInterval(new int[] {leftBoundary, p});
72        removeInterval(new int[] {p, rightBoundary});
73      
74        // Merge into one larger interval
75        addInterval(new int[] {leftBoundary, rightBoundary});
76    }
77
78    /**
79     * Calculate the maximum distance achievable in an interval
80     * @param interval the interval [left, right]
81     * @return the maximum distance from occupied seats
82     */
83    private int calculateDistance(int[] interval) {
84        int left = interval[0];
85        int right = interval[1];
86      
87        // Edge cases: intervals at the boundaries
88        if (left == -1 || right == totalSeats) {
89            // Distance is the entire interval length minus 1
90            return right - left - 1;
91        }
92        // Regular case: internal interval
93        // Maximum distance is half of the interval length
94        return (right - left) >> 1;
95    }
96
97    /**
98     * Add an interval to the data structures
99     * @param interval the interval to add
100     */
101    private void addInterval(int[] interval) {
102        intervals.add(interval);
103        // Update neighbor mappings
104        leftNeighbor.put(interval[1], interval[0]);
105        rightNeighbor.put(interval[0], interval[1]);
106    }
107
108    /**
109     * Remove an interval from the data structures
110     * @param interval the interval to remove
111     */
112    private void removeInterval(int[] interval) {
113        intervals.remove(interval);
114        // Clean up neighbor mappings
115        leftNeighbor.remove(interval[1]);
116        rightNeighbor.remove(interval[0]);
117    }
118}
119
120/**
121 * Your ExamRoom object will be instantiated and called as such:
122 * ExamRoom obj = new ExamRoom(n);
123 * int param_1 = obj.seat();
124 * obj.leave(p);
125 */
126

1class ExamRoom {
2private:
3    int roomSize;  // Total number of seats in the exam room
4  
5    // Calculate the distance to the nearest student for a given interval
6    static int N;  // Static variable for comparator access
7  
8    static int calculateDistance(const pair<int, int>& interval) {
9        auto [left, right] = interval;
10        // Special case: leftmost interval (no student on the left)
11        if (left == -1 || right == N) {
12            return right - left - 1;
13        }
14        // Regular case: distance is half of the interval length
15        return (right - left) >> 1;
16    }
17  
18    // Custom comparator for ordering intervals by distance (largest first)
19    struct IntervalComparator {
20        bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
21            int distanceA = calculateDistance(a);
22            int distanceB = calculateDistance(b);
23            // If distances are equal, prefer leftmost interval
24            if (distanceA == distanceB) {
25                return a.first < b.first;
26            }
27            // Otherwise, order by distance (largest first)
28            return distanceA > distanceB;
29        }
30    };
31  
32    // Data structures to maintain intervals and their relationships
33    set<pair<int, int>, IntervalComparator> intervals;  // All available intervals sorted by distance
34    unordered_map<int, int> leftNeighbor;   // Maps position -> left neighbor position
35    unordered_map<int, int> rightNeighbor;  // Maps position -> right neighbor position
36  
37    // Add an interval to the data structures
38    void addInterval(pair<int, int> interval) {
39        intervals.insert(interval);
40        leftNeighbor[interval.second] = interval.first;
41        rightNeighbor[interval.first] = interval.second;
42    }
43  
44    // Remove an interval from the data structures
45    void removeInterval(pair<int, int> interval) {
46        intervals.erase(interval);
47        leftNeighbor.erase(interval.second);
48        rightNeighbor.erase(interval.first);
49    }
50  
51public:
52    ExamRoom(int n) {
53        N = n;  // Set static variable for comparator
54        roomSize = n;
55        // Initially, the entire room is empty (represented as interval from -1 to n)
56        addInterval({-1, n});
57    }
58  
59    int seat() {
60        // Get the interval with maximum distance
61        auto largestInterval = *intervals.begin();
62      
63        // Calculate the optimal seat position
64        int seatPosition = (largestInterval.first + largestInterval.second) >> 1;
65      
66        // Special case: if interval starts at -1, sit at position 0
67        if (largestInterval.first == -1) {
68            seatPosition = 0;
69        }
70        // Special case: if interval ends at roomSize, sit at the last position
71        else if (largestInterval.second == roomSize) {
72            seatPosition = roomSize - 1;
73        }
74      
75        // Remove the old interval and add two new intervals
76        removeInterval(largestInterval);
77        addInterval({largestInterval.first, seatPosition});
78        addInterval({seatPosition, largestInterval.second});
79      
80        return seatPosition;
81    }
82  
83    void leave(int p) {
84        // Find the intervals adjacent to position p
85        int leftPos = leftNeighbor[p];
86        int rightPos = rightNeighbor[p];
87      
88        // Remove the two intervals that include position p
89        removeInterval({leftPos, p});
90        removeInterval({p, rightPos});
91      
92        // Merge into a single interval
93        addInterval({leftPos, rightPos});
94    }
95};
96
97// Initialize static member
98int ExamRoom::N = 0;
99
100/**
101 * Your ExamRoom object will be instantiated and called as such:
102 * ExamRoom* obj = new ExamRoom(n);
103 * int param_1 = obj->seat();
104 * obj->leave(p);
105 */
106

1// TreeSet implementation using Red-Black Tree
2type Compare<T> = (lhs: T, rhs: T) => number;
3
4// Red-Black Tree Node class
5class RBTreeNode<T = number> {
6    data: T;
7    count: number;
8    left: RBTreeNode<T> | null;
9    right: RBTreeNode<T> | null;
10    parent: RBTreeNode<T> | null;
11    color: number; // 0 = red, 1 = black
12  
13    constructor(data: T) {
14        this.data = data;
15        this.left = this.right = this.parent = null;
16        this.color = 0; // New nodes are red by default
17        this.count = 1;
18    }
19
20    // Get sibling node
21    sibling(): RBTreeNode<T> | null {
22        if (!this.parent) return null;
23        return this.isOnLeft() ? this.parent.right : this.parent.left;
24    }
25
26    // Check if node is left child of its parent
27    isOnLeft(): boolean {
28        return this === this.parent!.left;
29    }
30
31    // Check if node has at least one red child
32    hasRedChild(): boolean {
33        return (
34            Boolean(this.left && this.left.color === 0) ||
35            Boolean(this.right && this.right.color === 0)
36        );
37    }
38}
39
40// Red-Black Tree implementation
41class RBTree<T> {
42    root: RBTreeNode<T> | null;
43    lessThan: (left: T, right: T) => boolean;
44  
45    constructor(compare: Compare<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0)) {
46        this.root = null;
47        this.lessThan = (left: T, right: T) => compare(left, right) < 0;
48    }
49
50    // Left rotation for balancing
51    rotateLeft(pivotNode: RBTreeNode<T>): void {
52        const rightChild = pivotNode.right!;
53        pivotNode.right = rightChild.left;
54
55        if (pivotNode.right) pivotNode.right.parent = pivotNode;
56        rightChild.parent = pivotNode.parent;
57
58        if (!pivotNode.parent) this.root = rightChild;
59        else if (pivotNode === pivotNode.parent.left) pivotNode.parent.left = rightChild;
60        else pivotNode.parent.right = rightChild;
61
62        rightChild.left = pivotNode;
63        pivotNode.parent = rightChild;
64    }
65
66    // Right rotation for balancing
67    rotateRight(pivotNode: RBTreeNode<T>): void {
68        const leftChild = pivotNode.left!;
69        pivotNode.left = leftChild.right;
70
71        if (pivotNode.left) pivotNode.left.parent = pivotNode;
72        leftChild.parent = pivotNode.parent;
73
74        if (!pivotNode.parent) this.root = leftChild;
75        else if (pivotNode === pivotNode.parent.left) pivotNode.parent.left = leftChild;
76        else pivotNode.parent.right = leftChild;
77
78        leftChild.right = pivotNode;
79        pivotNode.parent = leftChild;
80    }
81
82    // Swap colors between two nodes
83    swapColor(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
84        const tempColor = node1.color;
85        node1.color = node2.color;
86        node2.color = tempColor;
87    }
88
89    // Swap data between two nodes
90    swapData(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
91        const tempData = node1.data;
92        node1.data = node2.data;
93        node2.data = tempData;
94    }
95
96    // Fix Red-Black Tree violations after insertion
97    fixAfterInsert(currentNode: RBTreeNode<T>): void {
98        let parentNode = null;
99        let grandParentNode = null;
100
101        // Continue fixing while violations exist
102        while (currentNode !== this.root && currentNode.color !== 1 && currentNode.parent?.color === 0) {
103            parentNode = currentNode.parent;
104            grandParentNode = currentNode.parent.parent;
105
106            // Case A: Parent is left child of grandparent
107            if (parentNode === grandParentNode?.left) {
108                const uncleNode = grandParentNode.right;
109
110                // Case 1: Uncle is red - only recoloring needed
111                if (uncleNode && uncleNode.color === 0) {
112                    grandParentNode.color = 0;
113                    parentNode.color = 1;
114                    uncleNode.color = 1;
115                    currentNode = grandParentNode;
116                } else {
117                    // Case 2: Current node is right child - left rotation needed
118                    if (currentNode === parentNode.right) {
119                        this.rotateLeft(parentNode);
120                        currentNode = parentNode;
121                        parentNode = currentNode.parent;
122                    }
123
124                    // Case 3: Current node is left child - right rotation needed
125                    this.rotateRight(grandParentNode);
126                    this.swapColor(parentNode!, grandParentNode);
127                    currentNode = parentNode!;
128                }
129            } else {
130                // Case B: Parent is right child of grandparent
131                const uncleNode = grandParentNode!.left;
132
133                // Case 1: Uncle is red - only recoloring needed
134                if (uncleNode != null && uncleNode.color === 0) {
135                    grandParentNode!.color = 0;
136                    parentNode.color = 1;
137                    uncleNode.color = 1;
138                    currentNode = grandParentNode!;
139                } else {
140                    // Case 2: Current node is left child - right rotation needed
141                    if (currentNode === parentNode.left) {
142                        this.rotateRight(parentNode);
143                        currentNode = parentNode;
144                        parentNode = currentNode.parent;
145                    }
146
147                    // Case 3: Current node is right child - left rotation needed
148                    this.rotateLeft(grandParentNode!);
149                    this.swapColor(parentNode!, grandParentNode!);
150                    currentNode = parentNode!;
151                }
152            }
153        }
154        this.root!.color = 1; // Root must always be black
155    }
156
157    // Delete a single occurrence of value
158    delete(value: T): boolean {
159        const nodeToDelete = this.find(value);
160        if (!nodeToDelete) return false;
161        nodeToDelete.count--;
162        if (!nodeToDelete.count) this.deleteNode(nodeToDelete);
163        return true;
164    }
165
166    // Delete all occurrences of value
167    deleteAll(value: T): boolean {
168        const nodeToDelete = this.find(value);
169        if (!nodeToDelete) return false;
170        this.deleteNode(nodeToDelete);
171        return true;
172    }
173
174    // Delete a node from the tree
175    deleteNode(nodeToDelete: RBTreeNode<T>): void {
176        // Helper function to find BST replacement node
177        function findBSTReplacement(node: RBTreeNode<T>): RBTreeNode<T> | null {
178            // Node has 2 children - find inorder successor
179            if (node.left && node.right) return findSuccessor(node.right);
180            // Node is leaf
181            if (!node.left && !node.right) return null;
182            // Node has single child
183            return node.left ?? node.right;
184        }
185
186        // Helper function to find inorder successor
187        function findSuccessor(node: RBTreeNode<T>): RBTreeNode<T> {
188            let current = node;
189            while (current.left) current = current.left;
190            return current;
191        }
192
193        const replacementNode = findBSTReplacement(nodeToDelete);
194        // True when both nodes are black
195        const bothBlack = (replacementNode === null || replacementNode.color === 1) && nodeToDelete.color === 1;
196        const parentNode = nodeToDelete.parent!;
197
198        if (!replacementNode) {
199            // Node to delete is a leaf
200            if (nodeToDelete === this.root) {
201                this.root = null; // Tree becomes empty
202            } else {
203                if (bothBlack) {
204                    // Both nodes are black - fix double black
205                    this.fixDoubleBlack(nodeToDelete);
206                } else {
207                    // One node is red - make sibling red if exists
208                    if (nodeToDelete.sibling()) {
209                        nodeToDelete.sibling()!.color = 0;
210                    }
211                }
212                // Remove node from tree
213                if (nodeToDelete.isOnLeft()) parentNode.left = null;
214                else parentNode.right = null;
215            }
216            return;
217        }
218
219        if (!nodeToDelete.left || !nodeToDelete.right) {
220            // Node has exactly one child
221            if (nodeToDelete === this.root) {
222                // Replace root's data and remove child
223                nodeToDelete.data = replacementNode.data;
224                nodeToDelete.left = nodeToDelete.right = null;
225            } else {
226                // Replace node with its child
227                if (nodeToDelete.isOnLeft()) parentNode.left = replacementNode;
228                else parentNode.right = replacementNode;
229                replacementNode.parent = parentNode;
230              
231                if (bothBlack) this.fixDoubleBlack(replacementNode);
232                else replacementNode.color = 1; // Make replacement black
233            }
234            return;
235        }
236
237        // Node has 2 children - swap with successor and recurse
238        this.swapData(replacementNode, nodeToDelete);
239        this.deleteNode(replacementNode);
240    }
241
242    // Fix double black violation after deletion
243    fixDoubleBlack(doubleBlackNode: RBTreeNode<T>): void {
244        if (doubleBlackNode === this.root) return; // Reached root
245
246        const siblingNode = doubleBlackNode.sibling();
247        const parentNode = doubleBlackNode.parent!;
248      
249        if (!siblingNode) {
250            // No sibling - push double black up
251            this.fixDoubleBlack(parentNode);
252        } else {
253            if (siblingNode.color === 0) {
254                // Sibling is red
255                parentNode.color = 0;
256                siblingNode.color = 1;
257                if (siblingNode.isOnLeft()) this.rotateRight(parentNode);
258                else this.rotateLeft(parentNode);
259                this.fixDoubleBlack(doubleBlackNode);
260            } else {
261                // Sibling is black
262                if (siblingNode.hasRedChild()) {
263                    // Sibling has at least one red child
264                    if (siblingNode.left && siblingNode.left.color === 0) {
265                        if (siblingNode.isOnLeft()) {
266                            // Left-left case
267                            siblingNode.left.color = siblingNode.color;
268                            siblingNode.color = parentNode.color;
269                            this.rotateRight(parentNode);
270                        } else {
271                            // Right-left case
272                            siblingNode.left.color = parentNode.color;
273                            this.rotateRight(siblingNode);
274                            this.rotateLeft(parentNode);
275                        }
276                    } else {
277                        if (siblingNode.isOnLeft()) {
278                            // Left-right case
279                            siblingNode.right!.color = parentNode.color;
280                            this.rotateLeft(siblingNode);
281                            this.rotateRight(parentNode);
282                        } else {
283                            // Right-right case
284                            siblingNode.right!.color = siblingNode.color;
285                            siblingNode.color = parentNode.color;
286                            this.rotateLeft(parentNode);
287                        }
288                    }
289                    parentNode.color = 1;
290                } else {
291                    // Sibling has two black children
292                    siblingNode.color = 0;
293                    if (parentNode.color === 1) this.fixDoubleBlack(parentNode);
294                    else parentNode.color = 1;
295                }
296            }
297        }
298    }
299
300    // Insert a new value into the tree
301    insert(data: T): boolean {
302        // Find insertion position
303        let parentNode = this.root;
304        while (parentNode) {
305            if (this.lessThan(data, parentNode.data)) {
306                if (!parentNode.left) break;
307                else parentNode = parentNode.left;
308            } else if (this.lessThan(parentNode.data, data)) {
309                if (!parentNode.right) break;
310                else parentNode = parentNode.right;
311            } else break;
312        }
313
314        // Create and insert new node
315        const newNode = new RBTreeNode(data);
316        if (!parentNode) {
317            this.root = newNode;
318        } else if (this.lessThan(newNode.data, parentNode.data)) {
319            parentNode.left = newNode;
320        } else if (this.lessThan(parentNode.data, newNode.data)) {
321            parentNode.right = newNode;
322        } else {
323            // Value already exists - increment count
324            parentNode.count++;
325            return false;
326        }
327        newNode.parent = parentNode;
328        this.fixAfterInsert(newNode);
329        return true;
330    }
331
332    // Find a node with given value
333    find(data: T): RBTreeNode<T> | null {
334        let currentNode = this.root;
335        while (currentNode) {
336            if (this.lessThan(data, currentNode.data)) {
337                currentNode = currentNode.left;
338            } else if (this.lessThan(currentNode.data, data)) {
339                currentNode = currentNode.right;
340            } else break;
341        }
342        return currentNode ?? null;
343    }
344
345    // In-order traversal generator
346    *inOrder(rootNode: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
347        if (!rootNode) return;
348        for (const value of this.inOrder(rootNode.left!)) yield value;
349        yield rootNode.data;
350        for (const value of this.inOrder(rootNode.right!)) yield value;
351    }
352
353    // Reverse in-order traversal generator
354    *reverseInOrder(rootNode: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
355        if (!rootNode) return;
356        for (const value of this.reverseInOrder(rootNode.right!)) yield value;
357        yield rootNode.data;
358        for (const value of this.reverseInOrder(rootNode.left!)) yield value;
359    }
360}
361
362// TreeSet wrapper class for Red-Black Tree
363class TreeSet<T = number> {
364    private _size: number;
365    private tree: RBTree<T>;
366    private compare: Compare<T>;
367  
368    constructor(
369        collection: T[] | Compare<T> = [],
370        compare: Compare<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0),
371    ) {
372        if (typeof collection === 'function') {
373            compare = collection;
374            collection = [];
375        }
376        this._size = 0;
377        this.compare = compare;
378        this.tree = new RBTree(compare);
379        for (const value of collection) this.add(value);
380    }
381
382    // Get the size of the set
383    size(): number {
384        return this._size;
385    }
386
387    // Check if value exists in the set
388    has(value: T): boolean {
389        return !!this.tree.find(value);
390    }
391
392    // Add a value to the set
393    add(value: T): boolean {
394        const wasSuccessful = this.tree.insert(value);
395        this._size += wasSuccessful ? 1 : 0;
396        return wasSuccessful;
397    }
398
399    // Delete a value from the set
400    delete(value: T): boolean {
401        const wasDeleted = this.tree.deleteAll(value);
402        this._size -= wasDeleted ? 1 : 0;
403        return wasDeleted;
404    }
405
406    // Find smallest value >= given value
407    ceil(value: T): T | undefined {
408        let currentNode = this.tree.root;
409        let ceilingNode = null;
410        while (currentNode) {
411            if (this.compare(currentNode.data, value) >= 0) {
412                ceilingNode = currentNode;
413                currentNode = currentNode.left;
414            } else {
415                currentNode = currentNode.right;
416            }
417        }
418        return ceilingNode?.data;
419    }
420
421    // Find largest value <= given value
422    floor(value: T): T | undefined {
423        let currentNode = this.tree.root;
424        let floorNode = null;
425        while (currentNode) {
426            if (this.compare(value, currentNode.data) >= 0) {
427                floorNode = currentNode;
428                currentNode = currentNode.right;
429            } else {
430                currentNode = currentNode.left;
431            }
432        }
433        return floorNode?.data;
434    }
435
436    // Find smallest value > given value
437    higher(value: T): T | undefined {
438        let currentNode = this.tree.root;
439        let higherNode = null;
440        while (currentNode) {
441            if (this.compare(value, currentNode.data) < 0) {
442                higherNode = currentNode;
443                currentNode = currentNode.left;
444            } else {
445                currentNode = currentNode.right;
446            }
447        }
448        return higherNode?.data;
449    }
450
451    // Find largest value < given value
452    lower(value: T): T | undefined {
453        let currentNode = this.tree.root;
454        let lowerNode = null;
455        while (currentNode) {
456            if (this.compare(currentNode.data, value) < 0) {
457                lowerNode = currentNode;
458                currentNode = currentNode.right;
459            } else {
460                currentNode = currentNode.left;
461            }
462        }
463        return lowerNode?.data;
464    }
465
466    // Get the minimum value
467    first(): T | undefined {
468        return this.tree.inOrder().next().value;
469    }
470
471    // Get the maximum value
472    last(): T | undefined {
473        return this.tree.reverseInOrder().next().value;
474    }
475
476    // Remove and return the minimum value
477    shift(): T | undefined {
478        const firstValue = this.first();
479        if (firstValue === undefined) return undefined;
480        this.delete(firstValue);
481        return firstValue;
482    }
483
484    // Remove and return the maximum value
485    pop(): T | undefined {
486        const lastValue = this.last();
487        if (lastValue === undefined) return undefined;
488        this.delete(lastValue);
489        return lastValue;
490    }
491
492    // Iterator protocol
493    *[Symbol.iterator](): Generator<T, void, void> {
494        for (const value of this.values()) yield value;
495    }
496
497    // Get keys iterator (same as values for a set)
498    *keys(): Generator<T, void, void> {
499        for (const value of this.values()) yield value;
500    }
501
502    // Get values iterator
503    *values(): Generator<T, undefined, void> {
504        for (const value of this.tree.inOrder()) yield value;
505        return undefined;
506    }
507
508    // Get reverse order values iterator
509    *rvalues(): Generator<T, undefined, void> {
510        for (const value of this.tree.reverseInOrder()) yield value;
511        return undefined;
512    }
513}
514
515// ExamRoom class - manages seat allocation in an exam room
516class ExamRoom {
517    // TreeSet to store intervals sorted by distance (priority queue)
518    private intervalSet: TreeSet<number[]> = new TreeSet<number[]>((interval1, interval2) => {
519        const distance1 = this.calculateDistance(interval1);
520        const distance2 = this.calculateDistance(interval2);
521        // Sort by distance (descending), then by start position (ascending)
522        return distance1 === distance2 ? interval1[0] - interval2[0] : distance2 - distance1;
523    });
524    // Map to track left neighbor of each position
525    private leftNeighbor: Map<number, number> = new Map();
526    // Map to track right neighbor of each position
527    private rightNeighbor: Map<number, number> = new Map();
528    // Total number of seats
529    private totalSeats: number;
530
531    constructor(n: number) {
532        this.totalSeats = n;
533        // Initialize with full range (-1 to n as virtual boundaries)
534        this.addInterval([-1, n]);
535    }
536
537    // Allocate a seat to maximize distance from others
538    seat(): number {
539        // Get the interval with maximum distance
540        const bestInterval = this.intervalSet.first();
541      
542        // Calculate seat position
543        let seatPosition = Math.floor((bestInterval[0] + bestInterval[1]) / 2);
544      
545        // Handle edge cases for first and last seats
546        if (bestInterval[0] === -1) {
547            seatPosition = 0; // Take first seat
548        } else if (bestInterval[1] === this.totalSeats) {
549            seatPosition = this.totalSeats - 1; // Take last seat
550        }
551      
552        // Remove the current interval and add two new intervals
553        this.removeInterval(bestInterval);
554        this.addInterval([bestInterval[0], seatPosition]);
555        this.addInterval([seatPosition, bestInterval[1]]);
556      
557        return seatPosition;
558    }
559
560    // Free a seat when student leaves
561    leave(position: number): void {
562        // Get neighboring positions
563        const leftPosition = this.leftNeighbor.get(position)!;
564        const rightPosition = this.rightNeighbor.get(position)!;
565      
566        // Remove the two intervals adjacent to this position
567        this.removeInterval([leftPosition, position]);
568        this.removeInterval([position, rightPosition]);
569      
570        // Add merged interval
571        this.addInterval([leftPosition, rightPosition]);
572    }
573
574    // Calculate the effective distance for an interval
575    private calculateDistance(interval: number[]): number {
576        const [left, right] = interval;
577        // Edge intervals have full distance minus 1
578        if (left === -1 || right === this.totalSeats) {
579            return right - left - 1;
580        }
581        // Interior intervals have half distance (rounded down)
582        return Math.floor((right - left) / 2);
583    }
584
585    // Add an interval to the data structures
586    private addInterval(interval: number[]): void {
587        this.intervalSet.add(interval);
588        this.leftNeighbor.set(interval[1], interval[0]);
589        this.rightNeighbor.set(interval[0], interval[1]);
590    }
591
592    // Remove an interval from the data structures
593    private removeInterval(interval: number[]): void {
594        this.intervalSet.delete(interval);
595        this.leftNeighbor.delete(interval[1]);
596        this.rightNeighbor.delete(interval[0]);
597    }
598}
599

Time and Space Complexity

Time Complexity:

__init__: O(log n) - Adding one initial segment (-1, n) to the SortedList takes O(log n) time.
seat(): O(log n) - Accessing the first element is O(1), but removing one segment and adding two new segments each take O(log n) time in the SortedList.
leave(p): O(log n) - Looking up adjacent segments using the dictionaries is O(1), but removing two segments and adding one merged segment each take O(log n) time in the SortedList.

Space Complexity: O(n)

The SortedList can contain at most n segments (when every seat is occupied, there would be n+1 segments including boundaries).
The left and right dictionaries each store at most O(n) key-value pairs.
Therefore, the overall space complexity is O(n).

The key insight is that the SortedList maintains segments sorted by their "distance" value (which represents how far a new student would be from others if seated in that segment). The custom sorting key (-dist(x), x[0]) ensures segments are ordered by maximum distance first, with ties broken by leftmost position. Operations on the SortedList (add/remove) have O(log n) complexity due to the underlying balanced tree structure.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Distance Calculation for Middle Seats

One of the most common mistakes is incorrectly calculating where to sit in an internal interval. When an interval (l, r) is not at a boundary, students often make these errors:

Pitfall Example:

# WRONG: Using floor division can give incorrect position for odd-length intervals
position = l + (r - l) // 2  

# WRONG: Off-by-one error
position = (l + r - 1) // 2

Why it's wrong: For interval (2, 7), the available seats are 3, 4, 5, 6. The middle position should be 4 or 5 (both give distance 2 from boundaries). Using (2 + 7) // 2 = 4 is correct, but some might incorrectly calculate it as 2 + (7-2)//2 = 4 which happens to work here but fails in other cases.

Solution:

# CORRECT: Direct average gives the right middle position
position = (l + r) >> 1  # or (l + r) // 2

2. Misunderstanding Boundary Interval Distance

Another critical pitfall is incorrectly calculating the distance for boundary intervals (-1, r) or (l, n).

Pitfall Example:

def dist(segment):
    l, r = segment
    # WRONG: Treating all intervals the same way
    return (r - l) // 2  # This is incorrect for boundary intervals!

Why it's wrong: For boundary interval (-1, 5), if we use (5 - (-1)) // 2 = 3, but a student sitting at position 0 would actually have distance 4 from the next person at position 5.

Solution:

def dist(segment):
    l, r = segment
    if l == -1 or r == n:
        # Boundary intervals: student sits at the edge
        return r - l - 1
    else:
        # Internal intervals: student sits in the middle
        return (r - l) >> 1

3. Forgetting to Handle Empty Room Edge Case

While the interval-based approach naturally handles the empty room case through the initial (-1, n) interval, some implementations might try to handle it separately and create inconsistencies.

Pitfall Example:

def seat(self):
    # WRONG: Redundant special case that might conflict with interval logic
    if len(self.occupied_seats) == 0:
        self.occupied_seats.add(0)
        return 0
  
    # ... rest of the interval logic

Why it's wrong: This creates a separate code path that might not properly update the interval data structures, leading to inconsistencies.

Solution: Let the interval logic handle it naturally. The initial (-1, n) interval with the distance calculation will automatically place the first student at seat 0.

4. Incorrect Interval Sorting for Tie-Breaking

When multiple intervals have the same maximum distance, the tie should be broken by choosing the interval with the smallest starting position.

Pitfall Example:

# WRONG: Sorting only by distance
self.sorted_segments = SortedList(key=lambda s: -calculate_distance(s))

# WRONG: Incorrect tie-breaking order
self.sorted_segments = SortedList(key=lambda s: (-calculate_distance(s), s[1]))  # Using right boundary

Why it's wrong: If intervals (1, 5) and (6, 10) both have distance 2, we should choose (1, 5) first (student sits at position 3) rather than (6, 10) (student sits at position 8).

Solution:

# CORRECT: Sort by negative distance (descending), then by left boundary (ascending)
self.sorted_segments = SortedList(key=lambda s: (-calculate_distance(s), s[0]))

5. Memory Leak from Hash Table Entries

Forgetting to clean up the hash table entries when deleting segments can lead to memory leaks and incorrect lookups.

Pitfall Example:

def _delete_segment(self, segment):
    self.sorted_segments.remove(segment)
    # WRONG: Forgetting to remove hash table entries
    # This leaves orphaned entries that could cause errors later

Solution:

def _delete_segment(self, segment):
    self.sorted_segments.remove(segment)
    self.left_boundary.pop(segment[1])   # Clean up right boundary mapping
    self.right_boundary.pop(segment[0])  # Clean up left boundary mapping

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

A graph is a special tree

A tree is a special graph

No relationship

They are the same thing

I don't know

855. Exam Room

Problem Description

Intuition

Solution Approach

Data Structures

Initialization

Seat Assignment

Student Leaving

Helper Methods

Time Complexity

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Incorrect Distance Calculation for Middle Seats

2. Misunderstanding Boundary Interval Distance

3. Forgetting to Handle Empty Room Edge Case

4. Incorrect Interval Sorting for Tie-Breaking

5. Memory Leak from Hash Table Entries

Recommended Readings