LeetCode 699: Falling Squares

Problem Restatement

We are given a list of squares falling onto the X-axis.

Each square is described by:

[left, side_length]

The square spans the interval:

[left, left + side_length)

The square falls vertically until:

After each square falls, we must report the maximum height among all squares so far.

The official statement models squares falling onto a 1D number line and asks for the highest stack after each placement. (leetcode.com)

Input and Output

Example function shape:

def fallingSquares(positions: list[list[int]]) -> list[int]:
    ...

Examples

Example 1:

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

First square

Square:

[1, 3)

Side length:

2

It lands on the ground.

Height becomes:

2

Maximum height:

2

Second square

Square:

[2, 5)

It overlaps the first square on interval:

[2, 3)

So it lands on top of height 2.

New height:

2 + 3 = 5

Maximum height:

5

Third square

Square:

[6, 7)

No overlap with previous squares.

It lands on the ground with height:

1

The global maximum remains:

5

Answer:

[2, 5, 5]

First Thought: Simulate the Plane

A direct idea is to model the entire coordinate line and fill heights.

But coordinates can be very large:

0 <= left <= 10^8

So we cannot build a huge array.

Instead, we only care about intervals created by squares.

Key Insight

When a new square falls:

[left, right)

its base height equals the maximum height among all previous overlapping intervals.

Suppose the current maximum overlapping height is:

base

Then the new square’s top height is:

base + side_length

So for each new square, we need:

1. Find the maximum height among overlapping previous squares.
2. Add the side length.
3. Store the new interval and its height.

Overlap Rule

Two intervals overlap if:

max(left1, left2) < min(right1, right2)

For example:

The intervals are half-open.

Touching edges do not overlap.

Simple Interval Simulation

We store placed squares as:

(left, right, height)

For each new square:

1. Compute:

   right = left + size
2. Initialize:

   base_height = 0
3. Check every previous interval:
   • if overlapping:

     base_height = max(base_height, previous_height)
4. New height:

   new_height = base_height + size
5. Save the interval.
6. Track the global maximum.

Walkthrough

Consider:

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

Square 1

Interval:

[1,3)

No previous intervals.

Height:

2

Global maximum:

2

Square 2

Interval:

[2,5)

Overlaps:

[1,3)

Base height:

2

New height:

2 + 3 = 5

Global maximum:

5

Square 3

Interval:

[6,7)

No overlap.

Height:

1

Global maximum stays:

5

Answer:

[2, 5, 5]

Correctness

Suppose a new square spans interval:

[left, right)

The square falls vertically until it reaches either:

A square can only land on squares whose horizontal intervals overlap its interval.

Therefore, the correct landing base is the maximum height among all previously placed overlapping intervals.

The algorithm checks every previous interval and computes exactly this maximum.

The new square then occupies height:

base_height + side_length

which matches the physical stacking rule.

The algorithm stores this new interval and height for future squares.

After each placement, the global maximum height among all squares is updated and appended to the answer list.

Thus, every reported height is correct.

Complexity

Let n = len(positions).

This simple solution passes because the official constraints are relatively small.

More advanced solutions use:

Implementation

class Solution:
    def fallingSquares(self, positions: list[list[int]]) -> list[int]:
        intervals = []
        answer = []

        current_max = 0

        for left, size in positions:
            right = left + size

            base_height = 0

            for prev_left, prev_right, prev_height in intervals:
                overlap = max(left, prev_left) < min(right, prev_right)

                if overlap:
                    base_height = max(base_height, prev_height)

            new_height = base_height + size

            intervals.append((left, right, new_height))

            current_max = max(current_max, new_height)
            answer.append(current_max)

        return answer

Code Explanation

We store all placed squares as:

(left, right, height)

For each new square:

for left, size in positions:

we compute its interval:

right = left + size

Initially, the square could land on the ground:

base_height = 0

We compare against every previous square:

for prev_left, prev_right, prev_height in intervals:

The overlap condition is:

max(left, prev_left) < min(right, prev_right)

If overlapping, the new square may stack higher:

base_height = max(base_height, prev_height)

The new square’s top height is:

new_height = base_height + size

Then we save the interval:

intervals.append((left, right, new_height))

Finally, update the global maximum:

current_max = max(current_max, new_height)

and append it to the answer list.

Coordinate Compression Idea

The optimized solution compresses all unique coordinates:

left
left + size

into small indices.

Then a segment tree or lazy propagation structure supports:

This improves the complexity to roughly:

O(n log n)

but the interval simulation solution is simpler and sufficient for many interview settings.

Testing

def run_tests():
    s = Solution()

    assert s.fallingSquares(
        [[1, 2], [2, 3], [6, 1]]
    ) == [2, 5, 5]

    assert s.fallingSquares(
        [[100, 100], [200, 100]]
    ) == [100, 100]

    assert s.fallingSquares(
        [[1, 5], [2, 2], [7, 1]]
    ) == [5, 7, 7]

    assert s.fallingSquares(
        [[1, 2], [1, 2], [1, 2]]
    ) == [2, 4, 6]

    assert s.fallingSquares(
        [[1, 2], [3, 2], [5, 2]]
    ) == [2, 2, 2]

    print("all tests passed")

run_tests()

Test meaning: