DSA problem
Falling Squares
There are several squares being dropped onto the X-axis of a 2D plane. You are given a 2D integer array positions where positions[i] = [left_i, sideLength_i] represents the i-th square dropped, with left edge at x = left_i and side length sideLength_i. Each square stacks on top of any square it overlaps in the x-range [left_i, left_i + sideLength_i); otherwise it rests on the ground. After each drop, record the maximum height of any stack so far. Return that running list of heights.
The natural data structure is a segment tree with range-max and range-assign lazy propagation. Each tree node stores the maximum height in its x-range. Dropping a square at x-range [L, R) with side s works in two steps: query the current max height h in [L, R), then range-assign h + s to all positions in [L, R). The running answer is max(prev_max, h + s).
Because x-coordinates can be as large as 10^8 but only 2n distinct values actually appear (left edges and right edges), coordinate-compress them first. Sort the unique endpoints, map each to an index in [0, m) where m <= 2n, and build the segment tree over that compressed universe. The compressed range [L, R) becomes [rankOf(L), rankOf(R) - 1] in inclusive segment-tree coordinates.
Lazy propagation handles the range-assign efficiently: each internal node carries an optional "pending assignment". When we recurse, we push the pending value to children and clear it. With careful boundary management each drop costs O(log n), yielding O(n log n) overall — far better than the O(n^2) brute force.
Examples
positions = [[1,2],[2,3],[6,1]][2,5,5]positions = [[100,100],[200,100]][100,100]positions = [[2,1],[1,2]][1,3]Constraints
- 1 <= positions.length <= 1000
- 1 <= left_i <= 10^8
- 1 <= sideLength_i <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.