Facebook Pixel

2286. Booking Concert Tickets in Groups

HardDesignBinary Indexed TreeSegment TreeBinary Search
Leetcode Link

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:

  1. Range maximum query: Find the row with the most available seats in a range (for gather)
  2. 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 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):

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

scatter(k, maxRow):

  1. Convert maxRow to 1-indexed: maxRow += 1
  2. Check total availability: if query_sum(1, 1, maxRow) < k, return false
  3. Find first row with any seats: i = query_idx(1, 1, maxRow, 1)
  4. 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
  5. 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.

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

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:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More