Falling Squares: Coordinate Compression and Interval Tracking

LeetCode 699, Falling Squares, gives you a sequence of squares that drop onto a number line. Each square is described by a pair [left, sideLength], meaning it occupies the range from left to left + sideLength on the x-axis. When a square falls, it either lands on the ground or stacks on top of any existing squares it overlaps. After each drop, you report the current maximum height across all squares.

The output is an array where the i-th element is the tallest stack after the i-th square has been dropped.

Why this problem matters

Falling Squares combines interval overlap detection with running max tracking in a way that shows up across many different problem families. The core question is: given a new interval, what is the tallest existing interval that it overlaps? This is the same kind of reasoning you use in skyline problems, calendar booking, and segment tree applications.

What makes this problem tricky is that you are not just merging intervals. Each square keeps its identity. You need to know the height at every occupied region, and when a new square lands, it stacks on top of whatever is tallest beneath it. The height of the new square becomes (tallest overlap) + sideLength, not a merge of ranges.

This is also a great problem for practicing coordinate compression. The positions can be very large (up to 10^8), but the number of squares is at most 1000. That means you only care about the boundaries defined by the squares themselves, which is a classic signal that coordinate compression will help.

The brute force approach

The simplest approach is to track each dropped square as an interval with a height. For every new square, scan all previously dropped squares, check for overlap, and find the maximum height among all overlapping squares. The new square's height is that maximum plus its own side length.

Two intervals [a1, a2) and [b1, b2) overlap when a1 < b2 and b1 < a2. Since each square occupies [left, left + side), you check this condition for every pair.

def fallingSquares(positions):
    intervals = []
    result = []
    max_height = 0

    for left, side in positions:
        right = left + side
        base = 0

        for l2, r2, h2 in intervals:
            if left < r2 and l2 < right:
                base = max(base, h2)

        height = base + side
        intervals.append((left, right, height))
        max_height = max(max_height, height)
        result.append(max_height)

    return result

For each new square you scan all previous squares, so the time complexity is O(n^2) where n is the number of squares. Since n is at most 1000, this runs fast enough to pass. But understanding why it works sets you up for the optimized approach.

Step-by-step walkthrough

Let's trace through positions = [[1,3], [2,2], [6,3], [3,4]].

The key insight in each step is the overlap check. When dropping square [3, 4] (occupying [3, 7)), it overlaps three existing intervals: [1, 4) at height 3, [2, 4) at height 5, and [6, 9) at height 3. The tallest overlap is 5, so the new height is 5 + 4 = 9.

Notice that the running max never decreases. If a new square lands somewhere low, the max stays the same as before. You only update the max when a new square creates a taller stack than anything seen so far.

Optimized approach with coordinate compression

When the coordinate space is huge but the number of squares is small, coordinate compression lets you map the large coordinates down to a compact index space. You collect all the left and right boundaries of every square, sort them, and assign each unique coordinate an index. Then you can use an array (or a segment tree) indexed by those compressed coordinates.

With coordinate compression and a segment tree, you can query "what is the max height in range [left, right)?" and update "set the height in range [left, right) to value h" both in O(log m) time, where m is the number of unique coordinates (at most 2n).

def fallingSquares(positions):
    coords = set()
    for left, side in positions:
        coords.add(left)
        coords.add(left + side)
    sorted_coords = sorted(coords)
    index_map = {v: i for i, v in enumerate(sorted_coords)}
    m = len(sorted_coords)

    heights = [0] * m
    result = []
    max_height = 0

    for left, side in positions:
        right = left + side
        li = index_map[left]
        ri = index_map[right]

        base = max(heights[li:ri])

        new_h = base + side
        for i in range(li, ri):
            heights[i] = max(heights[i], new_h)

        max_height = max(max_height, new_h)
        result.append(max_height)

    return result

This version compresses the coordinates but still does a linear scan over the compressed range for each square. The true O(n log n) solution replaces those linear scans with a segment tree supporting range-max queries and range updates. For interview purposes, the brute force O(n^2) solution is usually sufficient given the constraint of n <= 1000, but knowing about the segment tree optimization shows depth.

Complexity analysis

The brute force is acceptable for n <= 1000. For larger inputs, the segment tree approach brings it down to O(n log n).

Edge cases to watch for

• Single square. Only one drop. It lands on the ground, and the result is just its side length.
• No overlaps at all. Every square lands on a different part of the number line. Each height is just the side length, and the running max is the largest side length seen so far.
• Complete overlap. A new square lands exactly on top of an existing one. The base is the full height of the existing square.
• Partial overlap with multiple squares. The new square spans across several existing squares at different heights. You need the maximum height among all overlapping squares, not the sum.
• Adjacent but not overlapping. A square at [1, 3] occupies [1, 4). A square at [4, 2] occupies [4, 6). These do not overlap because the first square's right boundary equals the second square's left boundary. The overlap check uses strict less-than: left < r2 and l2 < right.
• Very large coordinates. Positions can be up to 10^8, but with only 1000 squares, the brute force approach does not care about coordinate size since it only tracks intervals, not individual positions.

The building blocks

Interval overlap detection

The core operation is checking whether two intervals [a, b) and [c, d) overlap. They overlap when a < d and c < b. This is the same check used in meeting rooms, merge intervals, and calendar booking problems. The half-open interval convention [left, left + side) makes the boundary condition clean: squares that touch at a single point do not overlap.

Coordinate compression

When the input values are spread across a huge range but there are relatively few distinct values, you can map them to consecutive integers. Collect all relevant coordinates, sort and deduplicate them, then replace each value with its index. This shrinks the problem space from potentially 10^8 positions down to at most 2n positions. Coordinate compression is a prerequisite for using segment trees or BITs on problems with large coordinate ranges.

Running maximum

After each drop, the answer is the maximum height seen so far. You maintain a single variable that tracks this across all drops. Because heights can only grow (a new square always adds positive side length on top of whatever it lands on), the running max is monotonically non-decreasing.

From understanding to recall

You have seen how Falling Squares works: for each new square, scan all existing intervals for overlap, take the max height among overlapping intervals, add the side length, and update the running max. The overlap check uses strict less-than with half-open intervals. The coordinate compression technique shrinks huge coordinate spaces into manageable arrays.

These are details that feel natural when you are reading through the solution but are easy to get wrong under pressure. Does the overlap check use < or <=? Is the height of the new square base + side or max(base, side)? Do adjacent squares overlap? Practicing until these details are automatic is the difference between solving this in an interview and getting stuck on off-by-one errors.

Related posts

• Insert Interval - The foundational interval insertion and merging pattern
• Merge Intervals - Sort and sweep to merge overlapping intervals
• The Skyline Problem - Another coordinate-based height tracking problem using sweep line