Falling Squares — Coordinate Compress + Segment Tree

Problem

Squares fall and stack. After each square, return the current maximum stack height.

Approach — Coordinate Compression + Seg Tree (Range Max)

Coordinate compress all x-values. Segment tree supports range max query and range assignment update.

Time: O(n log n) | Space: O(n)

Solutions

Python — Simplified O(n²)

class Solution:
    def fallingSquares(self, positions: list[list[int]]) -> list[int]:
        intervals=[]  # (left, right, height)
        result=[]
        for left,size in positions:
            right=left+size
            h=size
            for l2,r2,h2 in intervals:
                if l2<right and r2>left:  # overlap
                    h=max(h,h2+size)
            intervals.append((left,right,h))
            result.append(max(x[2] for x in intervals))
        return result

Complexity

Naive: O(n²) | Segment Tree: O(n log n)