699. Falling Squares

699

HardAdvanced Range Data StructuresSegment tree with lazy propagation over compressed coordinatesRange assign, range max

Falling Squares

Squares of given side lengths drop one at a time onto a number line at given left positions. Each square falls until it rests on the ground or on the top of a previously landed square that it overlaps horizontally. After each drop, report the height of the tallest stack so far. Return the list of these running maxima.

Open official problem prompt ↗

In plain English

After each falling square lands, know the height of the current tallest point across the whole line.

Picture it like this

Stacking sticky notes on a wall: a new note sticks on top of whatever is highest in the horizontal strip it covers. You constantly report the highest note anywhere on the wall.

Example

Input: positions = [[1,2],[2,3],[6,1]]
Output: [2,5,5]
Why: First square rests at height 2. The second overlaps it and stacks on top: 2+3=5. The third lands far away at height 1, so the tallest overall stays 5.

Constraints

1 <= positions.length <= 10001 <= left, sideLength <= 10^8positions[i] = [left, sideLength]

Pattern lesson

See the pattern, then code

Range assign, range max

↗

Advanced Range Data Structures

Online prefix or range queries with updates, inversions, or coordinate compression.. A square covering [l, l+side) lands at (max height currently under that interval) + side, and then that whole interval is set to the new height. Compress the sparse coordinates and maintain interval max with a lazy-assign segment tree.

New words, made simpleKnow these before the algorithm

Coordinate compression: Mapping the few relevant x endpoints to small indices so a segment tree over O(n) leaves suffices instead of 10^8.
Lazy propagation: Deferring a pending range assignment on a node, pushing it to children only when they are visited.
Range assign: Overwriting every value in an interval with a single new value (the square's top height).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Interval list O(n^2)

Fine at n = 1000 and simple, but does not scale and misses the segment-tree lesson.

Store landed intervals with heights; for each square scan all prior intervals it overlaps to find the base.

Time O(n^2)Space O(n)

Best choiceLazy segment tree

Scales cleanly and is the intended advanced-range-structure solution.

Compress coordinates, then range-max query and range-assign per square.

Time O(n log n)Space O(n)

The rule we keep true

Invariant

At all times the segment tree leaf for a compressed cell holds the current stacked height at that x-range, and every internal node holds the max height over its subtree, so a range query returns the true landing base.

Why this is correct

Reasoning

A square resting on the tallest thing beneath it must land at (max over its span) + its side; assigning that height across the span keeps every covered cell consistent. Lazy propagation makes range assignment and range max both O(log n) by deferring writes, and compression preserves overlap relationships because only endpoints matter. Using l+side-1 as the closed right cell prevents squares that merely touch at an edge from being treated as overlapping.

The algorithm in three movesSay these aloud before coding

1Collect and compress all interval endpoints (use l and l+side-1 to treat intervals as closed cells)

drop1: q[1,2]=0, land 2, assign 2

2Build a segment tree supporting range-assign updates and range-max queries with lazy propagation

drop2: q[2,4]=2, land 5, assign 5

3For each square query the max height over its compressed interval and add its side

drop3: q[6,6]=0, land 1

4Assign that new height across the interval

best = 2,5,5

5Track and append the global running maximum

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,2]0

[2,3]1

[6,1]2

1 · Readpositions=[[1,2],[2,3],[6,1]]

2 · AskWhich x cells?

3 · Update statexs = [1,2,4,6] (l and l+s-1)

4 · Result4 leaves

Key takeaway

Each square queries the max height beneath its span, then assigns its new top across that span.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-9Compress coordinates
Collect left edges and closed right edges (l+side-1), dedupe, and map to dense indices for the tree.
2
Lines 11-16push lazy down
Before recursing into children, apply any pending assignment to them.
3
Lines 18-30Range assign
Overwrite fully covered nodes with the new height and set their lazy tag; recombine child maxima on partial cover.
4
Lines 32-40Range max query
Return the maximum stacked height over the queried compressed span.
5
Lines 42-51Process drops
Each square lands at query + side, assigns that height, and updates the running best.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single square returns [side]
Two squares touching only at an edge (e.g. [1,2] then [3,1]) must not stack, hence the l+side-1 closed-cell trick
A square fully inside another's span stacks on it
Widely separated squares keep the running max from earlier drops

Common beginner mistakes

Using l+side (open endpoint) as the right cell, which makes edge-touching squares wrongly overlap
Forgetting lazy push before descending, returning stale maxima
Reporting the current square's height instead of the running maximum so far
Sizing the tree too small; 4*n leaves are needed for the recursive layout

Check your understanding

Why compress using l+side-1 for the right edge instead of l+side?

PyPython 3 · solution.py

Optimal

1from typing import List23class Solution:4    def fallingSquares(self, positions: List[List[int]]) -> List[int]:5        xs = sorted(set([p[0] for p in positions] + [p[0] + p[1] - 1 for p in positions]))6        idx = {x: i for i, x in enumerate(xs)}7        n = len(xs)8        tree = [0] * (4 * n)9        lazy = [0] * (4 * n)1011        def push(node: int) -> None:12            if lazy[node]:13                for c in (2 * node, 2 * node + 1):14                    tree[c] = lazy[node]15                    lazy[c] = lazy[node]16                lazy[node] = 01718        def update(node: int, lo: int, hi: int, l: int, r: int, val: int) -> None:19            if r < lo or hi < l:20                return21            if l <= lo and hi <= r:22                tree[node] = val23                lazy[node] = val24                return25            push(node)26            mid = (lo + hi) // 227            update(2 * node, lo, mid, l, r, val)28            update(2 * node + 1, mid + 1, hi, l, r, val)29            tree[node] = max(tree[2 * node], tree[2 * node + 1])3031        def query(node: int, lo: int, hi: int, l: int, r: int) -> int:32            if r < lo or hi < l:33                return 034            if l <= lo and hi <= r:35                return tree[node]36            push(node)37            mid = (lo + hi) // 238            return max(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r))3940        res = []41        best = 042        for l, s in positions:43            left, right = idx[l], idx[l + s - 1]44            cur = query(1, 0, n - 1, left, right) + s45            update(1, 0, n - 1, left, right, cur)46            best = max(best, cur)47            res.append(best)48        return res

Time complexityO(n log n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonAirbnb

Falling Squares

Falling Squares

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Advanced Range Data Structures