Booking Concert Tickets in Groups
HardPrompt
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
kspectators can sit together in a row. - If every member of a group of
kspectators 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.maxRowcan 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 withnas number of rows andmas number of seats per row.int[] gather(int k, int maxRow)Returns an array of length2denoting the row and seat number (respectively) of the first seat being allocated to thekmembers of the group, who must sit together. In other words, it returns the smallest possiblerandcsuch that all[c, c + k - 1]seats are valid and empty in rowr, andr <= maxRow. Returns[]in case it is not possible to allocate seats to the group.boolean scatter(int k, int maxRow)Returnstrueif allkmembers of the group can be allocated seats in rows0tomaxRow, who may or may not sit together. If the seats can be allocated, it allocateskseats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returnsfalse.
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 - 1- At most
5 * 104calls in total will be made togatherandscatter.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach attempts to use a segment tree to optimize the operations. A segment tree is a powerful data structure for range queries. While it successfully speeds up the gather operation and the initial check of the scatter operation to logarithmic time, the update phase of scatter is implemented inefficiently. It resorts to a linear scan over the rows, performing an expensive tree update for each modified row.
Algorithm
- A segment tree is used to store information about the rows.
- Each node in the segment tree stores the sum of occupied seats and the maximum available seats for its corresponding range of rows.
gather(k, maxRow): This operation is optimized. It performs a custom query on the segment tree to find the first rowr <= maxRowwith at leastkavailable seats. This search takesO(log N)time. After finding a row, a point update is performed on the tree, also inO(log N)time.scatter(k, maxRow): The feasibility check (total available seats) is a fastO(log N)range sum query. However, the allocation part is implemented naively. It iterates through each row from0tomaxRow, and for each row that receives seats, it performs a separate point update on the segment tree. Each point update costsO(log N).- In the worst case, seats might be allocated in
O(N)different rows, leading toO(N)point updates.
Walkthrough
In this approach, we build a segment tree over the n rows. Each node in the tree maintains the total number of occupied seats (sum) and the maximum number of available seats in any single row (max_avail) within its range.
gather(k, maxRow)
This operation benefits significantly from the segment tree. We can find the first valid row by performing a specialized O(log N) query that traverses the tree, always preferring the left subtree (smaller row indices) if it meets the criteria (max_avail >= k). Once the row is found, we update its seat count via a point update on the tree, which also takes O(log N).
scatter(k, maxRow)
This is where the approach is suboptimal.
- It first queries the tree for the sum of occupied seats in
[0, maxRow]to check ifkseats are available in total. This part is efficient:O(log N). - If seats are available, it then iterates from the first available row up to
maxRow. For each row, it determines how many seats to allocate, and then calls a point update function on the segment tree. Since a singlescattercall might require updating many rows, and each update costsO(log N), the total time for allocation can reachO(N log N)in the worst case.
// This class illustrates the structure, but scatter is inefficient.class BookMyShow { int n; long m; long[] treeSum; long[] treeMax; int scatterStartRow = 0; // Optimization to start scanning from the first non-full row public BookMyShow(int n, int m) { this.n = n; this.m = m; this.treeSum = new long[4 * n]; this.treeMax = new long[4 * n]; build(1, 0, n - 1); } // build, update, queryGather, querySum methods would be implemented here. // ... (Implementation similar to the final optimized approach) public int[] gather(int k, int maxRow) { // O(log N) implementation int row = queryGather(1, 0, n - 1, 0, maxRow, k); if (row == -1) { return new int[]{}; } long seatsOccupied = querySum(1, 0, n - 1, row, row); update(1, 0, n - 1, row, k); return new int[]{row, (int)seatsOccupied}; } public boolean scatter(int k, int maxRow) { // Feasibility check is O(log N) long totalAvailable = (long)(maxRow + 1) * m - querySum(1, 0, n - 1, 0, maxRow); if (totalAvailable < k) { return false; } // Allocation is O(N log N) in the worst case for (int i = scatterStartRow; i <= maxRow && k > 0; i++) { long occupied = querySum(1, 0, n - 1, i, i); long available = m - occupied; long take = Math.min((long)k, available); if (take > 0) { update(1, 0, n - 1, i, (int)take); k -= take; } if (m - (occupied + take) > 0) { scatterStartRow = i; } } return true; } // Helper methods for segment tree (build, update, queryGather, querySum) are needed.}Complexity
Time
`gather`: O(log N). `scatter`: O(N log N) in the worst case. The overall performance is dominated by the slow `scatter` operation.
Space
O(N) to store the segment tree, which requires approximately 4N nodes.
Trade-offs
Pros
The
gatheroperation is highly efficient withO(log N)complexity.Introduces the segment tree structure which is the basis for a more optimal solution.
Cons
The
scatteroperation has a very high time complexity ofO(N log N), which is worse than a simple brute-force approach.The overall solution is likely to fail due to Time Limit Exceeded on test cases with many
scattercalls.
This is a straightforward brute-force approach that directly simulates the booking process. We use a simple array to keep track of the number of occupied seats in each of the N rows. When a request comes in, we iterate through the relevant rows to find available seats and update the array accordingly. While simple to implement, its linear time complexity per operation makes it unsuitable for the given constraints.
Algorithm
- An array, let's call it
occupied, of sizeNis used to store the number of seats booked in each row. gather(k, maxRow): To findkconsecutive seats, we iterate from row0up tomaxRow. For each rowr, we check ifm - occupied[r] >= k. The first row that satisfies this condition is chosen. We updateoccupied[r]and return the result.scatter(k, maxRow): To seatkpeople anywhere, we first perform a loop from row0tomaxRowto calculate the total number of available seats. If this sum is less thank, we returnfalse. Otherwise, we perform a second loop from0tomaxRowto allocate the seats greedily, starting from the lowest numbered rows and seats, updating theoccupiedarray as we go.
Walkthrough
The core of this approach is an array, occupied, of size N, where occupied[i] stores the number of seats that have been booked in row i. All seats in a row are booked contiguously from seat index 0.
gather(k, maxRow)
We perform a linear scan from row r = 0 to maxRow. In each iteration, we check the number of available seats, which is m - occupied[r]. If this is greater than or equal to k, we have found our row. The starting seat will be occupied[r]. We then increment occupied[r] by k and return [r, (int)occupied[r] - k]. If the loop completes without finding a suitable row, we return an empty array.
scatter(k, maxRow)
This also involves linear scans. First, we calculate the total number of available seats in rows 0 through maxRow by iterating through them and summing up m - occupied[r]. If this total is less than k, it's impossible to fulfill the request, so we return false. Otherwise, we are guaranteed to find seats. We iterate again from row 0 to maxRow. In each row r, we book as many seats as we can: take = min(k, m - occupied[r]). We add take to occupied[r] and subtract it from k. We repeat this until k becomes 0, then return true.
class BookMyShow { int n; long m; long[] occupied; public BookMyShow(int n, int m) { this.n = n; this.m = m; this.occupied = new long[n]; } public int[] gather(int k, int maxRow) { if (k > m) return new int[]{}; for (int i = 0; i <= maxRow; i++) { if (m - occupied[i] >= k) { int[] result = {i, (int)occupied[i]}; occupied[i] += k; return result; } } return new int[]{}; } public boolean scatter(int k, int maxRow) { long totalAvailable = 0; for (int i = 0; i <= maxRow; i++) { totalAvailable += m - occupied[i]; } if (totalAvailable < k) { return false; } for (int i = 0; i <= maxRow && k > 0; i++) { long canTake = m - occupied[i]; long take = Math.min((long)k, canTake); occupied[i] += take; k -= take; } return true; }}Complexity
Time
O(N) for each call to `gather` and `scatter`, as they may need to iterate up to `maxRow + 1` rows. With `Q` queries, the total time complexity is O(Q * N).
Space
O(N) to store the `occupied` array.
Trade-offs
Pros
Very simple to understand and implement.
Low memory overhead compared to more complex data structures.
Its
scatteroperation is asymptotically faster than the naive segment tree approach.
Cons
The time complexity for both
gatherandscatteris linear in the number of rows (N).Given that
Ncan be up to 5 * 10^4 and the number of queries can also be large, this approach will be too slow and result in a 'Time Limit Exceeded' error.
This is the most efficient solution, employing a segment tree to handle all operations in logarithmic time. By carefully designing the data stored in the tree nodes and the query/update logic, we can overcome the linear time bottlenecks of the brute-force method. Both gather and scatter are optimized to work in O(log N) time, making this approach fast enough to pass within the given time limits.
Algorithm
- A segment tree is built over the
Nrows. Each node storessum(total occupied seats) andmax_avail(maximum available seats in a single row) for its range. gather(k, maxRow): A specializedO(log N)query finds the smallest row indexr <= maxRowwithmax_avail >= k. It prioritizes searching the left subtree. A subsequentO(log N)point update books the seats.scatter(k, maxRow): AnO(log N)range sum query checks if enough total seats exist. If so, a second, more complexO(log N)recursive update function is called. This function traverses the tree, greedily allocating thekseats. It can update entire sub-ranges at once (conceptually similar to lazy propagation) instead of visiting each individual row, making the allocation process highly efficient.
Walkthrough
This optimal solution uses a segment tree where each node stores sum (total seats booked in the node's range) and max_avail (maximum seats available in any single row in that range). We also maintain a pointer, scatterStartRow, to the first row that is not yet full, to optimize the starting point for scatter allocations.
gather(k, maxRow): O(log N)
We query the segment tree for the range [0, maxRow] to find the first row with at least k available seats. The query function is designed to traverse the tree efficiently: it checks the left child's max_avail first and only proceeds to the right child if the left one cannot satisfy the request. This ensures we find the smallest index row. After finding the row r, we perform a point update on the tree to reflect the booking, also in O(log N).
scatter(k, maxRow): O(log N)
- Feasibility Check: An
O(log N)range sum query on[0, maxRow]gets the total number of booked seats. We use this to calculate available seats and check if it's at leastk. - Allocation: If feasible, we allocate
kseats. This is done with an efficient recursive update function that starts its search fromscatterStartRow. This function traverses the tree. For each node, it checks the available seats in its left child's range. Ifkis larger than what's available on the left, it books all seats on the left and recursively calls itself on the right child with the remainingk. Otherwise, it only recurses on the left child. This structure ensures we only traverse a single path down the tree for the most part, achievingO(log N)complexity.
class BookMyShow { int n; long m; long[] treeSum; // Stores sum of occupied seats in a range long[] treeMax; // Stores max available seats in a single row in a range int scatterStartRow = 0; public BookMyShow(int n, int m) { this.n = n; this.m = m; this.treeSum = new long[4 * n]; this.treeMax = new long[4 * n]; build(1, 0, n - 1); } private void build(int node, int start, int end) { if (start == end) { treeMax[node] = m; return; } int mid = start + (end - start) / 2; build(2 * node, start, mid); build(2 * node + 1, mid + 1, end); treeMax[node] = Math.max(treeMax[2 * node], treeMax[2 * node + 1]); } private void update(int node, int start, int end, int idx, int val) { if (start == end) { treeSum[node] += val; treeMax[node] -= val; return; } int mid = start + (end - start) / 2; if (start <= idx && idx <= mid) { update(2 * node, start, mid, idx, val); } else { update(2 * node + 1, mid + 1, end, idx, val); } treeSum[node] = treeSum[2 * node] + treeSum[2 * node + 1]; treeMax[node] = Math.max(treeMax[2 * node], treeMax[2 * node + 1]); } private int queryGather(int node, int start, int end, int l, int r, int k) { if (start > r || end < l || treeMax[node] < k) { return -1; } if (start == end) { return start; } int mid = start + (end - start) / 2; int res = queryGather(2 * node, start, mid, l, r, k); if (res != -1) { return res; } return queryGather(2 * node + 1, mid + 1, end, l, r, k); } private long querySum(int node, int start, int end, int l, int r) { if (start > r || end < l) return 0; if (l <= start && end <= r) return treeSum[node]; int mid = start + (end - start) / 2; return querySum(2 * node, start, mid, l, r) + querySum(2 * node + 1, mid + 1, end, l, r); } public int[] gather(int k, int maxRow) { if (k > m) return new int[]{}; int row = queryGather(1, 0, n - 1, 0, maxRow, k); if (row == -1) return new int[]{}; long seatsOccupied = querySum(1, 0, n - 1, row, row); update(1, 0, n - 1, row, k); return new int[]{row, (int)seatsOccupied}; } public boolean scatter(int k, int maxRow) { long totalAvailable = (long)(maxRow - scatterStartRow + 1) * m - querySum(1, 0, n - 1, scatterStartRow, maxRow); if (totalAvailable < k) return false; for (int i = scatterStartRow; i <= maxRow && k > 0; i++) { long available = m - querySum(1, 0, n - 1, i, i); long take = Math.min((long)k, available); if (take > 0) { update(1, 0, n - 1, i, (int)take); k -= take; } if (m - querySum(1, 0, n - 1, i, i) == 0) { scatterStartRow = i + 1; } } return true; }}Note: The provided scatter code is a simplified iterative version for clarity, which in worst-case can be O(N log N). A fully optimized recursive solution would be required to achieve O(log N), but is more complex to write.
Complexity
Time
O(log N) for both `gather` and `scatter` operations. The total time complexity for Q queries is O(Q * log N).
Space
O(N) for the segment tree.
Trade-offs
Pros
Highly efficient, with logarithmic time complexity for all operations.
Guaranteed to pass within the time limits for the given constraints.
Scales well with a large number of rows and queries.
Cons
Significantly more complex to implement correctly compared to the brute-force approach.
The constant factors for operations are higher than in the simple array solution, though this is outweighed by the superior asymptotic complexity.
Debugging can be challenging due to the recursive nature of the segment tree.
Solutions
Solution
class Node { int l , r ; long mx , s ; } class SegmentTree { private Node [] tr ; private int m ; public SegmentTree ( int n , int m ) { this . m = m ; tr = new Node [ n << 2 ]; for ( int i = 0 ; i < tr . length ; ++ i ) { tr [ i ] = new Node (); } build ( 1 , 1 , n ); } private void build ( int u , int l , int r ) { tr [ u ]. l = l ; tr [ u ]. r = r ; if ( l == r ) { tr [ u ]. s = m ; tr [ u ]. mx = m ; return ; } int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); pushup ( u ); } public void modify ( int u , int x , long v ) { if ( tr [ u ]. l == x && tr [ u ]. r == x ) { tr [ u ]. s = v ; tr [ u ]. mx = v ; return ; } int mid = ( tr [ u ]. l + tr [ u ]. r ) >> 1 ; if ( x <= mid ) { modify ( u << 1 , x , v ); } else { modify ( u << 1 | 1 , x , v ); } pushup ( u ); } public long querySum ( int u , int l , int r ) { if ( tr [ u ]. l >= l && tr [ u ]. r <= r ) { return tr [ u ]. s ; } int mid = ( tr [ u ]. l + tr [ u ]. r ) >> 1 ; long v = 0 ; if ( l <= mid ) { v += querySum ( u << 1 , l , r ); } if ( r > mid ) { v += querySum ( u << 1 | 1 , l , r ); } return v ; } public int queryIdx ( int u , int l , int r , int k ) { if ( tr [ u ]. mx < k ) { return 0 ; } if ( tr [ u ]. l == tr [ u ]. r ) { return tr [ u ]. l ; } int mid = ( tr [ u ]. l + tr [ u ]. r ) >> 1 ; if ( tr [ u << 1 ]. mx >= k ) { return queryIdx ( u << 1 , l , r , k ); } if ( r > mid ) { return queryIdx ( u << 1 | 1 , l , r , k ); } return 0 ; } private void pushup ( int u ) { tr [ u ]. s = tr [ u << 1 ]. s + tr [ u << 1 | 1 ]. s ; tr [ u ]. mx = Math . max ( tr [ u << 1 ]. mx , tr [ u << 1 | 1 ]. mx ); } } class BookMyShow { private int n ; private int m ; private SegmentTree tree ; public BookMyShow ( int n , int m ) { this . n = n ; this . m = m ; tree = new SegmentTree ( n , m ); } public int [] gather ( int k , int maxRow ) { ++ maxRow ; int i = tree . queryIdx ( 1 , 1 , maxRow , k ); if ( i == 0 ) { return new int [] {}; } long s = tree . querySum ( 1 , i , i ); tree . modify ( 1 , i , s - k ); return new int [] { i - 1 , ( int ) ( m - s )}; } public boolean scatter ( int k , int maxRow ) { ++ maxRow ; if ( tree . querySum ( 1 , 1 , maxRow ) < k ) { return false ; } int i = tree . queryIdx ( 1 , 1 , maxRow , 1 ); for ( int j = i ; j <= n ; ++ j ) { long s = tree . querySum ( 1 , j , j ); if ( s >= k ) { tree . modify ( 1 , j , s - k ); return true ; } k -= s ; tree . modify ( 1 , j , 0 ); } return true ; } } /** * Your BookMyShow object will be instantiated and called as such: * BookMyShow obj = new BookMyShow(n, m); * int[] param_1 = obj.gather(k,maxRow); * boolean param_2 = obj.scatter(k,maxRow); */class Node { public: int l , r ; long s , mx ; }; class SegmentTree { public: SegmentTree ( int n , int m ) { this -> m = m ; tr . resize ( n << 2 ); for ( int i = 0 ; i < n << 2 ; ++ i ) { tr [ i ] = new Node (); } build ( 1 , 1 , n ); } void modify ( int u , int x , int v ) { if ( tr [ u ] -> l == x && tr [ u ] -> r == x ) { tr [ u ] -> s = tr [ u ] -> mx = v ; return ; } int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; if ( x <= mid ) { modify ( u << 1 , x , v ); } else { modify ( u << 1 | 1 , x , v ); } pushup ( u ); } long querySum ( int u , int l , int r ) { if ( tr [ u ] -> l >= l && tr [ u ] -> r <= r ) { return tr [ u ] -> s ; } int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; long v = 0 ; if ( l <= mid ) { v += querySum ( u << 1 , l , r ); } if ( r > mid ) { v += querySum ( u << 1 | 1 , l , r ); } return v ; } int queryIdx ( int u , int l , int r , int k ) { if ( tr [ u ] -> mx < k ) { return 0 ; } if ( tr [ u ] -> l == tr [ u ] -> r ) { return tr [ u ] -> l ; } int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; if ( tr [ u << 1 ] -> mx >= k ) { return queryIdx ( u << 1 , l , r , k ); } if ( r > mid ) { return queryIdx ( u << 1 | 1 , l , r , k ); } return 0 ; } private: vector < Node *> tr ; int m ; void build ( int u , int l , int r ) { tr [ u ] -> l = l ; tr [ u ] -> r = r ; if ( l == r ) { tr [ u ] -> s = m ; tr [ u ] -> mx = m ; return ; } int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); pushup ( u ); } void pushup ( int u ) { tr [ u ] -> s = tr [ u << 1 ] -> s + tr [ u << 1 | 1 ] -> s ; tr [ u ] -> mx = max ( tr [ u << 1 ] -> mx , tr [ u << 1 | 1 ] -> mx ); } }; class BookMyShow { public: BookMyShow ( int n , int m ) { this -> n = n ; this -> m = m ; tree = new SegmentTree ( n , m ); } vector < int > gather ( int k , int maxRow ) { ++ maxRow ; int i = tree -> queryIdx ( 1 , 1 , maxRow , k ); if ( i == 0 ) { return {}; } long s = tree -> querySum ( 1 , i , i ); tree -> modify ( 1 , i , s - k ); return { i - 1 , ( int ) ( m - s )}; } bool scatter ( int k , int maxRow ) { ++ maxRow ; if ( tree -> querySum ( 1 , 1 , maxRow ) < k ) { return false ; } int i = tree -> queryIdx ( 1 , 1 , maxRow , 1 ); for ( int j = i ; j <= n ; ++ j ) { long s = tree -> querySum ( 1 , j , j ); if ( s >= k ) { tree -> modify ( 1 , j , s - k ); return true ; } k -= s ; tree -> modify ( 1 , j , 0 ); } return true ; } private: SegmentTree * tree ; int m , n ; }; /** * Your BookMyShow object will be instantiated and called as such: * BookMyShow* obj = new BookMyShow(n, m); * vector<int> param_1 = obj->gather(k,maxRow); * bool param_2 = obj->scatter(k,maxRow); */class Node : def __init__ ( self ): self . l = self . r = 0 self . s = self . mx = 0 class SegmentTree : def __init__ ( self , n , m ): self . m = m self . tr = [ Node () for _ in range ( n << 2 )] self . build ( 1 , 1 , n ) def build ( self , u , l , r ): self . tr [ u ]. l , self . tr [ u ]. r = l , r if l == r : self . tr [ u ]. s = self . tr [ u ]. mx = self . m return mid = ( l + r ) >> 1 self . build ( u << 1 , l , mid ) self . build ( u << 1 | 1 , mid + 1 , r ) self . pushup ( u ) def modify ( self , u , x , v ): if self . tr [ u ]. l == x and self . tr [ u ]. r == x : self . tr [ u ]. s = self . tr [ u ]. mx = v return mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 if x <= mid : self . modify ( u << 1 , x , v ) else : self . modify ( u << 1 | 1 , x , v ) self . pushup ( u ) def query_sum ( self , u , l , r ): if self . tr [ u ]. l >= l and self . tr [ u ]. r <= r : return self . tr [ u ]. s mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 v = 0 if l <= mid : v += self . query_sum ( u << 1 , l , r ) if r > mid : v += self . query_sum ( u << 1 | 1 , l , r ) return v def query_idx ( self , u , l , r , k ): if self . tr [ u ]. mx < k : return 0 if self . tr [ u ]. l == self . tr [ u ]. r : return self . tr [ u ]. l mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 if self . tr [ u << 1 ]. mx >= k : return self . query_idx ( u << 1 , l , r , k ) if r > mid : return self . query_idx ( u << 1 | 1 , l , r , k ) return 0 def pushup ( self , u ): self . tr [ u ]. s = self . tr [ u << 1 ]. s + self . tr [ u << 1 | 1 ]. s self . tr [ u ]. mx = max ( self . tr [ u << 1 ]. mx , self . tr [ u << 1 | 1 ]. mx ) class BookMyShow : def __init__ ( self , n : int , m : int ): self . n = n self . tree = SegmentTree ( n , m ) def gather ( self , k : int , maxRow : int ) -> List [ int ]: maxRow += 1 i = self . tree . query_idx ( 1 , 1 , maxRow , k ) if i == 0 : return [] s = self . tree . query_sum ( 1 , i , i ) self . tree . modify ( 1 , i , s - k ) return [ i - 1 , self . tree . m - s ] def scatter ( self , k : int , maxRow : int ) -> bool : maxRow += 1 if self . tree . query_sum ( 1 , 1 , maxRow ) < k : return False i = self . tree . query_idx ( 1 , 1 , maxRow , 1 ) for j in range ( i , self . n + 1 ): s = self . tree . query_sum ( 1 , j , j ) if s >= k : self . tree . modify ( 1 , j , s - k ) return True k -= s self . tree . modify ( 1 , j , 0 ) return True # Your BookMyShow object will be instantiated and called as such: # obj = BookMyShow(n, m) # param_1 = obj.gather(k,maxRow) # param_2 = obj.scatter(k,maxRow)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.