855. Exam Room
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 withn
seatsint 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 seatp
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 isr - 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.
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 seats0
and1
(2, 7)
: representing seats3
,4
,5
,6
(7, n)
: representing seats from8
ton-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 atn
), the student would sit at the edge (seat0
or seatn-1
), giving distancer - 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
orr == n
): distance =r - l - 1
- For internal intervals: distance =
(r - l) >> 1
(equivalent to(r - l) // 2
)
-
Hash Tables (
left
andright
):left[p]
: stores the left boundary of the interval ending at positionp
right[p]
: stores the right boundary of the interval starting at positionp
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 operationsleave(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 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 takesO(log n)
time.seat()
:O(log n)
- Accessing the first element isO(1)
, but removing one segment and adding two new segments each takeO(log n)
time in the SortedList.leave(p)
:O(log n)
- Looking up adjacent segments using the dictionaries isO(1)
, but removing two segments and adding one merged segment each takeO(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 ben+1
segments including boundaries). - The
left
andright
dictionaries each store at mostO(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
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
https assets algo monster cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue is a data structure
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!