2286. Booking Concert Tickets in Groups Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 * 10⁴
1 <= m, k <= 10⁹
0 <= maxRow <= n - 1
At most 5 * 10⁴ 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.

Python

class BookMyShow:
    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m
        self.seats = [0] * n

    def gather(self, k: int, maxRow: int):
        for r in range(maxRow + 1):
            if self.m - self.seats[r] >= k:
                seat_start = self.seats[r]
                self.seats[r] += k
                return [r, seat_start]
        return []

    def scatter(self, k: int, maxRow: int):
        for r in range(maxRow + 1):
            available = self.m - self.seats[r]
            if available > 0:
                seats_to_fill = min(k, available)
                self.seats[r] += seats_to_fill
                k -= seats_to_fill
            if k == 0:
                return True
        return False

Java

class BookMyShow {
    private int n, m;
    private int[] seats;

    public BookMyShow(int n, int m) {
        this.n = n;
        this.m = m;
        this.seats = new int[n];
    }

    public int[] gather(int k, int maxRow) {
        for (int r = 0; r <= maxRow; r++) {
            if (m - seats[r] >= k) {
                seats[r] += k;
                return new int[]{r, seats[r] - k};
            }
        }
        return new int[]{};
    }

    public boolean scatter(int k, int maxRow) {
        for (int r = 0; r <= maxRow && k > 0; r++) {
            int availableSeats = m - seats[r];
            if (availableSeats > 0) {
                int seatsToBook = Math.min(k, availableSeats);
                seats[r] += seatsToBook;
                k -= seatsToBook;
            }
        }
        return k == 0;
    }
}

C++

#include <vector>
using namespace std;

class BookMyShow {
    int n, m;
    vector<int> seats;
public:
    BookMyShow(int n, int m) : n(n), m(m), seats(n, 0) {}

    vector<int> gather(int k, int maxRow) {
        for (int r = 0; r <= maxRow; ++r) {
            if (m - seats[r] >= k) {
                seats[r] += k;
                return {r, seats[r] - k};
            }
        }
        return {};
    }

    bool scatter(int k, int maxRow) {
        for (int r = 0; r <= maxRow && k > 0; ++r) {
            int availableSeats = m - seats[r];
            if (availableSeats > 0) {
                int seatsToBook = min(k, availableSeats);
                seats[r] += seatsToBook;
                k -= seatsToBook;
            }
        }
        return k == 0;
    }
};

JavaScript

class BookMyShow {
    constructor(n, m) {
        this.n = n;
        this.m = m;
        this.seats = Array(n).fill(0);
    }

    gather(k, maxRow) {
        for (let r = 0; r <= maxRow; r++) {
            if (this.m - this.seats[r] >= k) {
                let seatStart = this.seats[r];
                this.seats[r] += k;
                return [r, seatStart];
            }
        }
        return [];
    }

    scatter(k, maxRow) {
        for (let r = 0; r <= maxRow && k > 0; r++) {
            let available = this.m - this.seats[r];
            if (available > 0) {
                let seatsToFill = Math.min(k, available);
                this.seats[r] += seatsToFill;
                k -= seatsToFill;
            }
        }
        return k === 0;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int n, m;
    int* seats;
} BookMyShow;

BookMyShow* bookMyShowCreate(int n, int m) {
    BookMyShow* bms = (BookMyShow*)malloc(sizeof(BookMyShow));
    bms->n = n;
    bms->m = m;
    bms->seats = (int*)calloc(n, sizeof(int));
    return bms;
}

int* gather(BookMyShow* bms, int k, int maxRow, int* resultSize) {
    for (int r = 0; r <= maxRow; r++) {
        if (bms->m - bms->seats[r] >= k) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = r;
            result[1] = bms->seats[r];
            bms->seats[r] += k;
            *resultSize = 2;
            return result;
        }
    }
    *resultSize = 0;
    return NULL;
}

bool scatter(BookMyShow* bms, int k, int maxRow) {
    for (int r = 0; r <= maxRow && k > 0; r++) {
        int availableSeats = bms->m - bms->seats[r];
        if (availableSeats > 0) {
            int seatsToBook = (k < availableSeats) ? k : availableSeats;
            bms->seats[r] += seatsToBook;
            k -= seatsToBook;
        }
    }
    return k == 0;
}

void bookMyShowFree(BookMyShow* bms) {
    free(bms->seats);
    free(bms);
}

using System;

public class BookMyShow {
    private int n, m;
    private int[] seats;

    public BookMyShow(int n, int m) {
        this.n = n;
        this.m = m;
        this.seats = new int[n];
    }

    public int[] Gather(int k, int maxRow) {
        for (int r = 0; r <= maxRow; r++) {
            if (m - seats[r] >= k) {
                seats[r] += k;
                return new int[]{r, seats[r] - k};
            }
        }
        return new int[]{};
    }

    public bool Scatter(int k, int maxRow) {
        for (int r = 0; r <= maxRow && k > 0; r++) {
            int availableSeats = m - seats[r];
            if (availableSeats > 0) {
                int seatsToBook = Math.Min(k, availableSeats);
                seats[r] += seatsToBook;
                k -= seatsToBook;
            }
        }
        return k == 0;
    }
}

In the Python solution, we use a list to track how many seats have been allocated in each row. The logic for both gather and scatter methods involve iterating through the rows and checking seat availabilities.

Complexity

Time Complexity: O(n*m); Space Complexity: O(n), analogous to the previous solutions.

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.

Python

class BookMyShow:
    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m
        self.seats = [0] * n
        self.totalSeats = n * m

    def gather(self, k: int, maxRow: int):
        for r in range(maxRow + 1):
            if self.m - self.seats[r] >= k:
                seat_start = self.seats[r]
                self.seats[r] += k
                self.totalSeats -= k
                return [r, seat_start]
        return []

    def scatter(self, k: int, maxRow: int):
        if self.totalSeats < k:
            return False
        for r in range(maxRow + 1):
            if self.seats[r] < self.m:
                available = self.m - self.seats[r]
                if available > 0:
                    seats_to_fill = min(k, available)
                    self.seats[r] += seats_to_fill
                    self.totalSeats -= seats_to_fill
                    k -= seats_to_fill
            if k == 0:
                return True
        return False

Java

import java.util.*;

class BookMyShow {
    private int n, m;
    private int[] seats;
    private int totalSeats;
    private int[] prefixSum;

    public BookMyShow(int n, int m) {
        this.n = n;
        this.m = m;
        this.seats = new int[n];
        this.totalSeats = n * m;
        this.prefixSum = new int[n + 1];
    }

    public int[] gather(int k, int maxRow) {
        for (int r = 0; r <= maxRow; r++) {
            if (m - seats[r] >= k) {
                seats[r] += k;
                totalSeats -= k;
                updatePrefixSum(r, k);
                return new int[]{r, seats[r] - k};
            }
        }
        return new int[]{};
    }

    public boolean scatter(int k, int maxRow) {
        if (totalSeats < k) return false;
        for (int r = 0; r <= maxRow && k > 0; r++) {
            int available = m - seats[r];
            if (available > 0) {
                int seatsToBook = Math.min(k, available);
                seats[r] += seatsToBook;
                k -= seatsToBook;
                updatePrefixSum(r, seatsToBook);
                totalSeats -= seatsToBook;
            }
        }
        return k == 0;
    }

    private void updatePrefixSum(int row, int delta) {
        for (int i = row + 1; i <= n; i++) {
            prefixSum[i] += delta;
        }
    }
}

C++

#include <vector>
#include <numeric>
using namespace std;

class BookMyShow {
    int n, m;
    vector<int> seats;
    int totalSeats;
    vector<int> prefixSum;
public:
    BookMyShow(int n, int m) : n(n), m(m), seats(n, 0), totalSeats(n * m), prefixSum(n + 1, 0) {}

    vector<int> gather(int k, int maxRow) {
        for (int r = 0; r <= maxRow; ++r) {
            if (m - seats[r] >= k) {
                seats[r] += k;
                totalSeats -= k;
                updatePrefixSum(r, k);
                return {r, seats[r] - k};
            }
        }
        return {};
    }

    bool scatter(int k, int maxRow) {
        if (totalSeats < k) return false;
        
        for (int r = 0; r <= maxRow && k > 0; ++r) {
            if (seats[r] < m) {
                int availableSeats = m - seats[r];
                int seatsToBook = min(k, availableSeats);
                seats[r] += seatsToBook;
                k -= seatsToBook;
                updatePrefixSum(r, seatsToBook);
                totalSeats -= seatsToBook;
            }
        }
        return k == 0;
    }
    
    void updatePrefixSum(int row, int delta) {
        for (int i = row + 1; i <= n; ++i) {
            prefixSum[i] += delta;
        }
    }
};

JavaScript

class BookMyShow {
    constructor(n, m) {
        this.n = n;
        this.m = m;
        this.seats = Array(n).fill(0);
        this.totalSeats = n * m;
    }

    gather(k, maxRow) {
        for (let r = 0; r <= maxRow; r++) {
            if (this.m - this.seats[r] >= k) {
                let seatStart = this.seats[r];
                this.seats[r] += k;
                this.totalSeats -= k;
                return [r, seatStart];
            }
        }
        return [];
    }

    scatter(k, maxRow) {
        if (this.totalSeats < k) return false;
        let row = 0;
        while (row <= maxRow) {
            if (this.seats[row] < this.m) {
                let availableSeats = this.m - this.seats[row];
                let seatsToBook = Math.min(k, availableSeats);
                this.seats[row] += seatsToBook;
                this.totalSeats -= seatsToBook;
                k -= seatsToBook;
            }
            if (k === 0) return true;
            row++;
        }
        return false;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int n, m;
    int* seats;
    int totalSeats;
} BookMyShow;

BookMyShow* bookMyShowCreate(int n, int m) {
    BookMyShow* bms = (BookMyShow*)malloc(sizeof(BookMyShow));
    bms->n = n;
    bms->m = m;
    bms->seats = (int*)calloc(n, sizeof(int));
    bms->totalSeats = n * m;
    return bms;
}

int* gather(BookMyShow* bms, int k, int maxRow, int* resultSize) {
    for (int r = 0; r <= maxRow; r++) {
        if (bms->m - bms->seats[r] >= k) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = r;
            result[1] = bms->seats[r];
            bms->seats[r] += k;
            bms->totalSeats -= k;
            *resultSize = 2;
            return result;
        }
    }
    *resultSize = 0;
    return NULL;
}

bool scatter(BookMyShow* bms, int k, int maxRow) {
    if(bms->totalSeats < k)
        return false;
    for (int r = 0; r <= maxRow && k > 0; r++) {
        if (bms->seats[r] < bms->m) {
            int availableSeats = bms->m - bms->seats[r];
            if (availableSeats > 0) {
                int seatsToBook = (k < availableSeats) ? k : availableSeats;
                bms->seats[r] += seatsToBook;
                bms->totalSeats -= seatsToBook;
                k -= seatsToBook;
            }
        }
    }
    return k == 0;
}

void bookMyShowFree(BookMyShow* bms) {
    free(bms->seats);
    free(bms);
}

using System;

public class BookMyShow {
    private int n, m;
    private int[] seats;
    private int totalSeats;

    public BookMyShow(int n, int m) {
        this.n = n;
        this.m = m;
        this.seats = new int[n];
        this.totalSeats = n * m;
    }

    public int[] Gather(int k, int maxRow) {
        for (int r = 0; r <= maxRow; r++) {
            if (m - seats[r] >= k) {
                seats[r] += k;
                totalSeats -= k;
                return new int[]{r, seats[r] - k};
            }
        }
        return new int[0];
    }

    public bool Scatter(int k, int maxRow) {
        if (totalSeats < k) return false;
        for (int r = 0; r <= maxRow && k > 0; r++) {
            int availableSeats = m - seats[r];
            if (availableSeats > 0) {
                int seatsToBook = Math.Min(k, availableSeats);
                seats[r] += seatsToBook;
                totalSeats -= seatsToBook;
                k -= seatsToBook;
            }
        }
        return k == 0;
    }
}

The Python code similarly refines efficiency by streamlining total available seats and processing updates eliminating unnecessary checks during allocation operations, emulating the same cumulative verification process seen in Java and C++.

Complexity

Time Complexity: O(n log m); Space Complexity: O(n), facilitated by cumulative availability calculations and range operations.

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.

TypeScript

class Node {
    l: number;
    r: number;
    mx: number;
    s: number;

    constructor() {
        this.l = 0;
        this.r = 0;
        this.mx = 0;
        this.s = 0;
    }
}

class SegmentTree {
    private tr: Node[];
    private m: number;

    constructor(n: number, m: number) {
        this.m = m;
        this.tr = Array.from({ length: n << 2 }, () => new Node());
        this.build(1, 1, n);
    }

    private build(u: number, l: number, r: number): void {
        this.tr[u].l = l;
        this.tr[u].r = r;
        if (l === r) {
            this.tr[u].s = this.m;
            this.tr[u].mx = this.m;
            return;
        }
        const mid = (l + r) >> 1;
        this.build(u << 1, l, mid);
        this.build((u << 1) | 1, mid + 1, r);
        this.pushup(u);
    }

    public modify(u: number, x: number, v: number): void {
        if (this.tr[u].l === x && this.tr[u].r === x) {
            this.tr[u].s = v;
            this.tr[u].mx = v;
            return;
        }
        const mid = (this.tr[u].l + this.tr[u].r) >> 1;
        if (x <= mid) {
            this.modify(u << 1, x, v);
        } else {
            this.modify((u << 1) | 1, x, v);
        }
        this.pushup(u);
    }

    public querySum(u: number, l: number, r: number): number {
        if (this.tr[u].l >= l && this.tr[u].r <= r) {
            return this.tr[u].s;
        }
        const mid = (this.tr[u].l + this.tr[u].r) >> 1;
        let v = 0;
        if (l <= mid) {
            v += this.querySum(u << 1, l, r);
        }
        if (r > mid) {
            v += this.querySum((u << 1) | 1, l, r);
        }
        return v;
    }

    public queryIdx(u: number, l: number, r: number, k: number): number {
        if (this.tr[u].mx < k) {
            return 0;
        }
        if (this.tr[u].l === this.tr[u].r) {
            return this.tr[u].l;
        }
        const mid = (this.tr[u].l + this.tr[u].r) >> 1;
        if (this.tr[u << 1].mx >= k) {
            return this.queryIdx(u << 1, l, r, k);
        }
        if (r > mid) {
            return this.queryIdx((u << 1) | 1, l, r, k);
        }
        return 0;
    }

    private pushup(u: number): void {
        this.tr[u].s = this.tr[u << 1].s + this.tr[(u << 1) | 1].s;
        this.tr[u].mx = Math.max(this.tr[u << 1].mx, this.tr[(u << 1) | 1].mx);
    }
}

class BookMyShow {
    private n: number;
    private m: number;
    private tree: SegmentTree;

    constructor(n: number, m: number) {
        this.n = n;
        this.m = m;
        this.tree = new SegmentTree(n, m);
    }

    public gather(k: number, maxRow: number): number[] {
        ++maxRow;
        const i = this.tree.queryIdx(1, 1, maxRow, k);
        if (i === 0) {
            return [];
        }
        const s = this.tree.querySum(1, i, i);
        this.tree.modify(1, i, s - k);
        return [i - 1, this.m - s];
    }

    public scatter(k: number, maxRow: number): boolean {
        ++maxRow;
        if (this.tree.querySum(1, 1, maxRow) < k) {
            return false;
        }
        let i = this.tree.queryIdx(1, 1, maxRow, 1);
        for (let j = i; j <= this.n; ++j) {
            const s = this.tree.querySum(1, j, j);
            if (s >= k) {
                this.tree.modify(1, j, s - k);
                return true;
            }
            k -= s;
            this.tree.modify(1, j, 0);
        }
        return true;
    }
}

type BookMyShow struct {
	n, m int
	tree *segmentTree
}

func Constructor(n int, m int) BookMyShow {
	return BookMyShow{n, m, newSegmentTree(n, m)}
}

func (this *BookMyShow) Gather(k int, maxRow int) []int {
	maxRow++
	i := this.tree.queryIdx(1, 1, maxRow, k)
	if i == 0 {
		return []int{}
	}
	s := this.tree.querySum(1, i, i)
	this.tree.modify(1, i, s-k)
	return []int{i - 1, this.m - s}
}

func (this *BookMyShow) Scatter(k int, maxRow int) bool {
	maxRow++
	if this.tree.querySum(1, 1, maxRow) < k {
		return false
	}
	i := this.tree.queryIdx(1, 1, maxRow, 1)
	for j := i; j <= this.n; j++ {
		s := this.tree.querySum(1, j, j)
		if s >= k {
			this.tree.modify(1, j, s-k)
			return true
		}
		k -= s
		this.tree.modify(1, j, 0)
	}
	return true
}

type node struct {
	l, r, s, mx int
}

type segmentTree struct {
	tr []*node
	m  int
}

func newSegmentTree(n, m int) *segmentTree {
	tr := make([]*node, n<<2)
	for i := range tr {
		tr[i] = &node{}
	}
	t := &segmentTree{tr, m}
	t.build(1, 1, n)
	return t
}

func (t *segmentTree) build(u, l, r int) {
	t.tr[u].l, t.tr[u].r = l, r
	if l == r {
		t.tr[u].s, t.tr[u].mx = t.m, t.m
		return
	}
	mid := (l + r) >> 1
	t.build(u<<1, l, mid)
	t.build(u<<1|1, mid+1, r)
	t.pushup(u)
}

func (t *segmentTree) modify(u, x, v int) {
	if t.tr[u].l == x && t.tr[u].r == x {
		t.tr[u].s, t.tr[u].mx = v, v
		return
	}
	mid := (t.tr[u].l + t.tr[u].r) >> 1
	if x <= mid {
		t.modify(u<<1, x, v)
	} else {
		t.modify(u<<1|1, x, v)
	}
	t.pushup(u)
}

func (t *segmentTree) querySum(u, l, r int) int {
	if t.tr[u].l >= l && t.tr[u].r <= r {
		return t.tr[u].s
	}
	mid := (t.tr[u].l + t.tr[u].r) >> 1
	v := 0
	if l <= mid {
		v = t.querySum(u<<1, l, r)
	}
	if r > mid {
		v += t.querySum(u<<1|1, l, r)
	}
	return v
}

func (t *segmentTree) queryIdx(u, l, r, k int) int {
	if t.tr[u].mx < k {
		return 0
	}
	if t.tr[u].l == t.tr[u].r {
		return t.tr[u].l
	}
	mid := (t.tr[u].l + t.tr[u].r) >> 1
	if t.tr[u<<1].mx >= k {
		return t.queryIdx(u<<1, l, r, k)
	}
	if r > mid {
		return t.queryIdx(u<<1|1, l, r, k)
	}
	return 0
}

func (t *segmentTree) pushup(u int) {
	t.tr[u].s = t.tr[u<<1].s + t.tr[u<<1|1].s
	t.tr[u].mx = max(t.tr[u<<1].mx, t.tr[u<<1|1].mx)
}

/**
 * Your BookMyShow object will be instantiated and called as such:
 * obj := Constructor(n, m);
 * param_1 := obj.Gather(k,maxRow);
 * param_2 := obj.Scatter(k,maxRow);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Brute Force with Linear Search	Time Complexity: O(n*m); Space Complexity: O(n), analogous to the previous solutions.
Approach 2: Optimized with Binary Search and Prefix Sums	Time Complexity: O(n log m); Space Complexity: O(n), facilitated by cumulative availability calculations and range operations.
Segment Tree	–

Complexity analysis

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

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.

Booking Concert Tickets in Groups solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Brute Force with Linear Search

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

Approach 3: Segment Tree

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Booking Concert Tickets in Groups solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Brute Force with Linear Search

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

Approach 3: Segment Tree

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems