LeetCode 2286 - Booking Concert Tickets in Groups

The problem asks us to design a ticket reservation system for a concert hall. The hall contains n rows, and each row contains exactly m seats. Seats in every row are numbered from left to right starting at 0.

leetcodehardbinary-searchdesignbinary-indexed-treesegment-tree

LeetCode Problem 2286

Difficulty: 🔴 Hard
Topics: Binary Search, Design, Binary Indexed Tree, Segment Tree

Solution

Problem Understanding

The problem asks us to design a ticket reservation system for a concert hall. The hall contains n rows, and each row contains exactly m seats. Seats in every row are numbered from left to right starting at 0.

We must support two different operations:

The first operation, gather(k, maxRow), tries to reserve k consecutive seats in the same row. The row number must be at most maxRow. Among all valid choices, we must always choose the smallest possible row index. Within that row, we must choose the leftmost available block of seats. If no row from 0 through maxRow has k consecutive empty seats, we return an empty array.

The second operation, scatter(k, maxRow), is less restrictive. The k people do not need to sit together. We only need to ensure that there are at least k total empty seats across rows 0 through maxRow. If possible, seats are allocated greedily using the smallest row numbers first, and within each row, the smallest seat numbers first. The method returns true if allocation succeeds and false otherwise.

A key observation is that seats are always filled from left to right within each row. We never create gaps inside a row. This property becomes extremely important because it means we only need to track how many seats have already been used in each row.

The constraints are large:

  • n <= 5 * 10^4
  • At most 5 * 10^4 operations
  • m and k can be as large as 10^9

A naive simulation that checks every seat individually would be far too slow. Even iterating through all rows repeatedly can become expensive if done carelessly.

The main challenge is efficiently answering two questions repeatedly:

  1. Does some row up to maxRow have at least k consecutive empty seats?
  2. How many total empty seats exist up to maxRow?

These requirements strongly suggest a segment tree, because we need efficient range queries and updates.

Important edge cases include:

  • A row may become completely full.
  • gather must always choose the smallest valid row.
  • scatter may partially fill several rows.
  • k can exceed the capacity of any single row, making gather immediately impossible.
  • After many operations, the hall may be almost full, so efficient skipping of exhausted rows is necessary.

Approaches

Brute Force Approach

The most straightforward solution is to explicitly track how many seats remain in every row.

For gather(k, maxRow), we scan rows from 0 to maxRow and check whether the row has at least k consecutive seats available. Since seats are always allocated from left to right, this simply means checking whether the remaining capacity is at least k.

For scatter(k, maxRow), we first count how many seats remain across rows 0 through maxRow. If enough seats exist, we iterate row by row and consume seats until all k spectators are seated.

This approach is logically correct because it directly follows the problem rules. However, the performance is poor. In the worst case, each operation may scan up to O(n) rows, and there can be 5 * 10^4 operations. That leads to roughly 2.5 * 10^9 row inspections in the worst case, which is far too slow.

Optimal Approach

The key insight is that we repeatedly need two types of aggregated information over row ranges:

  1. The maximum number of remaining seats in any row, for gather
  2. The total number of remaining seats across rows, for scatter

A segment tree is ideal because it supports both range aggregation and point updates efficiently.

We maintain:

  • maxTree[node], the maximum remaining seats in that segment
  • sumTree[node], the total remaining seats in that segment

Each row initially contains m available seats.

For gather, we use the max segment tree to locate the leftmost row with at least k available seats.

For scatter, we use the sum segment tree to determine whether enough total seats exist. If so, we greedily consume seats from the smallest rows.

Each update only affects one row, so segment tree updates take O(log n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per operation O(n) Scans rows repeatedly
Optimal O(log n) for gather, O(log n + affected rows) for scatter O(n) Uses segment tree for efficient aggregation

Algorithm Walkthrough

Data Structures

We maintain three important pieces of state:

  • used[row], the number of seats already occupied in each row
  • maxTree, storing the maximum remaining seats in each segment
  • sumTree, storing the total remaining seats in each segment

Initially:

  • used[row] = 0
  • every row has m available seats

Gather Operation

  1. First, check whether any row in range [0, maxRow] has at least k free seats.
  2. We query the segment tree maximum over that range. If the maximum is less than k, gathering is impossible.
  3. Otherwise, we recursively search the segment tree for the leftmost row whose remaining capacity is at least k.
  4. Once the row is found, the starting seat index is simply used[row], because seats are always allocated from left to right.
  5. We increase used[row] by k.
  6. We update the segment tree values for that row:
  • remaining seats become m - used[row]
  • both max and sum values are refreshed upward through the tree
  1. Return [row, startingSeat].

Scatter Operation

  1. First, compute the total remaining seats in rows [0, maxRow].
  2. If the total is smaller than k, return false.
  3. Otherwise, we begin allocating seats greedily from the smallest available row.
  4. For each row:
  • determine how many seats remain
  • allocate as many as possible
  • update used[row]
  • update the segment tree
  1. Continue until all k spectators are seated.
  2. Return true.

Why it works

The algorithm works because the segment tree always maintains accurate aggregated information for every row range.

The maxTree invariant guarantees that we can efficiently determine whether some row can fit a consecutive block of size k, and locate the leftmost such row.

The sumTree invariant guarantees that we can correctly determine whether enough total seats exist for scatter.

Because seats are always allocated from left to right and rows are processed in increasing order, the implementation exactly matches the required tie breaking rules.

Python Solution

from typing import List

class BookMyShow:

    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m

        self.used = [0] * n

        size = 4 * n
        self.max_tree = [0] * size
        self.sum_tree = [0] * size

        self._build(1, 0, n - 1)

        self.scatter_row = 0

    def _build(self, node: int, left: int, right: int) -> None:
        if left == right:
            self.max_tree[node] = self.m
            self.sum_tree[node] = self.m
            return

        mid = (left + right) // 2

        self._build(node * 2, left, mid)
        self._build(node * 2 + 1, mid + 1, right)

        self.max_tree[node] = self.m
        self.sum_tree[node] = (right - left + 1) * self.m

    def _update(self, node: int, left: int, right: int, idx: int) -> None:
        if left == right:
            remaining = self.m - self.used[idx]
            self.max_tree[node] = remaining
            self.sum_tree[node] = remaining
            return

        mid = (left + right) // 2

        if idx <= mid:
            self._update(node * 2, left, mid, idx)
        else:
            self._update(node * 2 + 1, mid + 1, right, idx)

        self.max_tree[node] = max(
            self.max_tree[node * 2],
            self.max_tree[node * 2 + 1]
        )

        self.sum_tree[node] = (
            self.sum_tree[node * 2]
            + self.sum_tree[node * 2 + 1]
        )

    def _query_max(
        self,
        node: int,
        left: int,
        right: int,
        ql: int,
        qr: int
    ) -> int:
        if ql <= left and right <= qr:
            return self.max_tree[node]

        mid = (left + right) // 2
        result = 0

        if ql <= mid:
            result = max(
                result,
                self._query_max(node * 2, left, mid, ql, qr)
            )

        if qr > mid:
            result = max(
                result,
                self._query_max(node * 2 + 1, mid + 1, right, ql, qr)
            )

        return result

    def _query_sum(
        self,
        node: int,
        left: int,
        right: int,
        ql: int,
        qr: int
    ) -> int:
        if ql <= left and right <= qr:
            return self.sum_tree[node]

        mid = (left + right) // 2
        total = 0

        if ql <= mid:
            total += self._query_sum(
                node * 2,
                left,
                mid,
                ql,
                qr
            )

        if qr > mid:
            total += self._query_sum(
                node * 2 + 1,
                mid + 1,
                right,
                ql,
                qr
            )

        return total

    def _find_row(
        self,
        node: int,
        left: int,
        right: int,
        max_row: int,
        k: int
    ) -> int:
        if left == right:
            return left

        mid = (left + right) // 2

        if (
            left <= max_row
            and self.max_tree[node * 2] >= k
        ):
            return self._find_row(
                node * 2,
                left,
                mid,
                max_row,
                k
            )

        return self._find_row(
            node * 2 + 1,
            mid + 1,
            right,
            max_row,
            k
        )

    def gather(self, k: int, maxRow: int) -> List[int]:
        if self._query_max(1, 0, self.n - 1, 0, maxRow) < k:
            return []

        row = self._find_row(1, 0, self.n - 1, maxRow, k)

        seat = self.used[row]

        self.used[row] += k

        self._update(1, 0, self.n - 1, row)

        return [row, seat]

    def scatter(self, k: int, maxRow: int) -> bool:
        available = self._query_sum(1, 0, self.n - 1, 0, maxRow)

        if available < k:
            return False

        row = self.scatter_row

        while k > 0 and row <= maxRow:
            remaining = self.m - self.used[row]

            if remaining == 0:
                row += 1
                continue

            take = min(k, remaining)

            self.used[row] += take

            self._update(1, 0, self.n - 1, row)

            k -= take

            if self.used[row] == self.m:
                row += 1

        self.scatter_row = row

        return True

The implementation begins by constructing a segment tree where every row initially has m available seats.

The _build method initializes the tree. Each leaf corresponds to one row. Internal nodes aggregate information from children.

The _update method refreshes one row after seats are allocated. Since only one row changes at a time, updates propagate upward efficiently.

The _query_max method determines whether some row in a range can satisfy a gather request.

The _query_sum method computes total remaining capacity for scatter.

The _find_row method performs a binary search over the segment tree structure itself. It always explores the left child first, guaranteeing that we find the smallest valid row.

The scatter_row pointer is an optimization. Once a row becomes completely full, future scatter operations never need to revisit it.

Go Solution

package main

type BookMyShow struct {
	n          int
	m          int
	used       []int
	maxTree    []int
	sumTree    []int64
	scatterRow int
}

func Constructor(n int, m int) BookMyShow {
	bms := BookMyShow{
		n:          n,
		m:          m,
		used:       make([]int, n),
		maxTree:    make([]int, 4*n),
		sumTree:    make([]int64, 4*n),
		scatterRow: 0,
	}

	bms.build(1, 0, n-1)

	return bms
}

func (this *BookMyShow) build(node int, left int, right int) {
	if left == right {
		this.maxTree[node] = this.m
		this.sumTree[node] = int64(this.m)
		return
	}

	mid := (left + right) / 2

	this.build(node*2, left, mid)
	this.build(node*2+1, mid+1, right)

	this.maxTree[node] = this.m
	this.sumTree[node] = int64(right-left+1) * int64(this.m)
}

func (this *BookMyShow) update(
	node int,
	left int,
	right int,
	idx int,
) {
	if left == right {
		remaining := this.m - this.used[idx]
		this.maxTree[node] = remaining
		this.sumTree[node] = int64(remaining)
		return
	}

	mid := (left + right) / 2

	if idx <= mid {
		this.update(node*2, left, mid, idx)
	} else {
		this.update(node*2+1, mid+1, right, idx)
	}

	if this.maxTree[node*2] > this.maxTree[node*2+1] {
		this.maxTree[node] = this.maxTree[node*2]
	} else {
		this.maxTree[node] = this.maxTree[node*2+1]
	}

	this.sumTree[node] =
		this.sumTree[node*2] +
			this.sumTree[node*2+1]
}

func (this *BookMyShow) queryMax(
	node int,
	left int,
	right int,
	ql int,
	qr int,
) int {
	if ql <= left && right <= qr {
		return this.maxTree[node]
	}

	mid := (left + right) / 2
	result := 0

	if ql <= mid {
		val := this.queryMax(node*2, left, mid, ql, qr)
		if val > result {
			result = val
		}
	}

	if qr > mid {
		val := this.queryMax(node*2+1, mid+1, right, ql, qr)
		if val > result {
			result = val
		}
	}

	return result
}

func (this *BookMyShow) querySum(
	node int,
	left int,
	right int,
	ql int,
	qr int,
) int64 {
	if ql <= left && right <= qr {
		return this.sumTree[node]
	}

	mid := (left + right) / 2
	var total int64 = 0

	if ql <= mid {
		total += this.querySum(node*2, left, mid, ql, qr)
	}

	if qr > mid {
		total += this.querySum(node*2+1, mid+1, right, ql, qr)
	}

	return total
}

func (this *BookMyShow) findRow(
	node int,
	left int,
	right int,
	maxRow int,
	k int,
) int {
	if left == right {
		return left
	}

	mid := (left + right) / 2

	if mid >= left &&
		this.maxTree[node*2] >= k &&
		left <= maxRow {

		return this.findRow(
			node*2,
			left,
			mid,
			maxRow,
			k,
		)
	}

	return this.findRow(
		node*2+1,
		mid+1,
		right,
		maxRow,
		k,
	)
}

func (this *BookMyShow) Gather(
	k int,
	maxRow int,
) []int {
	if this.queryMax(1, 0, this.n-1, 0, maxRow) < k {
		return []int{}
	}

	row := this.findRow(1, 0, this.n-1, maxRow, k)

	seat := this.used[row]

	this.used[row] += k

	this.update(1, 0, this.n-1, row)

	return []int{row, seat}
}

func (this *BookMyShow) Scatter(
	k int,
	maxRow int,
) bool {
	available := this.querySum(1, 0, this.n-1, 0, maxRow)

	if available < int64(k) {
		return false
	}

	row := this.scatterRow

	for k > 0 && row <= maxRow {
		remaining := this.m - this.used[row]

		if remaining == 0 {
			row++
			continue
		}

		take := remaining
		if k < take {
			take = k
		}

		this.used[row] += take

		this.update(1, 0, this.n-1, row)

		k -= take

		if this.used[row] == this.m {
			row++
		}
	}

	this.scatterRow = row

	return true
}

The Go implementation mirrors the Python logic closely, but there are a few language specific details worth noting.

The total number of seats can exceed 32 bit integer range because n * m may be as large as 5 * 10^13. For this reason, sumTree uses int64.

Go does not have dynamic lists like Python, so empty results are returned as []int{}.

Methods are implemented with pointer receivers so updates modify the shared structure correctly.

Worked Examples

Example 1

Input:
BookMyShow(2, 5)
gather(4, 0)
gather(2, 0)
scatter(5, 1)
scatter(5, 1)

Initial state:

Row Used Remaining
0 0 5
1 0 5

Operation 1: gather(4, 0)

We search rows [0, 0].

Row 0 has 5 remaining seats, which is enough.

We allocate seats [0,1,2,3].

Updated state:

Row Used Remaining
0 4 1
1 0 5

Return:

[0, 0]

Operation 2: gather(2, 0)

We search rows [0,0].

Row 0 only has 1 remaining seat.

No valid row exists.

Return:

[]

State remains unchanged.

Operation 3: scatter(5, 1)

Total remaining seats:

  • Row 0: 1
  • Row 1: 5

Total = 6, so allocation succeeds.

We allocate:

  • 1 seat in row 0
  • 4 seats in row 1

Updated state:

Row Used Remaining
0 5 0
1 4 1

Return:

true

Operation 4: scatter(5, 1)

Total remaining seats:

  • Row 0: 0
  • Row 1: 1

Total = 1.

Not enough seats.

Return:

false

Complexity Analysis

Measure Complexity Explanation
Time O(log n) for gather, amortized O(log n) for scatter Segment tree queries and updates dominate
Space O(n) Segment tree and row tracking arrays

The segment tree contains O(n) nodes.

Each gather operation performs:

  • one max query
  • one search down the tree
  • one update

Each step costs O(log n).

For scatter, rows are only advanced forward because of the scatter_row pointer. Across all operations, each row becomes full at most once. Therefore, the total extra scanning work is amortized linear over the entire execution.

Test Cases

from typing import List

# Example case
bms = BookMyShow(2, 5)
assert bms.gather(4, 0) == [0, 0]  # basic gather
assert bms.gather(2, 0) == []  # insufficient consecutive seats
assert bms.scatter(5, 1) is True  # scatter across rows
assert bms.scatter(5, 1) is False  # insufficient total seats

# Single row exact fit
bms = BookMyShow(1, 5)
assert bms.gather(5, 0) == [0, 0]  # fill entire row
assert bms.gather(1, 0) == []  # row now full

# Scatter partially fills rows
bms = BookMyShow(3, 4)
assert bms.scatter(6, 2) is True  # fills row 0 and part of row 1
assert bms.gather(3, 1) == []  # row 1 only has 2 seats left
assert bms.gather(2, 1) == [1, 2]  # valid consecutive block

# Gather prefers smallest row
bms = BookMyShow(3, 5)
assert bms.gather(2, 2) == [0, 0]
assert bms.gather(2, 2) == [0, 2]
assert bms.gather(2, 2) == [1, 0]  # row 0 no longer fits

# Scatter respects maxRow
bms = BookMyShow(3, 5)
assert bms.scatter(6, 0) is False  # only row 0 available

# Large k impossible for gather
bms = BookMyShow(5, 10)
assert bms.gather(11, 4) == []  # row capacity exceeded

# Full exhaustion
bms = BookMyShow(2, 2)
assert bms.scatter(4, 1) is True  # consume everything
assert bms.scatter(1, 1) is False  # no seats remain
assert bms.gather(1, 1) == []  # no consecutive seat exists

# Scatter after gathers
bms = BookMyShow(2, 5)
assert bms.gather(3, 1) == [0, 0]
assert bms.scatter(4, 1) is True  # uses row 0 remainder + row 1
assert bms.gather(2, 1) == []  # insufficient consecutive seats
Test Why
Example from prompt Verifies correctness against official behavior
Single row exact fit Tests complete exhaustion
Scatter partially fills rows Ensures partial row handling works
Gather prefers smallest row Verifies tie breaking rules
Scatter respects maxRow Ensures row restriction is enforced
Large k impossible Tests impossible gather requests
Full exhaustion Verifies fully occupied hall behavior
Scatter after gathers Tests mixed operation ordering

Edge Cases

One important edge case occurs when k exceeds the capacity of every row. Since a gather request requires consecutive seats in one row, no allocation is possible even if many total seats remain across multiple rows. The implementation handles this naturally because the segment tree maximum query immediately determines that no row has enough remaining capacity.

Another tricky case happens when rows become completely full. A naive scatter implementation might repeatedly revisit exhausted rows, causing severe performance degradation. The solution avoids this problem using the scatter_row pointer, which permanently skips rows that are already full.

A third important edge case involves tie breaking. The problem requires always choosing the smallest possible row and then the smallest possible seat number. This can easily be implemented incorrectly if the search order is not carefully controlled. The segment tree search always explores the left child first, guaranteeing that the first valid row discovered is the smallest valid row. Since seats are allocated from left to right, the starting seat index is always minimal as well.