# LeetCode 699: Falling Squares

## Problem Restatement

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

Each square is described by:

```python
[left, side_length]
```

The square spans the interval:

```text
[left, left + side_length)
```

The square falls vertically until:

| Situation | Result |
|---|---|
| It hits the ground | Stops at height `0` |
| It lands on another square | Stacks on top |

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](https://leetcode.com/problems/falling-squares/))

## Input and Output

| Item | Meaning |
|---|---|
| Input | List `positions` of `[left, side_length]` |
| Output | List of maximum heights after each square |
| Square interval | `[left, left + side_length)` |
| Falling direction | Vertical |
| Collision rule | Overlapping intervals stack |

Example function shape:

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

## Examples

Example 1:

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

### First square

Square:

```text
[1, 3)
```

Side length:

```text
2
```

It lands on the ground.

Height becomes:

```text
2
```

Maximum height:

```python
2
```

### Second square

Square:

```text
[2, 5)
```

It overlaps the first square on interval:

```text
[2, 3)
```

So it lands on top of height `2`.

New height:

```text
2 + 3 = 5
```

Maximum height:

```python
5
```

### Third square

Square:

```text
[6, 7)
```

No overlap with previous squares.

It lands on the ground with height:

```text
1
```

The global maximum remains:

```python
5
```

Answer:

```python
[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:

```text
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:

```text
[left, right)
```

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

Suppose the current maximum overlapping height is:

```text
base
```

Then the new square's top height is:

```text
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:

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

For example:

| Interval A | Interval B | Overlap? |
|---|---|---:|
| `[1,3)` | `[2,5)` | Yes |
| `[1,2)` | `[2,4)` | No |
| `[5,7)` | `[1,5)` | No |

The intervals are half-open.

Touching edges do not overlap.

## Simple Interval Simulation

We store placed squares as:

```python
(left, right, height)
```

For each new square:

1. Compute:
   ```python id="0y8ah5"
   right = left + size
   ```
2. Initialize:
   ```python id="crw5c3"
   base_height = 0
   ```
3. Check every previous interval:
   - if overlapping:
     ```python id="u84xpm"
     base_height = max(base_height, previous_height)
     ```
4. New height:
   ```python id="kl8h6z"
   new_height = base_height + size
   ```
5. Save the interval.
6. Track the global maximum.

## Walkthrough

Consider:

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

### Square 1

Interval:

```text
[1,3)
```

No previous intervals.

Height:

```text
2
```

Global maximum:

```text
2
```

### Square 2

Interval:

```text
[2,5)
```

Overlaps:

```text
[1,3)
```

Base height:

```text
2
```

New height:

```text
2 + 3 = 5
```

Global maximum:

```text
5
```

### Square 3

Interval:

```text
[6,7)
```

No overlap.

Height:

```text
1
```

Global maximum stays:

```text
5
```

Answer:

```python
[2, 5, 5]
```

## Correctness

Suppose a new square spans interval:

```text
[left, right)
```

The square falls vertically until it reaches either:

| Situation | Landing height |
|---|---|
| Ground | `0` |
| Top of an overlapping square | That square's height |

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:

```text
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | Each square may compare against all previous squares |
| Space | `O(n)` | Store intervals and heights |

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

More advanced solutions use:

| Technique | Complexity |
|---|---|
| Coordinate compression + segment tree | `O(n log n)` |
| Balanced interval structures | `O(n log n)` |

## Implementation

```python
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:

```python
(left, right, height)
```

For each new square:

```python
for left, size in positions:
```

we compute its interval:

```python
right = left + size
```

Initially, the square could land on the ground:

```python
base_height = 0
```

We compare against every previous square:

```python
for prev_left, prev_right, prev_height in intervals:
```

The overlap condition is:

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

If overlapping, the new square may stack higher:

```python
base_height = max(base_height, prev_height)
```

The new square's top height is:

```python
new_height = base_height + size
```

Then we save the interval:

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

Finally, update the global maximum:

```python
current_max = max(current_max, new_height)
```

and append it to the answer list.

## Coordinate Compression Idea

The optimized solution compresses all unique coordinates:

```text
left
left + size
```

into small indices.

Then a segment tree or lazy propagation structure supports:

| Operation | Meaning |
|---|---|
| Range maximum query | Find base height |
| Range update | Set new height |

This improves the complexity to roughly:

```text
O(n log n)
```

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

## Testing

```python
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:

| Test | Expected | Why |
|---|---:|---|
| `[[1,2],[2,3],[6,1]]` | `[2,5,5]` | Official example |
| Separate large intervals | `[100,100]` | No overlap |
| Nested overlap | `[5,7,7]` | Second square stacks on first |
| Same interval repeated | `[2,4,6]` | Heights accumulate |
| Touching but not overlapping intervals | `[2,2,2]` | Half-open intervals do not overlap |