2286. Booking Concert Tickets in Groups

HardDesignBinary Indexed TreeSegment TreeBinary Search

Problem Description

You need to design a ticketing system for a concert hall with n rows (numbered 0 to n-1) and m seats per row (numbered 0 to m-1).

The system must handle two types of booking requests:

1. Group booking (gather): A group of k people wants to sit together in the same row.

They will only book if all k members can sit in consecutive seats in a single row
The row number must be ≤ maxRow
If multiple rows are available, choose the row with the smallest number
Within a row, choose the leftmost available consecutive seats

2. Scattered booking (scatter): A group of k people can sit separately.

They will only book if all k members can get seats (not necessarily together)
All seats must be in rows numbered ≤ maxRow
Allocate seats starting from the smallest row numbers
Within each row, allocate from the smallest seat numbers

You need to implement a BookMyShow class with three methods:

BookMyShow(n, m): Initialize with n rows and m seats per row
gather(k, maxRow): Try to book k consecutive seats in a single row (row ≤ maxRow). Returns [row, seat] indicating the row number and starting seat number if successful, or empty array [] if not possible
scatter(k, maxRow): Try to book k seats total across rows 0 to maxRow (seats don't need to be together). Returns true if successful and allocates the seats, false otherwise

The key challenge is efficiently tracking available seats and finding optimal allocations according to the "smallest row first, smallest seat first" rule while handling potentially large numbers of rows and frequent booking operations.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The core challenge is efficiently tracking available seats across all rows and quickly finding rows that meet specific criteria. Let's think about what operations we need:

For gather(k, maxRow), we need to find the smallest row number that has at least k consecutive empty seats. This means we need to quickly query "what's the maximum number of available seats in rows 0 to maxRow?" and "which is the first row with at least k available seats?"

For scatter(k, maxRow), we need to check if the total available seats in rows 0 to maxRow is at least k, then greedily fill seats starting from the smallest row numbers.

If we use a simple array to track available seats per row, finding the first row with enough seats would take O(n) time for each query, which could be inefficient for large n.

The key insight is that we need two types of range queries:

Range maximum query: Find the row with the most available seats in a range (for gather)
Range sum query: Calculate total available seats in a range (for scatter)

Both operations also require point updates when we book seats in a specific row.

This pattern - range queries with point updates - is a classic use case for a Segment Tree. A segment tree can handle both types of queries in O(log n) time.

In our segment tree, each node stores:

s: sum of available seats in its range (for checking total availability)
mx: maximum available seats in any single row within its range (for finding rows that can accommodate a group)

For gather, we use the segment tree to find the leftmost row with mx >= k, then update that row's available seats.

For scatter, we first check if the sum of available seats is sufficient, then greedily allocate seats row by row, starting from the first row that has any available seats.

The segment tree structure allows us to efficiently maintain and query this information as bookings are made, reducing query complexity from O(n) to O(log n).

Learn more about Segment Tree and Binary Search patterns.

Solution Implementation

1from typing import List, Optional 2 3 4class SegmentTreeNode: 5 """Node for segment tree storing range information and statistics.""" 6 __slots__ = "left", "right", "sum", "max_value" 7 8 def __init__(self): 9 self.left = 0 # Left boundary of range 10 self.right = 0 # Right boundary of range 11 self.sum = 0 # Sum of available seats in range 12 self.max_value = 0 # Maximum available seats in any row within range 13 14 15class SegmentTree: 16 """Segment tree for efficient range queries and updates on row seat availability.""" 17 18 def __init__(self, num_rows: int, seats_per_row: int): 19 """ 20 Initialize segment tree for venue with given dimensions. 21 22 Args: 23 num_rows: Number of rows in the venue 24 seats_per_row: Number of seats in each row 25 """ 26 self.seats_per_row = seats_per_row 27 # Allocate 4n nodes for complete binary tree representation 28 self.nodes = [SegmentTreeNode() for _ in range(num_rows << 2)] 29 self._build(1, 1, num_rows) 30 31 def _build(self, node_idx: int, left: int, right: int) -> None: 32 """ 33 Recursively build the segment tree. 34 35 Args: 36 node_idx: Current node index in tree array 37 left: Left boundary of current range 38 right: Right boundary of current range 39 """ 40 self.nodes[node_idx].left = left 41 self.nodes[node_idx].right = right 42 43 if left == right: 44 # Leaf node: initialize with full row capacity 45 self.nodes[node_idx].sum = self.seats_per_row 46 self.nodes[node_idx].max_value = self.seats_per_row 47 return 48 49 mid = (left + right) >> 1 50 left_child = node_idx << 1 51 right_child = (node_idx << 1) | 1 52 53 # Build left and right subtrees 54 self._build(left_child, left, mid) 55 self._build(right_child, mid + 1, right) 56 57 # Update current node based on children 58 self._push_up(node_idx) 59 60 def modify(self, node_idx: int, target_row: int, new_value: int) -> None: 61 """ 62 Update the available seats for a specific row. 63 64 Args: 65 node_idx: Current node index in tree traversal 66 target_row: Row number to update (1-indexed) 67 new_value: New number of available seats 68 """ 69 current_node = self.nodes[node_idx] 70 71 if current_node.left == target_row and current_node.right == target_row: 72 # Found target leaf node 73 current_node.sum = new_value 74 current_node.max_value = new_value 75 return 76 77 mid = (current_node.left + current_node.right) >> 1 78 left_child = node_idx << 1 79 right_child = (node_idx << 1) | 1 80 81 # Recursively update appropriate subtree 82 if target_row <= mid: 83 self.modify(left_child, target_row, new_value) 84 else: 85 self.modify(right_child, target_row, new_value) 86 87 # Update current node based on modified children 88 self._push_up(node_idx) 89 90 def query_sum(self, node_idx: int, query_left: int, query_right: int) -> int: 91 """ 92 Query the total available seats in a range of rows. 93 94 Args: 95 node_idx: Current node index in tree traversal 96 query_left: Left boundary of query range (1-indexed) 97 query_right: Right boundary of query range (1-indexed) 98 99 Returns: 100 Total available seats in the specified range 101 """ 102 current_node = self.nodes[node_idx] 103 104 # Current range completely within query range 105 if current_node.left >= query_left and current_node.right <= query_right: 106 return current_node.sum 107 108 mid = (current_node.left + current_node.right) >> 1 109 left_child = node_idx << 1 110 right_child = (node_idx << 1) | 1 111 total = 0 112 113 # Query left subtree if overlap exists 114 if query_left <= mid: 115 total += self.query_sum(left_child, query_left, query_right) 116 117 # Query right subtree if overlap exists 118 if query_right > mid: 119 total += self.query_sum(right_child, query_left, query_right) 120 121 return total 122 123 def query_idx(self, node_idx: int, query_left: int, query_right: int, min_seats: int) -> int: 124 """ 125 Find the first row with at least min_seats available seats. 126 127 Args: 128 node_idx: Current node index in tree traversal 129 query_left: Left boundary of query range (1-indexed) 130 query_right: Right boundary of query range (1-indexed) 131 min_seats: Minimum number of required seats 132 133 Returns: 134 Row number (1-indexed) of first suitable row, or 0 if none found 135 """ 136 current_node = self.nodes[node_idx] 137 138 # No row in this range has enough seats 139 if current_node.max_value < min_seats: 140 return 0 141 142 # Leaf node with enough seats 143 if current_node.left == current_node.right: 144 return current_node.left 145 146 mid = (current_node.left + current_node.right) >> 1 147 left_child = node_idx << 1 148 right_child = (node_idx << 1) | 1 149 150 # Check left subtree first (prefer earlier rows) 151 if self.nodes[left_child].max_value >= min_seats: 152 return self.query_idx(left_child, query_left, query_right, min_seats) 153 154 # Check right subtree if needed 155 if query_right > mid: 156 return self.query_idx(right_child, query_left, query_right, min_seats) 157 158 return 0 159 160 def _push_up(self, node_idx: int) -> None: 161 """ 162 Update parent node based on children's values. 163 164 Args: 165 node_idx: Index of parent node to update 166 """ 167 left_child = node_idx << 1 168 right_child = (node_idx << 1) | 1 169 170 # Sum is total of both children 171 self.nodes[node_idx].sum = ( 172 self.nodes[left_child].sum + self.nodes[right_child].sum 173 ) 174 175 # Max is maximum of both children 176 self.nodes[node_idx].max_value = max( 177 self.nodes[left_child].max_value, 178 self.nodes[right_child].max_value 179 ) 180 181 182class BookMyShow: 183 """System for booking seats in a show venue with multiple rows.""" 184 185 def __init__(self, n: int, m: int): 186 """ 187 Initialize the booking system. 188 189 Args: 190 n: Number of rows in the venue 191 m: Number of seats per row 192 """ 193 self.num_rows = n 194 self.segment_tree = SegmentTree(n, m) 195 196 def gather(self, k: int, maxRow: int) -> List[int]: 197 """ 198 Attempt to book k consecutive seats in a single row. 199 200 Args: 201 k: Number of consecutive seats to book 202 maxRow: Maximum row index to consider (0-indexed) 203 204 Returns: 205 [row_index, starting_seat] if successful, empty list otherwise 206 """ 207 # Convert to 1-indexed for segment tree 208 max_row_inclusive = maxRow + 1 209 210 # Find first row with at least k available seats 211 row_number = self.segment_tree.query_idx(1, 1, max_row_inclusive, k) 212 213 if row_number == 0: 214 return [] 215 216 # Get current available seats in found row 217 available_seats = self.segment_tree.query_sum(1, row_number, row_number) 218 219 # Book the seats by reducing available count 220 self.segment_tree.modify(1, row_number, available_seats - k) 221 222 # Return 0-indexed row and starting seat position 223 starting_seat = self.segment_tree.seats_per_row - available_seats 224 return [row_number - 1, starting_seat] 225 226 def scatter(self, k: int, maxRow: int) -> bool: 227 """ 228 Attempt to book k seats, possibly across multiple rows. 229 230 Args: 231 k: Number of seats to book 232 maxRow: Maximum row index to consider (0-indexed) 233 234 Returns: 235 True if booking successful, False otherwise 236 """ 237 # Convert to 1-indexed for segment tree 238 max_row_inclusive = maxRow + 1 239 240 # Check if enough total seats available 241 total_available = self.segment_tree.query_sum(1, 1, max_row_inclusive) 242 if total_available < k: 243 return False 244 245 # Find first row with at least one available seat 246 first_available_row = self.segment_tree.query_idx(1, 1, max_row_inclusive, 1) 247 248 # Book seats row by row, starting from first available 249 remaining_to_book = k 250 for row_number in range(first_available_row, self.num_rows + 1): 251 available_in_row = self.segment_tree.query_sum(1, row_number, row_number) 252 253 if available_in_row >= remaining_to_book: 254 # Can finish booking in this row 255 self.segment_tree.modify(1, row_number, available_in_row - remaining_to_book) 256 return True 257 258 # Book all available seats in this row 259 remaining_to_book -= available_in_row 260 self.segment_tree.modify(1, row_number, 0) 261 262 return True 263

1/** 2 * Node class for segment tree 3 * Stores information about a range of rows in the theater 4 */ 5class Node { 6 int left, right; // Range boundaries [left, right] 7 long maxSeats; // Maximum available seats in any single row within this range 8 long totalSeats; // Sum of all available seats in this range 9} 10 11/** 12 * Segment Tree implementation for efficient range queries and updates 13 * Used to manage available seats across theater rows 14 */ 15class SegmentTree { 16 private Node[] tree; 17 private int seatsPerRow; 18 19 /** 20 * Constructor for SegmentTree 21 * @param numRows Total number of rows in the theater 22 * @param seatsPerRow Number of seats per row 23 */ 24 public SegmentTree(int numRows, int seatsPerRow) { 25 this.seatsPerRow = seatsPerRow; 26 // Allocate 4 times the number of rows for segment tree nodes 27 tree = new Node[numRows << 2]; 28 for (int i = 0; i < tree.length; ++i) { 29 tree[i] = new Node(); 30 } 31 build(1, 1, numRows); 32 } 33 34 /** 35 * Recursively build the segment tree 36 * @param nodeIndex Current node index in the tree 37 * @param left Left boundary of current range 38 * @param right Right boundary of current range 39 */ 40 private void build(int nodeIndex, int left, int right) { 41 tree[nodeIndex].left = left; 42 tree[nodeIndex].right = right; 43 44 // Leaf node: single row 45 if (left == right) { 46 tree[nodeIndex].totalSeats = seatsPerRow; 47 tree[nodeIndex].maxSeats = seatsPerRow; 48 return; 49 } 50 51 // Build left and right subtrees 52 int mid = (left + right) >> 1; 53 build(nodeIndex << 1, left, mid); 54 build(nodeIndex << 1 | 1, mid + 1, right); 55 56 // Update current node based on children 57 pushup(nodeIndex); 58 } 59 60 /** 61 * Modify the number of available seats in a specific row 62 * @param nodeIndex Current node index in the tree 63 * @param targetRow The row to modify (1-indexed) 64 * @param newValue New number of available seats 65 */ 66 public void modify(int nodeIndex, int targetRow, long newValue) { 67 // Found the target leaf node 68 if (tree[nodeIndex].left == targetRow && tree[nodeIndex].right == targetRow) { 69 tree[nodeIndex].totalSeats = newValue; 70 tree[nodeIndex].maxSeats = newValue; 71 return; 72 } 73 74 // Recursively search in appropriate subtree 75 int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1; 76 if (targetRow <= mid) { 77 modify(nodeIndex << 1, targetRow, newValue); 78 } else { 79 modify(nodeIndex << 1 | 1, targetRow, newValue); 80 } 81 82 // Update current node after modification 83 pushup(nodeIndex); 84 } 85 86 /** 87 * Query the sum of available seats in range [left, right] 88 * @param nodeIndex Current node index in the tree 89 * @param queryLeft Left boundary of query range 90 * @param queryRight Right boundary of query range 91 * @return Total available seats in the range 92 */ 93 public long querySum(int nodeIndex, int queryLeft, int queryRight) { 94 // Current range is completely within query range 95 if (tree[nodeIndex].left >= queryLeft && tree[nodeIndex].right <= queryRight) { 96 return tree[nodeIndex].totalSeats; 97 } 98 99 int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1; 100 long sum = 0; 101 102 // Query left subtree if needed 103 if (queryLeft <= mid) { 104 sum += querySum(nodeIndex << 1, queryLeft, queryRight); 105 } 106 107 // Query right subtree if needed 108 if (queryRight > mid) { 109 sum += querySum(nodeIndex << 1 | 1, queryLeft, queryRight); 110 } 111 112 return sum; 113 } 114 115 /** 116 * Find the first row with at least k available seats 117 * @param nodeIndex Current node index in the tree 118 * @param queryLeft Left boundary of query range 119 * @param queryRight Right boundary of query range 120 * @param minSeats Minimum number of seats required 121 * @return Row index (1-indexed) or 0 if not found 122 */ 123 public int queryIdx(int nodeIndex, int queryLeft, int queryRight, int minSeats) { 124 // No row in this range has enough seats 125 if (tree[nodeIndex].maxSeats < minSeats) { 126 return 0; 127 } 128 129 // Found a leaf node with enough seats 130 if (tree[nodeIndex].left == tree[nodeIndex].right) { 131 return tree[nodeIndex].left; 132 } 133 134 int mid = (tree[nodeIndex].left + tree[nodeIndex].right) >> 1; 135 136 // Check left subtree first (prioritize earlier rows) 137 if (tree[nodeIndex << 1].maxSeats >= minSeats) { 138 return queryIdx(nodeIndex << 1, queryLeft, queryRight, minSeats); 139 } 140 141 // Check right subtree if needed 142 if (queryRight > mid) { 143 return queryIdx(nodeIndex << 1 | 1, queryLeft, queryRight, minSeats); 144 } 145 146 return 0; 147 } 148 149 /** 150 * Update parent node based on its children 151 * @param nodeIndex Current node index to update 152 */ 153 private void pushup(int nodeIndex) { 154 tree[nodeIndex].totalSeats = tree[nodeIndex << 1].totalSeats + tree[nodeIndex << 1 | 1].totalSeats; 155 tree[nodeIndex].maxSeats = Math.max(tree[nodeIndex << 1].maxSeats, tree[nodeIndex << 1 | 1].maxSeats); 156 } 157} 158 159/** 160 * Theater booking system that manages seat reservations 161 */ 162class BookMyShow { 163 private int numRows; 164 private int seatsPerRow; 165 private SegmentTree segmentTree; 166 167 /** 168 * Initialize the booking system 169 * @param n Number of rows in the theater 170 * @param m Number of seats per row 171 */ 172 public BookMyShow(int n, int m) { 173 this.numRows = n; 174 this.seatsPerRow = m; 175 segmentTree = new SegmentTree(n, m); 176 } 177 178 /** 179 * Try to book k consecutive seats in the same row 180 * @param k Number of consecutive seats to book 181 * @param maxRow Maximum row index (0-indexed) to consider 182 * @return Array [row, startSeat] if successful, empty array otherwise 183 */ 184 public int[] gather(int k, int maxRow) { 185 // Convert to 1-indexed for segment tree 186 ++maxRow; 187 188 // Find first row with at least k available seats 189 int rowIndex = segmentTree.queryIdx(1, 1, maxRow, k); 190 if (rowIndex == 0) { 191 return new int[] {}; 192 } 193 194 // Get current available seats in the found row 195 long availableSeats = segmentTree.querySum(1, rowIndex, rowIndex); 196 197 // Book the seats by reducing available count 198 segmentTree.modify(1, rowIndex, availableSeats - k); 199 200 // Return 0-indexed row and starting seat position 201 return new int[] {rowIndex - 1, (int) (seatsPerRow - availableSeats)}; 202 } 203 204 /** 205 * Try to book k seats, not necessarily consecutive 206 * @param k Number of seats to book 207 * @param maxRow Maximum row index (0-indexed) to consider 208 * @return true if booking successful, false otherwise 209 */ 210 public boolean scatter(int k, int maxRow) { 211 // Convert to 1-indexed for segment tree 212 ++maxRow; 213 214 // Check if enough total seats available 215 if (segmentTree.querySum(1, 1, maxRow) < k) { 216 return false; 217 } 218 219 // Find first row with at least one available seat 220 int startRow = segmentTree.queryIdx(1, 1, maxRow, 1); 221 222 // Greedily fill rows from front to back 223 for (int row = startRow; row <= numRows; ++row) { 224 long availableSeats = segmentTree.querySum(1, row, row); 225 226 if (availableSeats >= k) { 227 // Can fulfill remaining request in this row 228 segmentTree.modify(1, row, availableSeats - k); 229 return true; 230 } 231 232 // Use all seats in this row 233 k -= availableSeats; 234 segmentTree.modify(1, row, 0); 235 } 236 237 return true; 238 } 239} 240 241/** 242 * Your BookMyShow object will be instantiated and called as such: 243 * BookMyShow obj = new BookMyShow(n, m); 244 * int[] param_1 = obj.gather(k,maxRow); 245 * boolean param_2 = obj.scatter(k,maxRow); 246 */ 247

1class Node { 2public: 3 int left, right; // Range boundaries [left, right] 4 long sum, maxValue; // Sum and maximum value in this range 5}; 6 7class SegmentTree { 8public: 9 /** 10 * Constructor: Initialize segment tree with n rows, each with m seats 11 * @param n: number of rows 12 * @param m: number of seats per row 13 */ 14 SegmentTree(int n, int m) { 15 this->seatsPerRow = m; 16 tree.resize(n << 2); // Allocate 4n nodes for segment tree 17 for (int i = 0; i < n << 2; ++i) { 18 tree[i] = new Node(); 19 } 20 build(1, 1, n); 21 } 22 23 /** 24 * Update the number of available seats at position x to value 25 * @param nodeIdx: current node index in segment tree 26 * @param position: row position to update (1-indexed) 27 * @param value: new value for available seats 28 */ 29 void modify(int nodeIdx, int position, int value) { 30 // Base case: leaf node 31 if (tree[nodeIdx]->left == position && tree[nodeIdx]->right == position) { 32 tree[nodeIdx]->sum = tree[nodeIdx]->maxValue = value; 33 return; 34 } 35 36 // Recursive case: update left or right subtree 37 int mid = (tree[nodeIdx]->left + tree[nodeIdx]->right) >> 1; 38 if (position <= mid) { 39 modify(nodeIdx << 1, position, value); 40 } else { 41 modify(nodeIdx << 1 | 1, position, value); 42 } 43 pushUp(nodeIdx); 44 } 45 46 /** 47 * Query sum of available seats in range [left, right] 48 * @param nodeIdx: current node index 49 * @param left: left boundary of query range 50 * @param right: right boundary of query range 51 * @return sum of available seats in the range 52 */ 53 long querySum(int nodeIdx, int left, int right) { 54 // Current range is completely within query range 55 if (tree[nodeIdx]->left >= left && tree[nodeIdx]->right <= right) { 56 return tree[nodeIdx]->sum; 57 } 58 59 // Query left and/or right subtree based on overlap 60 int mid = (tree[nodeIdx]->left + tree[nodeIdx]->right) >> 1; 61 long result = 0; 62 if (left <= mid) { 63 result += querySum(nodeIdx << 1, left, right); 64 } 65 if (right > mid) { 66 result += querySum(nodeIdx << 1 | 1, left, right); 67 } 68 return result; 69 } 70 71 /** 72 * Find the first row index with at least k available seats 73 * @param nodeIdx: current node index 74 * @param left: left boundary (unused in current implementation) 75 * @param right: right boundary (unused in current implementation) 76 * @param k: minimum number of required seats 77 * @return row index (1-indexed) or 0 if not found 78 */ 79 int queryIdx(int nodeIdx, int left, int right, int k) { 80 // No row in this subtree has enough seats 81 if (tree[nodeIdx]->maxValue < k) { 82 return 0; 83 } 84 85 // Leaf node: this row has enough seats 86 if (tree[nodeIdx]->left == tree[nodeIdx]->right) { 87 return tree[nodeIdx]->left; 88 } 89 90 // Check left subtree first (prefer smaller row numbers) 91 int mid = (tree[nodeIdx]->left + tree[nodeIdx]->right) >> 1; 92 if (tree[nodeIdx << 1]->maxValue >= k) { 93 return queryIdx(nodeIdx << 1, left, right, k); 94 } 95 96 // Check right subtree if needed 97 if (right > mid) { 98 return queryIdx(nodeIdx << 1 | 1, left, right, k); 99 } 100 return 0; 101 } 102 103private: 104 vector<Node*> tree; 105 int seatsPerRow; 106 107 /** 108 * Build segment tree recursively 109 * @param nodeIdx: current node index 110 * @param left: left boundary of range 111 * @param right: right boundary of range 112 */ 113 void build(int nodeIdx, int left, int right) { 114 tree[nodeIdx]->left = left; 115 tree[nodeIdx]->right = right; 116 117 // Leaf node: initialize with full row capacity 118 if (left == right) { 119 tree[nodeIdx]->sum = seatsPerRow; 120 tree[nodeIdx]->maxValue = seatsPerRow; 121 return; 122 } 123 124 // Internal node: build left and right subtrees 125 int mid = (left + right) >> 1; 126 build(nodeIdx << 1, left, mid); 127 build(nodeIdx << 1 | 1, mid + 1, right); 128 pushUp(nodeIdx); 129 } 130 131 /** 132 * Update parent node based on children values 133 * @param nodeIdx: node index to update 134 */ 135 void pushUp(int nodeIdx) { 136 tree[nodeIdx]->sum = tree[nodeIdx << 1]->sum + tree[nodeIdx << 1 | 1]->sum; 137 tree[nodeIdx]->maxValue = max(tree[nodeIdx << 1]->maxValue, 138 tree[nodeIdx << 1 | 1]->maxValue); 139 } 140}; 141 142class BookMyShow { 143public: 144 /** 145 * Constructor: Initialize the booking system 146 * @param n: number of rows in the theater 147 * @param m: number of seats per row 148 */ 149 BookMyShow(int n, int m) { 150 this->numRows = n; 151 this->seatsPerRow = m; 152 segmentTree = new SegmentTree(n, m); 153 } 154 155 /** 156 * Try to allocate k consecutive seats in the same row 157 * @param k: number of consecutive seats needed 158 * @param maxRow: maximum row index allowed (0-indexed) 159 * @return {row_index, starting_seat} if successful, empty vector otherwise 160 */ 161 vector<int> gather(int k, int maxRow) { 162 ++maxRow; // Convert to 1-indexed 163 164 // Find first row with at least k available seats 165 int rowIdx = segmentTree->queryIdx(1, 1, maxRow, k); 166 if (rowIdx == 0) { 167 return {}; // No suitable row found 168 } 169 170 // Allocate seats in the found row 171 long availableSeats = segmentTree->querySum(1, rowIdx, rowIdx); 172 segmentTree->modify(1, rowIdx, availableSeats - k); 173 174 // Return 0-indexed row and starting seat position 175 return {rowIdx - 1, (int)(seatsPerRow - availableSeats)}; 176 } 177 178 /** 179 * Try to allocate k seats, can be scattered across multiple rows 180 * @param k: total number of seats needed 181 * @param maxRow: maximum row index allowed (0-indexed) 182 * @return true if allocation successful, false otherwise 183 */ 184 bool scatter(int k, int maxRow) { 185 ++maxRow; // Convert to 1-indexed 186 187 // Check if enough total seats available 188 if (segmentTree->querySum(1, 1, maxRow) < k) { 189 return false; 190 } 191 192 // Find first non-empty row 193 int startRow = segmentTree->queryIdx(1, 1, maxRow, 1); 194 195 // Allocate seats row by row 196 for (int row = startRow; row <= numRows; ++row) { 197 long availableSeats = segmentTree->querySum(1, row, row); 198 199 if (availableSeats >= k) { 200 // Can satisfy remaining demand with this row 201 segmentTree->modify(1, row, availableSeats - k); 202 return true; 203 } 204 205 // Use all seats in this row 206 k -= availableSeats; 207 segmentTree->modify(1, row, 0); 208 } 209 210 return true; 211 } 212 213private: 214 SegmentTree* segmentTree; 215 int seatsPerRow; 216 int numRows; 217}; 218 219/** 220 * Your BookMyShow object will be instantiated and called as such: 221 * BookMyShow* obj = new BookMyShow(n, m); 222 * vector<int> param_1 = obj->gather(k,maxRow); 223 * bool param_2 = obj->scatter(k,maxRow); 224 */ 225

1// Node structure for segment tree 2interface SegmentTreeNode { 3 left: number; // Left boundary of the range 4 right: number; // Right boundary of the range 5 max: number; // Maximum value in the range 6 sum: number; // Sum of values in the range 7} 8 9// Global variables 10let segmentTree: SegmentTreeNode[] = []; 11let seatsPerRow: number = 0; 12let totalRows: number = 0; 13 14// Initialize the booking system 15function initializeBookingSystem(n: number, m: number): void { 16 totalRows = n; 17 seatsPerRow = m; 18 // Allocate space for segment tree (4 times the number of rows) 19 segmentTree = Array.from({ length: n << 2 }, () => ({ 20 left: 0, 21 right: 0, 22 max: 0, 23 sum: 0 24 })); 25 buildSegmentTree(1, 1, n); 26} 27 28// Build the segment tree recursively 29function buildSegmentTree(nodeIndex: number, leftBound: number, rightBound: number): void { 30 segmentTree[nodeIndex].left = leftBound; 31 segmentTree[nodeIndex].right = rightBound; 32 33 // Leaf node: initialize with full capacity 34 if (leftBound === rightBound) { 35 segmentTree[nodeIndex].sum = seatsPerRow; 36 segmentTree[nodeIndex].max = seatsPerRow; 37 return; 38 } 39 40 // Build left and right subtrees 41 const mid = (leftBound + rightBound) >> 1; 42 buildSegmentTree(nodeIndex << 1, leftBound, mid); 43 buildSegmentTree((nodeIndex << 1) | 1, mid + 1, rightBound); 44 45 // Update current node based on children 46 pushUp(nodeIndex); 47} 48 49// Update a specific position in the segment tree 50function modifySegmentTree(nodeIndex: number, targetPosition: number, newValue: number): void { 51 // Found the target leaf node 52 if (segmentTree[nodeIndex].left === targetPosition && 53 segmentTree[nodeIndex].right === targetPosition) { 54 segmentTree[nodeIndex].sum = newValue; 55 segmentTree[nodeIndex].max = newValue; 56 return; 57 } 58 59 // Recursively update the appropriate child 60 const mid = (segmentTree[nodeIndex].left + segmentTree[nodeIndex].right) >> 1; 61 if (targetPosition <= mid) { 62 modifySegmentTree(nodeIndex << 1, targetPosition, newValue); 63 } else { 64 modifySegmentTree((nodeIndex << 1) | 1, targetPosition, newValue); 65 } 66 67 // Update current node after modifying child 68 pushUp(nodeIndex); 69} 70 71// Query the sum of values in a range 72function queryRangeSum(nodeIndex: number, queryLeft: number, queryRight: number): number { 73 // Current range is completely within query range 74 if (segmentTree[nodeIndex].left >= queryLeft && 75 segmentTree[nodeIndex].right <= queryRight) { 76 return segmentTree[nodeIndex].sum; 77 } 78 79 // Query left and/or right child as needed 80 const mid = (segmentTree[nodeIndex].left + segmentTree[nodeIndex].right) >> 1; 81 let totalSum = 0; 82 83 if (queryLeft <= mid) { 84 totalSum += queryRangeSum(nodeIndex << 1, queryLeft, queryRight); 85 } 86 if (queryRight > mid) { 87 totalSum += queryRangeSum((nodeIndex << 1) | 1, queryLeft, queryRight); 88 } 89 90 return totalSum; 91} 92 93// Find the first index where value >= threshold 94function findFirstIndexWithCapacity(nodeIndex: number, queryLeft: number, queryRight: number, threshold: number): number { 95 // No position in this range has enough capacity 96 if (segmentTree[nodeIndex].max < threshold) { 97 return 0; 98 } 99 100 // Found a leaf node with sufficient capacity 101 if (segmentTree[nodeIndex].left === segmentTree[nodeIndex].right) { 102 return segmentTree[nodeIndex].left; 103 } 104 105 // Check left child first (we want the leftmost valid position) 106 const mid = (segmentTree[nodeIndex].left + segmentTree[nodeIndex].right) >> 1; 107 if (segmentTree[nodeIndex << 1].max >= threshold) { 108 return findFirstIndexWithCapacity(nodeIndex << 1, queryLeft, queryRight, threshold); 109 } 110 111 // Check right child if needed 112 if (queryRight > mid) { 113 return findFirstIndexWithCapacity((nodeIndex << 1) | 1, queryLeft, queryRight, threshold); 114 } 115 116 return 0; 117} 118 119// Update parent node based on its children 120function pushUp(nodeIndex: number): void { 121 const leftChild = nodeIndex << 1; 122 const rightChild = (nodeIndex << 1) | 1; 123 124 segmentTree[nodeIndex].sum = segmentTree[leftChild].sum + segmentTree[rightChild].sum; 125 segmentTree[nodeIndex].max = Math.max(segmentTree[leftChild].max, segmentTree[rightChild].max); 126} 127 128// Book consecutive seats in a single row 129function gather(k: number, maxRow: number): number[] { 130 // Convert to 1-indexed 131 maxRow++; 132 133 // Find the first row with at least k available seats 134 const rowIndex = findFirstIndexWithCapacity(1, 1, maxRow, k); 135 if (rowIndex === 0) { 136 return []; // No suitable row found 137 } 138 139 // Get current available seats in the found row 140 const availableSeats = queryRangeSum(1, rowIndex, rowIndex); 141 142 // Book k seats in this row 143 modifySegmentTree(1, rowIndex, availableSeats - k); 144 145 // Return [0-indexed row, starting seat position] 146 return [rowIndex - 1, seatsPerRow - availableSeats]; 147} 148 149// Book seats across multiple rows 150function scatter(k: number, maxRow: number): boolean { 151 // Convert to 1-indexed 152 maxRow++; 153 154 // Check if there are enough total seats available 155 if (queryRangeSum(1, 1, maxRow) < k) { 156 return false; 157 } 158 159 // Find the first row with available seats 160 let startRow = findFirstIndexWithCapacity(1, 1, maxRow, 1); 161 162 // Greedily fill rows from left to right 163 for (let row = startRow; row <= totalRows; ++row) { 164 const availableSeats = queryRangeSum(1, row, row); 165 166 if (availableSeats >= k) { 167 // All remaining seats can be booked in this row 168 modifySegmentTree(1, row, availableSeats - k); 169 return true; 170 } 171 172 // Book all available seats in this row 173 k -= availableSeats; 174 modifySegmentTree(1, row, 0); 175 } 176 177 return true; 178} 179 180// BookMyShow class wrapper 181class BookMyShow { 182 constructor(n: number, m: number) { 183 initializeBookingSystem(n, m); 184 } 185 186 public gather(k: number, maxRow: number): number[] { 187 return gather(k, maxRow); 188 } 189 190 public scatter(k: number, maxRow: number): boolean { 191 return scatter(k, maxRow); 192 } 193} 194

Solution Approach

The solution uses a Segment Tree data structure to efficiently manage seat availability across all rows. Let's walk through the implementation details:

Segment Tree Node Structure

Each node in the segment tree contains:

l, r: The left and right endpoints of the interval (row range) this node represents
s: The total sum of available seats in this interval
mx: The maximum available seats in any single row within this interval

Building the Segment Tree

The build(u, l, r) method constructs the tree recursively:

For leaf nodes (when l == r), both s and mx are initialized to m (all seats available)
For internal nodes, we recursively build left and right children
The node spans are divided at mid = (l + r) >> 1
After building children, we call pushup(u) to update the parent's values

Core Operations

1. Point Update - modify(u, x, v)

Updates row x to have v available seats
Recursively traverses down to the leaf node representing row x
Updates the leaf's s and mx values to v
Calls pushup on the path back up to update ancestor nodes

2. Range Sum Query - query_sum(u, l, r)

Calculates total available seats in rows [l, r]
If current node's interval is completely within [l, r], return its s value
Otherwise, recursively query relevant children and sum the results

3. Find First Row with k Seats - query_idx(u, l, r, k)

Finds the leftmost row in range [l, r] with at least k available seats
If current node's mx < k, no row in this subtree has enough seats, return 0
For leaf nodes, return the row number if it has enough seats
Otherwise, check left child first (for leftmost row), then right child if needed

4. Update Parent - pushup(u)

Updates node u based on its children
s = left_child.s + right_child.s (sum of available seats)
mx = max(left_child.mx, right_child.mx) (maximum available in any row)

BookMyShow Implementation

gather(k, maxRow):

Convert maxRow to 1-indexed: maxRow += 1
Use query_idx(1, 1, maxRow, k) to find first row i with ≥ k seats
If no such row exists (i == 0), return empty array
Get current available seats in row i: s = query_sum(1, i, i)
Book k seats: modify(1, i, s - k)
Return [i - 1, m - s] (convert back to 0-indexed row, and seat starts at m - s)

scatter(k, maxRow):

Convert maxRow to 1-indexed: maxRow += 1
Check total availability: if query_sum(1, 1, maxRow) < k, return false
Find first row with any seats: i = query_idx(1, 1, maxRow, 1)
Starting from row i, greedily allocate seats:
- Get available seats in current row: s = query_sum(1, j, j)
- If s >= k, book k seats and return true
- Otherwise, book all s seats, update k -= s, and continue to next row
Return true after allocating all seats

Time Complexity

Initialization: O(n) to build the segment tree
gather: O(log n) for one query_idx and one modify operation
scatter: O(n × log n) worst case when seats are scattered across many rows, but typically much better

The segment tree approach transforms what would be O(n) linear searches into O(log n) operations, making the solution efficient for large concert halls with many rows.

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 small example with a concert hall having 4 rows and 5 seats per row.

Initial Setup:

BookMyShow(4, 5) // 4 rows (0-3), 5 seats per row (0-4)  Initial state (all seats empty): Row 0: [_, _, _, _, _] (5 available) Row 1: [_, _, _, _, _] (5 available) Row 2: [_, _, _, _, _] (5 available) Row 3: [_, _, _, _, _] (5 available)  Segment Tree (1-indexed internally):  [1,4]  s=20, mx=5  / \  [1,2] [3,4]  s=10,mx=5 s=10,mx=5  / \ / \  [1] [2] [3] [4]  s=5 s=5 s=5 s=5  mx=5 mx=5 mx=5 mx=5

Operation 1: gather(3, 1)

Want 3 consecutive seats in rows 0-1
Query segment tree: Find first row in [1,2] with mx ≥ 3
Tree traversal finds row 1 (0-indexed: row 0) has 5 seats ≥ 3
Book seats 0,1,2 in row 0
Update: modify row 1 to have 2 seats left

After gather(3, 1) returns [0, 0]: Row 0: [X, X, X, _, _] (2 available) Row 1: [_, _, _, _, _] (5 available) Row 2: [_, _, _, _, _] (5 available) Row 3: [_, _, _, _, _] (5 available)  Tree update at row 1: s=2, mx=2 Parent nodes updated via pushup

Operation 2: scatter(7, 2)

Want 7 total seats in rows 0-2
Check sum: query_sum([1,3]) = 2+5+5 = 12 ≥ 7 ✓
Find first row with seats: row 1 has 2 seats
Allocation process:
- Row 0: Take 2 seats (positions 3,4), k=5 remaining
- Row 1: Take 5 seats (positions 0-4), k=0 remaining
Return true

After scatter(7, 2) returns true: Row 0: [X, X, X, X, X] (0 available) Row 1: [X, X, X, X, X] (0 available) Row 2: [_, _, _, _, _] (5 available) Row 3: [_, _, _, _, _] (5 available)  Tree updates: - Row 1: s=0, mx=0 - Row 2: s=0, mx=0 - Parent nodes updated

Operation 3: gather(4, 3)

Want 4 consecutive seats in rows 0-3
Query segment tree: Find first row in [1,4] with mx ≥ 4
Traversal checks:
- Left subtree [1,2]: mx=0 (no row has 4 seats)
- Right subtree [3,4]: mx=5 (check here)
- Row 3 has 5 seats ≥ 4
Book seats 0,1,2,3 in row 2
Return [2, 0]

After gather(4, 3) returns [2, 0]: Row 0: [X, X, X, X, X] (0 available) Row 1: [X, X, X, X, X] (0 available) Row 2: [X, X, X, X, _] (1 available) Row 3: [_, _, _, _, _] (5 available)  Tree update at row 3: s=1, mx=1

Operation 4: gather(2, 1)

Want 2 consecutive seats in rows 0-1
Query segment tree: Find first row in [1,2] with mx ≥ 2
Both rows have mx=0 (no seats available)
Return []

gather(2, 1) returns [] (no available seats in rows 0-1)

This example demonstrates how the segment tree efficiently tracks available seats, finds suitable rows for group bookings, and manages scattered allocations while maintaining the "smallest row first, smallest seat first" allocation rule.

Time and Space Complexity

Time Complexity:

The overall time complexity is O(n + q × log n), where n is the number of rows and q is the number of operations.

Breaking down the operations:

Initialization (__init__): The segment tree construction calls build() which visits each node once in the tree. With 4n nodes total, this takes O(n) time.
gather() operation:
- query_idx(): Traverses from root to leaf in the segment tree, taking O(log n) time
- query_sum(): Also traverses the tree path, taking O(log n) time
- modify(): Updates values along the path from root to leaf, taking O(log n) time
- Total per gather: O(log n)
scatter() operation:
- query_sum() for checking total: O(log n) time
- query_idx() to find first available row: O(log n) time
- In the worst case, the loop iterates through all n rows, and for each row:
  - query_sum(): O(log n)
  - modify(): O(log n)
- Worst case per scatter: O(n × log n)

However, amortized over all operations, each seat is only allocated once. Across q operations, the total work for all scatter operations is bounded by O(q × log n) amortized.

Space Complexity:

The space complexity is O(n).

The segment tree uses an array of size 4n to store nodes (using the standard n << 2 allocation for 1-indexed segment trees)
Each Node object stores 4 integer values (l, r, s, mx)
Additional space usage is O(1) for other variables

Therefore, the total space used is O(4n) = O(n).

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

Common Pitfalls

1. Index Confusion Between 0-indexed and 1-indexed Systems

The most common pitfall in this implementation is the mixing of 0-indexed (problem requirement) and 1-indexed (segment tree internal) coordinate systems. This creates multiple opportunities for off-by-one errors.

Where it happens:

The problem uses 0-indexed rows (0 to n-1) and seats (0 to m-1)
The segment tree internally uses 1-indexed rows (1 to n)
Conversion happens at the interface between BookMyShow methods and SegmentTree

Specific error-prone areas:

# In gather method: max_row_inclusive = maxRow + 1 # Convert 0-indexed to 1-indexed return [row_number - 1, starting_seat] # Convert back to 0-indexed  # In scatter method: max_row_inclusive = maxRow + 1 # Same conversion needed

Solution: Create explicit conversion helper methods to centralize this logic:

def _to_internal_row(self, external_row: int) -> int:  """Convert 0-indexed external row to 1-indexed internal row."""  return external_row + 1  def _to_external_row(self, internal_row: int) -> int:  """Convert 1-indexed internal row to 0-indexed external row."""  return internal_row - 1

2. Incorrect Seat Position Calculation

Another subtle pitfall is calculating the starting seat position when booking consecutive seats in the gather method.

The problem:

starting_seat = self.segment_tree.seats_per_row - available_seats

This assumes seats are allocated from left to right, but if there's a bug in tracking which specific seats are taken (the current implementation only tracks counts), this could return incorrect positions.

Example scenario:

Row has 10 seats total, 5 available
But the available seats might not be seats 5-9; they could be scattered
The current implementation assumes they're always the rightmost seats

Solution: If precise seat tracking is needed, maintain a bitmap or list of available seats per row:

class BookMyShow:  def __init__(self, n: int, m: int):  self.num_rows = n  self.seats_per_row = m  self.segment_tree = SegmentTree(n, m)  # Track actual seat availability per row  self.row_seats = [[True] * m for _ in range(n)]   def _find_consecutive_seats(self, row: int, k: int) -> int:  """Find starting position of k consecutive available seats."""  count = 0  for i in range(self.seats_per_row):  if self.row_seats[row][i]:  count += 1  if count == k:  return i - k + 1  else:  count = 0  return -1

3. Range Boundary Errors in query_idx

The query_idx method doesn't properly respect the query boundaries when recursing:

Current problematic code:

def query_idx(self, node_idx: int, query_left: int, query_right: int, min_seats: int) -> int:  # ...  if self.nodes[left_child].max_value >= min_seats:  return self.query_idx(left_child, query_left, query_right, min_seats)   if query_right > mid:  return self.query_idx(right_child, query_left, query_right, min_seats)

The issue: The method checks the left child's max_value but doesn't verify if the left child's range actually overlaps with [query_left, query_right].

Solution:

def query_idx(self, node_idx: int, query_left: int, query_right: int, min_seats: int) -> int:  current_node = self.nodes[node_idx]   # No row in this range has enough seats  if current_node.max_value < min_seats:  return 0   # Current range completely outside query range  if current_node.right < query_left or current_node.left > query_right:  return 0   # Leaf node with enough seats  if current_node.left == current_node.right:  return current_node.left   mid = (current_node.left + current_node.right) >> 1  left_child = node_idx << 1  right_child = (node_idx << 1) | 1   # Check left subtree first if it overlaps with query range  if query_left <= mid:  result = self.query_idx(left_child, query_left, query_right, min_seats)  if result != 0:  return result   # Check right subtree if it overlaps with query range  if query_right > mid:  return self.query_idx(right_child, query_left, query_right, min_seats)   return 0

4. Performance Degradation in scatter Method

The scatter method iterates through rows sequentially after finding the first available row, which could be inefficient:

Current approach:

for row_number in range(first_available_row, self.num_rows + 1):  # Process each row sequentially

The issue: This creates O(n) iterations in worst case, each with O(log n) segment tree operations.

Solution: Use the segment tree more efficiently by finding each next available row:

def scatter(self, k: int, maxRow: int) -> bool:  max_row_inclusive = maxRow + 1   if self.segment_tree.query_sum(1, 1, max_row_inclusive) < k:  return False   remaining = k  current_row = 1   while remaining > 0 and current_row <= max_row_inclusive:  # Find next row with available seats  next_row = self.segment_tree.query_idx(1, current_row, max_row_inclusive, 1)  if next_row == 0:  break   available = self.segment_tree.query_sum(1, next_row, next_row)  seats_to_book = min(available, remaining)   self.segment_tree.modify(1, next_row, available - seats_to_book)  remaining -= seats_to_book  current_row = next_row + 1   return True

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

What's the output of running the following function using input 56?

1KEYBOARD = { 2 '2': 'abc', 3 '3': 'def', 4 '4': 'ghi', 5 '5': 'jkl', 6 '6': 'mno', 7 '7': 'pqrs', 8 '8': 'tuv', 9 '9': 'wxyz', 10} 11 12def letter_combinations_of_phone_number(digits): 13 def dfs(path, res): 14 if len(path) == len(digits): 15 res.append(''.join(path)) 16 return 17 18 next_number = digits[len(path)] 19 for letter in KEYBOARD[next_number]: 20 path.append(letter) 21 dfs(path, res) 22 path.pop() 23 24 res = [] 25 dfs([], res) 26 return res 27

1private static final Map<Character, char[]> KEYBOARD = Map.of( 2 '2', "abc".toCharArray(), 3 '3', "def".toCharArray(), 4 '4', "ghi".toCharArray(), 5 '5', "jkl".toCharArray(), 6 '6', "mno".toCharArray(), 7 '7', "pqrs".toCharArray(), 8 '8', "tuv".toCharArray(), 9 '9', "wxyz".toCharArray() 10); 11 12public static List<String> letterCombinationsOfPhoneNumber(String digits) { 13 List<String> res = new ArrayList<>(); 14 dfs(new StringBuilder(), res, digits.toCharArray()); 15 return res; 16} 17 18private static void dfs(StringBuilder path, List<String> res, char[] digits) { 19 if (path.length() == digits.length) { 20 res.add(path.toString()); 21 return; 22 } 23 char next_digit = digits[path.length()]; 24 for (char letter : KEYBOARD.get(next_digit)) { 25 path.append(letter); 26 dfs(path, res, digits); 27 path.deleteCharAt(path.length() - 1); 28 } 29} 30

1const KEYBOARD = { 2 '2': 'abc', 3 '3': 'def', 4 '4': 'ghi', 5 '5': 'jkl', 6 '6': 'mno', 7 '7': 'pqrs', 8 '8': 'tuv', 9 '9': 'wxyz', 10} 11 12function letter_combinations_of_phone_number(digits) { 13 let res = []; 14 dfs(digits, [], res); 15 return res; 16} 17 18function dfs(digits, path, res) { 19 if (path.length === digits.length) { 20 res.push(path.join('')); 21 return; 22 } 23 let next_number = digits.charAt(path.length); 24 for (let letter of KEYBOARD[next_number]) { 25 path.push(letter); 26 dfs(digits, path, res); 27 path.pop(); 28 } 29} 30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know