Falling Squares
Hard · Intervals · Array · Segment Tree · Ordered Set
Problem
Squares are dropped one at a time onto the x-axis. positions[i] = [left_i, side_i] drops a square whose left edge is at x = left_i and whose side length is side_i, so it spans [left_i, left_i + side_i].
Each square falls straight down until its bottom lands on the x-axis or on the top of an earlier square it overlaps. Touching another square only at an edge (one square's right side at the other's left side) does not stop it. Once landed, a square stays put.
After each drop, record the height of the tallest stack so far. Return the list of those heights.
Examples
Input: positions = [[1,3],[2,2],[5,4]] Output: [3,5,5]
The second square lands on the first and reaches 5. The third starts at x = 5, where the second one ends: it only touches, so it lands on the ground at height 4. The tallest stays 5.
Input: positions = [[0,2],[2,2],[1,2]] Output: [2,2,4]
The first two sit side by side at height 2. The third spans x = 1 to 3, overlapping both, and lands on top at 4.
Input: positions = [[100,100]] Output: [100]
It lands on the ground: height 100.
Constraints
- 1 <= len(positions) <= 1000
- 1 <= left_i <= 10^8
- 1 <= side_i <= 10^6
Approaches
- Baseline: compare with every landed square — time O(n²), space O(n)
Follow-up
The segment tree needs no push-down here because a new square is never lower than what it covers: a "cover" tag on a node just records the height laid over its whole range. The use cases report where each square lands rather than the running maximum, and drop bricks whose height differs from their width.
Related problems
Start free on Cariara · Coding problems · System design studio
