Falling Squares

Falling Squares hard

Description

Squares drop one by one onto a number line. positions[i] = [left, sideLength] describes a square occupying [left, left + sideLength). A square lands on top of whatever is currently tallest under its footprint. After each drop, report the maximum height anywhere on the line so far.

Examples

> positions = [[1,2],[2,3],[6,1]]
  Output: [2, 5, 5]
  # square1 height 2; square2 lands on square1's overlap -> top at 2+3=5; square3 isolated -> 1, max stays 5
 
> positions = [[100,100],[200,100]]
  Output: [100, 100]     # they don't overlap

Constraints

1 <= positions.length <= 1000, coordinates up to 10^8.

Intuition

Two range operations over the footprint interval [left, right):

Query the current max height under the footprint (range-max).
The new top is that max + sideLength; assign that height to the whole footprint (range-assign).

That’s a lazy-propagation segment tree supporting range-assign + range-max. Coordinates reach 10^8 but there are ≤ 2000 distinct endpoints, so coordinate-compress first. (With only 1000 squares, an O(n²) “compare against all previous intervals” solution also passes — but the segment tree is the scalable, intended structure.)

Code (lazy range-assign / range-max segment tree)

⚠️

The lazy tag here is an ASSIGN, not an ADD — so it overwrites. When a square lands, its footprint becomes a flat height, replacing whatever was there. pushDown therefore sets children to the tag value rather than adding. Mixing this up with the additive lazy logic from the range-add tree is the classic bug. Also: compress endpoints as left and left + side − 1 (inclusive right edge) so adjacent, non-overlapping squares don’t falsely merge.

Analysis

Time: O(n log n) with the segment tree (n = squares, after compression). The brute-force interval-compare is O(n²) — acceptable here but not scalable.
Space: O(n) for the compressed tree.

Same skin

My Calendar III — also range-update + range-max; this is the “with heights” cousin.
Lazy Propagation — the technique, with the assign-vs-add distinction spelled out.
The Skyline Problem (Day 26) — another “max height over intervals” problem, solved by a sweep + heap.

My Calendar III Overview