Falling Squares
Hard Segment tree with range assign / range max
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Squares fall one by one onto a line; each lands on top of the highest square under its span. After each drop, report the tallest stack height so far.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: drop squares one by one; report the tallest stack after each drop.
Why this works: a segment tree over compressed x-coordinates answers "max height in a range" and "set a range to h".
Example: [[1,2], [2,3], [6,1]]
square 1 lands at 0 → height 2square 2 overlaps → 2 + 3 = 5square 3 alone → 1 → answers [2, 5, 5]
✦Hints open one at a time
↗Approach
Collect all lefts and rights, sort and compress. For each square: h = query max over its compressed range + side; assign h to that range; the answer is the running maximum.
</>Solution (Java)
import java.util.*;
class Solution {
private int[] mx, lazy;
public List<Integer> fallingSquares(int[][] positions) {
TreeSet<Integer> coords = new TreeSet<>();
for (int[] p : positions) {
coords.add(p[0]);
coords.add(p[0] + p[1] - 1); // last occupied unit
}
Map<Integer, Integer> id = new HashMap<>();
for (int c : coords) id.put(c, id.size());
int n = id.size();
mx = new int[4 * n];
lazy = new int[4 * n];
List<Integer> res = new ArrayList<>();
int best = 0;
for (int[] p : positions) {
int l = id.get(p[0]), r = id.get(p[0] + p[1] - 1);
int h = query(1, 0, n - 1, l, r) + p[1];
assign(1, 0, n - 1, l, r, h);
best = Math.max(best, h);
res.add(best);
}
return res;
}
private void push(int node) {
if (lazy[node] != 0) {
for (int c : new int[]{2 * node, 2 * node + 1}) {
mx[c] = lazy[node];
lazy[c] = lazy[node];
}
lazy[node] = 0;
}
}
private void assign(int node, int lo, int hi, int l, int r, int h) {
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) { // fully covered: set lazily
mx[node] = h;
lazy[node] = h;
return;
}
push(node);
int mid = (lo + hi) / 2;
assign(2 * node, lo, mid, l, r, h);
assign(2 * node + 1, mid + 1, hi, l, r, h);
mx[node] = Math.max(mx[2 * node], mx[2 * node + 1]);
}
private int query(int node, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return mx[node];
push(node);
int mid = (lo + hi) / 2;
return Math.max(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
}
}!Common mistake
Treating the right edge as occupied — squares touching at an edge don't stack, so use the half-open range [left, left + side).
- Time: O(n log n).
- Space: O(n).