Watch 7 video solutions for Booking Concert Tickets in Groups, a hard level problem involving Binary Search, Design, Binary Indexed Tree. This walkthrough by codingMohan has 6,083 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A concert hall has n rows numbered from 0 to n - 1, each with m seats, numbered from 0 to m - 1. You need to design a ticketing system that can allocate seats in the following cases:
k spectators can sit together in a row.k spectators can get a seat. They may or may not sit together.Note that the spectators are very picky. Hence:
maxRow. maxRow can vary from group to group.Implement the BookMyShow class:
BookMyShow(int n, int m) Initializes the object with n as number of rows and m as number of seats per row.int[] gather(int k, int maxRow) Returns an array of length 2 denoting the row and seat number (respectively) of the first seat being allocated to the k members of the group, who must sit together. In other words, it returns the smallest possible r and c such that all [c, c + k - 1] seats are valid and empty in row r, and r <= maxRow. Returns [] in case it is not possible to allocate seats to the group.boolean scatter(int k, int maxRow) Returns true if all k members of the group can be allocated seats in rows 0 to maxRow, who may or may not sit together. If the seats can be allocated, it allocates k seats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returns false.
Example 1:
Input
["BookMyShow", "gather", "gather", "scatter", "scatter"]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
Output
[null, [0, 0], [], true, false]
Explanation
BookMyShow bms = new BookMyShow(2, 5); // There are 2 rows with 5 seats each
bms.gather(4, 0); // return [0, 0]
// The group books seats [0, 3] of row 0.
bms.gather(2, 0); // return []
// There is only 1 seat left in row 0,
// so it is not possible to book 2 consecutive seats.
bms.scatter(5, 1); // return True
// The group books seat 4 of row 0 and seats [0, 3] of row 1.
bms.scatter(5, 1); // return False
// There is only one seat left in the hall.
Constraints:
1 <= n <= 5 * 1041 <= m, k <= 1090 <= maxRow <= n - 15 * 104 calls in total will be made to gather and scatter.Problem Overview: You need to design a ticket booking system for a concert hall with n rows and m seats per row. Two operations are supported: gather, which books k consecutive seats in a single row up to maxRow, and scatter, which books k seats across multiple rows (not necessarily consecutive) up to maxRow. The challenge is handling many queries efficiently while constantly updating available seats.
Approach 1: Brute Force with Linear Search (Time: O(n) per query, Space: O(n))
Maintain an array that stores how many seats remain in each row. For a gather request, iterate from row 0 to maxRow and check whether a row has at least k consecutive seats available. Once found, allocate seats and update the remaining capacity. For scatter, iterate through rows up to maxRow, filling seats greedily until k tickets are assigned. This approach is easy to implement and works well when the number of rows or queries is small. However, every request may scan many rows, making it inefficient when n and query count are large.
Approach 2: Binary Search with Prefix Sums (Time: O(log n) per query, Space: O(n))
Optimize the search process using prefix sums and binary search. Maintain cumulative seat availability so you can quickly determine how many seats exist in rows 0..maxRow. For scatter, check the prefix sum to confirm whether enough seats exist, then distribute seats across rows while updating the structure. For gather, binary search the earliest row that still has at least k consecutive seats. After allocation, update the prefix values to reflect the reduced capacity.
This design significantly reduces row scanning. Instead of checking every row, you locate candidate rows with logarithmic search and maintain running totals for fast validation. In large systems with thousands of rows and frequent operations, this difference is critical. Many implementations internally rely on structures similar to a segment tree or binary indexed tree to support these prefix queries and updates efficiently.
Recommended for interviews: Interviewers expect an optimized design rather than repeated linear scans. Starting with the brute force approach shows you understand the booking rules and constraints. The optimized binary-search/prefix-sum strategy demonstrates stronger algorithmic thinking and familiarity with scalable data structures used in real systems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Linear Search | O(n) per query | O(n) | Simple implementation when row count or query volume is small |
| Binary Search with Prefix Sums | O(log n) per query | O(n) | Large inputs with many queries where fast seat lookup and updates are required |