Falling Squares — Segment Tree with Lazy Propagation & Coordinate Compression

Problem Statement#

LeetCode 699 — Falling Squares | Difficulty: Hard

You are given a 2D array positions, where positions[i] = [left_i, side_i] represents a square with side length side_i whose left edge starts at x-coordinate left_i. Each square drops one at a time onto the number line.

When a square lands, it stacks on top of any squares already covering its [left, left + side) interval. The new top of that interval becomes max(existing height in interval) + side.

Return an array answer where answer[i] is the height of the tallest stack on the entire number line after the i-th square has landed.

Constraints:

• 1 is less than or equal to positions.length, which is less than or equal to 1000
• 1 is less than or equal to left_i, which is less than or equal to 10^8
• 1 is less than or equal to side_i, which is less than or equal to 10^6

Example:

Input:  positions = [[1, 2], [2, 3], [6, 1]]
Output: [2, 5, 5]
Explanation:
  Drop [1,3) with side 2 -> stack height 2 in [1,3); max overall = 2
  Drop [2,5) with side 3 -> rests on stack of 2; new height 5 in [2,5); max overall = 5
  Drop [6,7) with side 1 -> standalone height 1 in [6,7); max overall = 5

Why This Problem Matters#

Falling Squares is the gold-standard interview test for segment trees with lazy propagation. Google, Amazon, and Bloomberg use it because it requires three independent skills working together: coordinate compression to fit a 10^8 number line into a few thousand indices, range-max queries to find the highest existing stack under the falling square, and range-assign updates with lazy propagation to mark the new height across an interval.

This pattern shows up in computational geometry (skyline construction), game physics (collision-stacking), network bandwidth management (peak utilization tracking), and any "interval paint" workload where a single update must rewrite a contiguous range. Mastering this problem unlocks every "range update plus range max" problem on the planet.

The Core Insight#

The data structure must support two operations efficiently on a continuous number line:

1. Range max query: what is the tallest stack inside [L, R)?
2. Range assign update: set every position in [L, R) to a new height.

A segment tree with lazy propagation does both in O(log n). Lazy propagation means we do not push the update all the way down to leaves — instead we store a pending value at the highest fully-covered node and push it down only when a child is needed for a finer query.

Coordinate compression is mandatory because the raw x-coordinates can be up to 10^8 but there are at most 1000 squares. Collect all distinct boundary points (left and left + side), sort them, and replace each x-coordinate with its index. The compressed line has at most 2 * n = 2000 cells, and the segment tree has at most 4 * 2000 = 8000 nodes.

Lazy values semantics:

• tree[node] stores the maximum height in the node's range.
• lazy[node] stores a pending range-assign value (or 0 if none). When set, every leaf in the node's range will eventually equal lazy[node].

When we recurse into a child, we push lazy[parent] down: tree[child] = lazy[parent] and lazy[child] = lazy[parent]. This keeps the tree consistent while deferring work.

Visual Dry Run#

Trace positions = [[1, 2], [2, 3], [6, 1]].

Square 1: [1, 3) with side 2
  Compressed boundaries: {1, 3, 2, 5, 6, 7} -> sorted: [1, 2, 3, 5, 6, 7]
  Range query max over [1, 3) = 0 (empty)
  New height = 0 + 2 = 2
  Range assign [1, 3) := 2
  answer[0] = global max = 2
 
Square 2: [2, 5) with side 3
  Range query max over [2, 5) = 2 (from previous square)
  New height = 2 + 3 = 5
  Range assign [2, 5) := 5
  answer[1] = global max = 5
 
Square 3: [6, 7) with side 1
  Range query max over [6, 7) = 0 (empty)
  New height = 0 + 1 = 1
  Range assign [6, 7) := 1
  answer[2] = global max = 5  (the 5-stack still exists in [2, 5))

Segment tree structure after square 2:
                       max=5, range [1..7)
                      /                   \
              max=5, [1..3.5)         max=0, [3.5..7)
              /        \                /        \
        max=2,[1..2)  max=5,[2..3.5) max=0,...  max=0,...
                          (lazy=5)
 
When we query max over [2, 5), we descend, push lazy=5 to children
of the node covering [2, 3.5), and continue right side.

The lazy tag prevents us from rewriting every leaf during the assign step — that is the entire point of lazy propagation.

Solution (Optimal)#

Python — Segment Tree with Lazy Propagation#

from typing import List
from bisect import bisect_left
 
class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        # 1) coordinate compression of all interval boundaries
        boundaries = sorted({x for L, side in positions for x in (L, L + side)})
        idx = {x: i for i, x in enumerate(boundaries)}     # x -> compressed index
        n = len(boundaries)
        tree = [0] * (4 * n)                                # range max
        lazy = [0] * (4 * n)                                # pending range-assign
 
        def push_down(node: int) -> None:
            # propagate lazy assign value to both children, then clear
            if lazy[node]:
                tree[2 * node] = lazy[node]; lazy[2 * node] = lazy[node]
                tree[2 * node + 1] = lazy[node]; lazy[2 * node + 1] = lazy[node]
                lazy[node] = 0
 
        def update(node: int, l: int, r: int, ql: int, qr: int, val: int) -> None:
            # range-assign tree[ql..qr] = val
            if qr < l or r < ql:                            # disjoint
                return
            if ql <= l and r <= qr:                         # fully inside query range
                tree[node] = val                            # set max to val
                lazy[node] = val                            # mark pending
                return
            push_down(node)                                 # propagate before recursing
            mid = (l + r) // 2
            update(2 * node, l, mid, ql, qr, val)
            update(2 * node + 1, mid + 1, r, ql, qr, val)
            tree[node] = max(tree[2 * node], tree[2 * node + 1])
 
        def query(node: int, l: int, r: int, ql: int, qr: int) -> int:
            # range-max over [ql..qr]
            if qr < l or r < ql:
                return 0
            if ql <= l and r <= qr:
                return tree[node]
            push_down(node)
            mid = (l + r) // 2
            return max(query(2 * node, l, mid, ql, qr),
                       query(2 * node + 1, mid + 1, r, ql, qr))
 
        result = []
        global_max = 0
        for L, side in positions:
            R = L + side
            l_idx = idx[L]                                  # compressed left
            r_idx = idx[R] - 1                              # half-open: subtract 1 for inclusive
            existing = query(1, 0, n - 1, l_idx, r_idx)     # tallest stack under this square
            new_h = existing + side
            update(1, 0, n - 1, l_idx, r_idx, new_h)        # paint range with new height
            global_max = max(global_max, new_h)
            result.append(global_max)
        return result

JavaScript — O(n^2) Interval Sweep (Acceptable for n at 1000)#

var fallingSquares = function(positions) {
    const intervals = [];                                   // (left, right, height) tuples
    const result = [];
    let globalMax = 0;
 
    for (const [L, side] of positions) {
        const R = L + side;
        let baseHeight = 0;
 
        // find tallest existing stack that overlaps [L, R)
        for (const [l, r, h] of intervals) {
            if (l < R && L < r) {                           // half-open overlap test
                baseHeight = Math.max(baseHeight, h);
            }
        }
 
        const newHeight = baseHeight + side;
        intervals.push([L, R, newHeight]);                  // record this square's stack
        globalMax = Math.max(globalMax, newHeight);
        result.push(globalMax);
    }
    return result;
};

Complexity: Segment tree solution: O(n log n) time, O(n) space — log factor from compressed-line tree depth. Interval sweep: O(n^2) time, O(n) space — acceptable when n is at most 1000, which is the LeetCode constraint.

Common Mistakes#

1. Forgetting to push down before recursing. If you skip push_down in the update or query path, stale values propagate into children and the answer is wrong. Push down first, then descend.
2. Mixing range-assign with range-add semantics. Falling Squares is a replace, not an add — when a square lands, the new height is the absolute new value, not an increment. Lazy values must overwrite, not accumulate.
3. Wrong half-open boundary in compression. The square covers [L, L+side). After compression, the right edge is idx[R] - 1 for an inclusive segment-tree query. Off by one here is the most common bug.
4. Allocating only 2 * n tree nodes. Always allocate 4 * n to handle non-power-of-two sizes. The classic trap.
5. Re-querying global max from the entire tree. Maintaining a running global_max variable is O(1) per square. Recomputing each call adds an unnecessary log factor.
6. Not coordinate-compressing. Trying to build a segment tree over 10^8 indices runs out of memory immediately. Compression is mandatory.

Interview Tips#

• Identify the two ops upfront. Say "I need range max query plus range assign update — that points me at a segment tree with lazy propagation."
• Justify compression. "X coordinates go up to 10^8 but there are at most 1000 squares — so I will compress to at most 2000 distinct boundary points before building the tree."
• Pseudocode the push_down before writing it. Lazy propagation is the trickiest part; sketching the invariant ("if lazy is set, children must be overwritten before we descend") prevents the most common bug.
• Mention the O(n^2) fallback. With n at 1000, the trivial interval sweep passes within the time limit. State this as your fallback if lazy propagation goes wrong, then implement the segment tree for full credit.
• Walk through one push_down on the whiteboard. Showing how a single assign at a parent flows to children when a deeper query arrives convinces the interviewer you actually understand lazy propagation.

Follow-up Questions#

1. Range add instead of range assign. Lazy values accumulate via addition. The push_down adds rather than overwrites.
2. Both range add AND range assign. Maintain two lazy fields with priority — assign clears any pending add.
3. Range min instead of range max. Same template, replace max with min and identity from 0 to infinity.
4. Skyline problem (LeetCode 218). Same compression, but emit boundary events instead of stacking.
5. 2D version: stacks of rectangles in a plane. 2D segment tree with lazy propagation, or sweep line plus 1D segment tree.
6. Online queries with persistence. Use a persistent segment tree (functional) so each square produces a new immutable version.

Key Takeaways#

• Segment tree with lazy propagation is the canonical structure for problems combining range queries with range updates — it amortizes the work across nodes by deferring updates.
• Coordinate compression turns a sparse 10^8 number line into a dense index space the tree can handle.
• The lazy field semantics matter: range-assign overwrites children completely, while range-add accumulates. Always push down before descending into children.
• Allocate 4 * n nodes, not 2 * n. The latter only works for powers of two.
• Maintain a running global_max as you process squares — recomputing it from the tree wastes a log factor per call.
• Falling Squares is the entry-level problem for the entire "range update plus range query" family. Master it, and skyline, range-add range-min, and dynamic-2D variants follow naturally.