Skip to main content
Talentd

Booking Concert Tickets in Groups - Solution & Explanation

HardBinary SearchDesignBinary Indexed TreeSegment Tree37 min readAsked at: Google
Practice this problem

Problem Statement

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:

  • If a group of k spectators can sit together in a row.
  • If every member of a group of k spectators can get a seat. They may or may not sit together.

Note that the spectators are very picky. Hence:

  • They will book seats only if each member of their group can get a seat with row number less than or equal to maxRow. maxRow can vary from group to group.
  • In case there are multiple rows to choose from, the row with the smallest number is chosen. If there are multiple seats to choose in the same row, the seat with the smallest number is chosen.

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 * 104
  • 1 <= m, k <= 109
  • 0 <= maxRow <= n - 1
  • At most 5 * 104 calls in total will be made to gather and scatter.

Approach Overview

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 1: Approach 1: Brute Force with Linear Search

This approach involves iterating through each row to check if the required number of consecutive seats (for gather) or total seats (for scatter) are available. It's straightforward but can be inefficient for large inputs.

In this solution, we represent the concert hall using an array where each element contains the number of seats booked in the corresponding row. When using gather, we iterate through rows checking for available consecutive seats. For scatter, we distribute seats across rows until all are booked or no seats are left.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m); Space Complexity: O(n), where n is the number of rows.

Try this approach in the editor →

Approach 2: Approach 2: Optimized with Binary Search and Prefix Sums

To enhance seat allocation efficiency, we utilize binary search combined with prefix sums. By preprocessing seat availability data, both gather and scatter operations can be executed in a more optimized manner.

This C solution augments the simple approach with a total seat counter. The scatter method exploits this counter to quickly invalidate requests exceeding total availability, thus optimizing seat watching operations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m); Space Complexity: O(n), where direct seat counting offsets redundant checks.

Try this approach in the editor →

Approach 3: Segment Tree

From the problem description, we can deduce the following:

  • For the gather(k, maxRow) operation, the goal is to seat k people on the same row with consecutive seats. In other words, we need to find the smallest row where the remaining seats are greater than or equal to k.
  • For the scatter(k, maxRow) operation, we just need to find k seats in total, but we want to minimize the row number. Therefore, we need to find the first row that has more than 0 seats remaining, allocate seats there, and continue searching for the rest.

We can implement this using a segment tree. Each segment tree node contains the following information:

  • l: The left endpoint of the node's interval
  • r: The right endpoint of the node's interval
  • s: The total remaining seats in the interval corresponding to the node
  • mx: The maximum remaining seats in the interval corresponding to the node

Note that the index range for the segment tree starts from 1.

The operations of the segment tree are as follows:

  • build(u, l, r): Builds node u, corresponding to the interval [l, r], and recursively builds its left and right children.
  • modify(u, x, v): Starting from node u, finds the first node corresponding to the interval [l, r] where l = r = x, and modifies the s and mx values of this node to v, then updates the tree upwards.
  • query_sum(u, l, r): Starting from node u, calculates the sum of s values in the interval [l, r].
  • query_idx(u, l, r, k): Starting from node u, finds the first node in the interval [l, r] where mx is greater than or equal to k, and returns the left endpoint l of this node. When searching, we start from the largest interval [1, maxRow]. Since we need to find the leftmost node with mx greater than or equal to k, we check whether the mx of the first half of the interval meets the condition. If so, the answer is in the first half, and we recursively search that half. Otherwise, the answer is in the second half, and we search that half recursively.
  • pushup(u): Updates the information of node u using the information from its children.

For the gather(k, maxRow) operation, we first use query_idx(1, 1, n, k) to find the first row where the remaining seats are greater than or equal to k, denoted as i. Then, we use query_sum(1, i, i) to get the remaining seats in this row, denoted as s. Next, we use modify(1, i, s - k) to modify the remaining seats of this row to s - k, and update the tree upwards. Finally, we return the result [i - 1, m - s].

For the scatter(k, maxRow) operation, we first use query_sum(1, 1, maxRow) to calculate the total remaining seats in the first maxRow rows, denoted as s. If s \lt k, there are not enough seats, so we return false. Otherwise, we use query_idx(1, 1, maxRow, 1) to find the first row where the remaining seats are greater than or equal to 1, denoted as i. Starting from this row, we use query_sum(1, i, i) to get the remaining seats in row i, denoted as s_i. If s_i geq k, we directly use modify(1, i, s_i - k) to modify the remaining seats of this row to s_i - k, update the tree upwards, and return true. Otherwise, we update k = k - s_i, modify the remaining seats of this row to 0, and update the tree upwards. Finally, we return true.

Time complexity:

  • The initialization time complexity is O(n).
  • The time complexity of gather(k, maxRow) is O(log n).
  • The time complexity of scatter(k, maxRow) is O((n + q) times log n).

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force with Linear Search

Time Complexity: O(n*m); Space Complexity: O(n), where n is the number of rows.

Approach 2: Optimized with Binary Search and Prefix Sums

Time Complexity: O(n + m); Space Complexity: O(n), where direct seat counting offsets redundant checks.

Segment Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Linear SearchO(n) per queryO(n)Simple implementation when row count or query volume is small
Binary Search with Prefix SumsO(log n) per queryO(n)Large inputs with many queries where fast seat lookup and updates are required

Video Solution

BiWeekly Contest 79 | 10011. Booking Concert Tickets in Groups • codingMohan • 6,279 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Booking Concert Tickets in Groups easy or hard?
Booking Concert Tickets in Groups is categorized as a hard problem on LeetCode. The difficulty comes from combining system design logic with efficient query handling using advanced data structures and careful seat allocation rules.
Booking Concert Tickets in Groups Python/Java solution
Python and Java implementations typically maintain an array for remaining seats and a tree-based structure for prefix queries. Each gather or scatter operation updates the structure so future queries reflect the new seat availability.
How to solve Booking Concert Tickets in Groups in O(log n)?
Maintain seat availability per row and build a prefix-based structure that supports fast range queries. Use binary search to locate the first row that has at least k consecutive seats for gather operations. For scatter, check the prefix total up to maxRow to confirm enough seats exist, then update rows while maintaining the prefix structure.
What is the best approach for Booking Concert Tickets in Groups?
The most efficient solution uses binary search with prefix sums or a tree-based structure to track remaining seats per row. This allows you to quickly locate a row that can satisfy a gather request and verify capacity for scatter requests. The typical complexity is O(log n) per operation, which scales well for thousands of rows and queries.
Is Booking Concert Tickets in Groups asked at Google/Amazon/Meta?
Problems involving dynamic seat allocation and interval capacity tracking commonly appear in interviews at companies like Google, Amazon, and Meta. The question tests system-style thinking along with advanced data structures such as segment trees or Fenwick trees.
What data structure is used in Booking Concert Tickets in Groups?
Efficient solutions use structures that support fast prefix queries and updates, such as a segment tree or binary indexed tree. These allow quick checks for remaining capacity and help locate rows that can satisfy a gather request without scanning the entire array.
What is the time complexity of Booking Concert Tickets in Groups?
The brute force design scans rows linearly and costs O(n) time per query. Optimized implementations that combine prefix sums with binary search or tree structures reduce operations to about O(log n) per query while maintaining O(n) space for seat tracking.

Ready to solve this problem?

Practice Booking Concert Tickets in Groups with our built-in code editor and test cases.

Practice on FleetCode
Previous

Cinema Seat Allocation

Next

Longest Increasing Subsequence II