Falling Squares

hard array segment tree ordered set

Problem

positions[i] = [left, sideLength] means a square with side sideLength drops on the number line so its left edge is at left. Squares stack on top of any blocks under their footprint. After each drop, record the tallest height on the line so far.

Inputpositions = [[1,2], [2,3], [6,1]]

Output[2, 5, 5]

First drop reaches h=2. Second sits on first → top = 2 + 3 = 5. Third lands on the floor at h=1 but max stays 5.

positions ("1-2,2-3,6-1")

def falling_squares(positions):
    intervals = []  # list of (left, right, height)
    best = 0
    ans = []
    for left, side in positions:
        right = left + side
        base = 0
        for (l, r, h) in intervals:
            if l < right and left < r:
                base = max(base, h)
        top = base + side
        intervals.append((left, right, top))
        best = max(best, top)
        ans.append(best)
    return ans

function fallingSquares(positions) {
  const intervals = [];
  let best = 0;
  const ans = [];
  for (const [left, side] of positions) {
    const right = left + side;
    let base = 0;
    for (const [l, r, h] of intervals) {
      if (l < right && left < r) base = Math.max(base, h);
    }
    const top = base + side;
    intervals.push([left, right, top]);
    if (top > best) best = top;
    ans.push(best);
  }
  return ans;
}

class Solution {
    public List<Integer> fallingSquares(int[][] positions) {
        List<int[]> intervals = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        int best = 0;
        for (int[] p : positions) {
            int left = p[0], side = p[1], right = left + side, base = 0;
            for (int[] iv : intervals) if (iv[0] < right && left < iv[1]) base = Math.max(base, iv[2]);
            int top = base + side;
            intervals.add(new int[]{left, right, top});
            best = Math.max(best, top);
            ans.add(best);
        }
        return ans;
    }
}

vector<int> fallingSquares(vector<vector<int>>& positions) {
    vector<tuple<int,int,int>> intervals;
    vector<int> ans;
    int best = 0;
    for (auto& p : positions) {
        int left = p[0], side = p[1], right = left + side, base = 0;
        for (auto& [l, r, h] : intervals) if (l < right && left < r) base = max(base, h);
        int top = base + side;
        intervals.push_back({left, right, top});
        best = max(best, top);
        ans.push_back(best);
    }
    return ans;
}

Explanation

Each square falls and lands on top of whatever is already underneath its horizontal footprint. So before dropping a square we just need the tallest height among all earlier squares that overlap it.

We store every placed square as (left, right, height). For a new square spanning [left, right), we scan all existing intervals and check overlap with the test l < right && left < r, taking the maximum height as the base it rests on.

The new top is base + side. We record this square, then update best, the tallest height anywhere so far, and append it to the answer after each drop.

Example: [[1,2],[2,3],[6,1]]. The first reaches height 2. The second overlaps it, so it sits at 2 + 3 = 5. The third lands on empty floor at height 1, but best stays 5, giving [2, 5, 5].

Comparing each square against the earlier ones is simple and exact; a segment tree can speed it up, but the overlap-and-stack idea is the same.

Time: O(n^2) (segment tree: O(n log n)) Space: O(n)