Approach Framework
Intuition
Intuitively, there are two operations: update
, which updates our notion of the board (number line) after dropping a square; and query
, which finds the largest height in the current board on some interval. We will work on implementing these operations.
Coordinate Compression
In the below approaches, since there are only up to 2 * len(positions)
critical points, namely the left and right edges of each square, we can use a technique called coordinate compression to map these critical points to adjacent integers, as shown in the code snippets below.
For brevity, these snippets are omitted from the remaining solutions.
Approach 1: Offline Propagation
Intuition
Instead of asking the question "what squares affect this query?", lets ask the question "what queries are affected by this square?"
Algorithm
Let qans[i]
be the maximum height of the interval specified by positions[i]
. At the end, we'll return a running max of qans
.
For each square positions[i]
, the maximum height will get higher by the size of the square we drop. Then, for any future squares that intersect the interval [left, right)
(where left = positions[i][0], right = positions[i][0] + positions[i][1]
), we'll update the maximum height of that interval.
Complexity Analysis

Time Complexity: , where is the length of
positions
. We use two forloops, each of complexity . 
Space Complexity: , the space used by
qans
andans
.
Approach 2: Brute Force with Coordinate Compression
Intuition and Algorithm
Let N = len(positions)
. After mapping the board to a board of length at most , we can brute force the answer by simulating each square's drop directly.
Our answer is either the current answer or the height of the square that was just dropped, and we'll update it appropriately.
Complexity Analysis

Time Complexity: , where is the length of
positions
. We use two forloops, each of complexity (because of coordinate compression.) 
Space Complexity: , the space used by
heights
.
Approach 3: Block (Square Root) Decomposition
Intuition
Whenever we perform operations (like update
and query
) on some interval in a domain, we could segment that domain with size into blocks of size .
Then, instead of a typical brute force where we update our array heights
representing the board, we will also hold another array blocks
, where blocks[i]
represents the elements heights[B*i], heights[B*i + 1], ..., heights[B*i + B1]
. This allows us to write to the array in operations.
Algorithm
Let's get into the details. We actually need another array, blocks_read
. When we update some element i
in block b = i / B
, we'll also update blocks_read[b]
. If later we want to read the entire block, we can read from here (and stuff written to the whole block in blocks[b]
.)
When we write to a block, we'll write in blocks[b]
. Later, when we want to read from an element i
in block b = i / B
, we'll read from heights[i]
and blocks[b]
.
Our process for managing query
and update
will be similar. While left
isn't a multiple of B
, we'll proceed with a bruteforcelike approach, and similarly for right
. At the end, [left, right+1)
will represent a series of contiguous blocks: the interval will have length which is a multiple of B
, and left
will also be a multiple of B
.
Complexity Analysis

Time Complexity: , where is the length of
positions
. Eachquery
andupdate
has complexity . 
Space Complexity: , the space used by
heights
.
Approach 4: Segment Tree with Lazy Propagation
Intuition
If we were familiar with the idea of a segment tree (which supports queries and updates on intervals), we can immediately crack the problem.
Algorithm
Segment trees work by breaking intervals into a disjoint sum of component intervals, whose number is at most log(width)
. The motivation is that when we change an element, we only need to change log(width)
many intervals that aggregate on an interval containing that element.
When we want to update an interval all at once, we need to use lazy propagation to ensure good runtime complexity. This topic is covered in more depth here.
With such an implementation in hand, the problem falls out immediately.
Complexity Analysis

Time Complexity: , where is the length of
positions
. This is the runtime complexity of using a segment tree. 
Space Complexity: , the space used by our tree.
Analysis written by: @awice.