LeetCode 699 - Falling Squares

The problem describes a simulation of squares falling onto the X-axis. Each square is represented by two values: - lefti, the X-coordinate of the square's left edge - sideLengthi, the side length of the square A square occupies the interval: When a square falls, it continues…

leetcodehardarraysegment-treeordered-set

LeetCode Problem 699

Difficulty: 🔴 Hard
Topics: Array, Segment Tree, Ordered Set

Solution

Problem Understanding

The problem describes a simulation of squares falling onto the X-axis. Each square is represented by two values:

  • lefti, the X-coordinate of the square's left edge
  • sideLengthi, the side length of the square

A square occupies the interval:

$$[lefti,\ lefti + sideLengthi)$$

When a square falls, it continues downward until one of two things happens:

  1. It reaches the ground, which is the X-axis at height 0
  2. It lands on top of another square that overlaps horizontally

The key detail is that touching edges does not count as overlap. Two intervals overlap only if they share positive width. For example:

  • [1, 3) and [3, 5) do not overlap
  • [1, 4) and [2, 5) do overlap

For every new square:

  • We determine the maximum height among all previously placed squares that overlap horizontally
  • The new square lands on top of that height
  • Its top height becomes:

$$\text{base height} + \text{side length}$$

After placing each square, we record the tallest height seen anywhere so far.

The output array should contain these running maximum heights.

The constraints are important:

  • Up to 1000 squares
  • Coordinates can be as large as 10^8

The large coordinate range means we cannot build a giant grid or height array indexed by X-coordinate. However, the number of squares is relatively small, which suggests that comparing intervals directly is feasible.

An important observation is that every square only interacts with previously placed squares that overlap horizontally. Non-overlapping squares are completely independent.

Several edge cases can trip up naive implementations:

  • Squares that only touch edges should not stack
  • Multiple overlapping squares may create tall towers
  • Large coordinate values prevent coordinate-by-coordinate simulation
  • Nested overlaps can create cascading height increases
  • Disjoint regions must maintain separate heights

The problem guarantees valid positive coordinates and side lengths, so we never need to handle empty squares or invalid intervals.

Approaches

Brute Force Approach

The most direct approach is to simulate each falling square by comparing it against all previously placed squares.

For each new square:

  1. Compute its interval [left, right)
  2. Check every earlier square
  3. If intervals overlap, determine the maximum height among them
  4. Place the current square on top of that maximum height
  5. Record the updated global maximum

To support this, we store:

  • Left boundary
  • Right boundary
  • Top height

for every previously placed square.

This approach is correct because every square's resting height depends only on previously placed overlapping squares. Since the number of squares is only 1000, checking all earlier squares is computationally acceptable.

However, this approach becomes inefficient for larger inputs because every square may compare against every earlier square.

Better Insight

The important insight is that we do not care about every X-coordinate independently. We only care about intervals and their maximum heights.

The falling process depends entirely on interval overlap. If two squares overlap horizontally, then the later square may stack on top of the earlier one.

Instead of simulating geometry continuously, we can treat this as an interval maximum problem:

  • Query the maximum height among overlapping intervals
  • Insert a new interval with updated height

A segment tree with coordinate compression is a more scalable solution. Coordinate compression maps large coordinates into a compact index range while preserving interval relationships.

The segment tree allows:

  • Range maximum query
  • Range update

both in logarithmic time.

Although O(n^2) passes within the constraints, the segment tree solution demonstrates the intended advanced technique for this hard problem.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Compare every square with all previous squares
Optimal O(n log n) O(n) Coordinate compression with segment tree

Algorithm Walkthrough

Coordinate Compression

The coordinates can be as large as 10^8, so we compress them into a smaller index space.

For every square:

  • Add left
  • Add left + sideLength

to a set of coordinates.

After sorting these coordinates, each unique coordinate gets a compressed index.

This preserves overlap relationships while making the segment tree compact.

Segment Tree Purpose

The segment tree stores maximum heights across compressed intervals.

It supports two operations efficiently:

  1. Query the maximum height in a range
  2. Update a range to a new height

Step by Step Algorithm

  1. Collect all interval boundaries.

For each square [left, size], compute:

$$right = left + size$$

Add both left and right to a coordinate set. 2. Sort the coordinates and build a compression map.

Each unique coordinate receives an integer index. 3. Initialize a segment tree.

The tree stores maximum heights for compressed intervals. 4. Process squares one by one.

For each square:

  • Compute compressed interval indices
  • Query the current maximum height over that interval
  • New height becomes:

$$\text{base height} + \text{size}$$ 5. Update the segment tree.

Set the entire interval to the new height because the square now occupies that horizontal range. 6. Track the global maximum height.

After every insertion, append the current tallest height to the answer array.

Why it works

The invariant is that the segment tree always stores the correct maximum occupied height for every compressed interval.

When a new square falls, it must land on the tallest overlapping structure beneath it. Querying the interval maximum gives exactly that supporting height. Updating the interval afterward ensures future squares see the correct terrain.

Because every square is processed in chronological order, and every update reflects the final resting height of that square, the algorithm always produces the correct stacking heights.

Python Solution

from typing import List

class SegmentTree:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (4 * size)
        self.lazy = [0] * (4 * size)

    def push(self, node: int):
        if self.lazy[node]:
            value = self.lazy[node]

            self.tree[node * 2] = max(self.tree[node * 2], value)
            self.tree[node * 2 + 1] = max(self.tree[node * 2 + 1], value)

            self.lazy[node * 2] = max(self.lazy[node * 2], value)
            self.lazy[node * 2 + 1] = max(self.lazy[node * 2 + 1], value)

            self.lazy[node] = 0

    def update(
        self,
        node: int,
        left: int,
        right: int,
        query_left: int,
        query_right: int,
        value: int,
    ) -> None:
        if query_left > right or query_right < left:
            return

        if query_left <= left and right <= query_right:
            self.tree[node] = max(self.tree[node], value)
            self.lazy[node] = max(self.lazy[node], value)
            return

        self.push(node)

        mid = (left + right) // 2

        self.update(
            node * 2,
            left,
            mid,
            query_left,
            query_right,
            value,
        )

        self.update(
            node * 2 + 1,
            mid + 1,
            right,
            query_left,
            query_right,
            value,
        )

        self.tree[node] = max(
            self.tree[node * 2],
            self.tree[node * 2 + 1],
        )

    def query(
        self,
        node: int,
        left: int,
        right: int,
        query_left: int,
        query_right: int,
    ) -> int:
        if query_left > right or query_right < left:
            return 0

        if query_left <= left and right <= query_right:
            return self.tree[node]

        self.push(node)

        mid = (left + right) // 2

        return max(
            self.query(
                node * 2,
                left,
                mid,
                query_left,
                query_right,
            ),
            self.query(
                node * 2 + 1,
                mid + 1,
                right,
                query_left,
                query_right,
            ),
        )

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        coordinates = set()

        for left, size in positions:
            coordinates.add(left)
            coordinates.add(left + size)

        sorted_coords = sorted(coordinates)

        coordinate_index = {
            coordinate: index
            for index, coordinate in enumerate(sorted_coords)
        }

        segment_tree = SegmentTree(len(sorted_coords))

        result = []
        tallest = 0

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

            left_index = coordinate_index[left]
            right_index = coordinate_index[right] - 1

            base_height = segment_tree.query(
                1,
                0,
                len(sorted_coords) - 1,
                left_index,
                right_index,
            )

            new_height = base_height + size

            segment_tree.update(
                1,
                0,
                len(sorted_coords) - 1,
                left_index,
                right_index,
                new_height,
            )

            tallest = max(tallest, new_height)
            result.append(tallest)

        return result

The implementation begins with coordinate compression. Since coordinates can be extremely large, compression converts sparse coordinate values into dense indices.

The SegmentTree class manages interval heights. The query method retrieves the maximum height in a range, while the update method assigns a new height across an interval.

Lazy propagation is used so that range updates remain efficient. Instead of updating every leaf individually, updates are deferred until necessary.

For each square:

  1. We determine its compressed interval
  2. Query the current maximum height beneath it
  3. Compute the new top height
  4. Update the occupied interval
  5. Record the running maximum

This directly mirrors the physical falling process described in the problem.

Go Solution

package main

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type SegmentTree struct {
	tree []int
	lazy []int
	size int
}

func NewSegmentTree(size int) *SegmentTree {
	return &SegmentTree{
		tree: make([]int, 4*size),
		lazy: make([]int, 4*size),
		size: size,
	}
}

func (st *SegmentTree) push(node int) {
	if st.lazy[node] != 0 {
		value := st.lazy[node]

		st.tree[node*2] = max(st.tree[node*2], value)
		st.tree[node*2+1] = max(st.tree[node*2+1], value)

		st.lazy[node*2] = max(st.lazy[node*2], value)
		st.lazy[node*2+1] = max(st.lazy[node*2+1], value)

		st.lazy[node] = 0
	}
}

func (st *SegmentTree) update(
	node, left, right,
	queryLeft, queryRight,
	value int,
) {
	if queryLeft > right || queryRight < left {
		return
	}

	if queryLeft <= left && right <= queryRight {
		st.tree[node] = max(st.tree[node], value)
		st.lazy[node] = max(st.lazy[node], value)
		return
	}

	st.push(node)

	mid := (left + right) / 2

	st.update(
		node*2,
		left,
		mid,
		queryLeft,
		queryRight,
		value,
	)

	st.update(
		node*2+1,
		mid+1,
		right,
		queryLeft,
		queryRight,
		value,
	)

	st.tree[node] = max(
		st.tree[node*2],
		st.tree[node*2+1],
	)
}

func (st *SegmentTree) query(
	node, left, right,
	queryLeft, queryRight int,
) int {
	if queryLeft > right || queryRight < left {
		return 0
	}

	if queryLeft <= left && right <= queryRight {
		return st.tree[node]
	}

	st.push(node)

	mid := (left + right) / 2

	return max(
		st.query(
			node*2,
			left,
			mid,
			queryLeft,
			queryRight,
		),
		st.query(
			node*2+1,
			mid+1,
			right,
			queryLeft,
			queryRight,
		),
	)
}

func fallingSquares(positions [][]int) []int {
	coordinates := map[int]bool{}

	for _, position := range positions {
		left := position[0]
		size := position[1]

		coordinates[left] = true
		coordinates[left+size] = true
	}

	sortedCoords := make([]int, 0, len(coordinates))

	for coordinate := range coordinates {
		sortedCoords = append(sortedCoords, coordinate)
	}

	for i := 0; i < len(sortedCoords); i++ {
		for j := i + 1; j < len(sortedCoords); j++ {
			if sortedCoords[j] < sortedCoords[i] {
				sortedCoords[i], sortedCoords[j] =
					sortedCoords[j], sortedCoords[i]
			}
		}
	}

	coordinateIndex := map[int]int{}

	for index, coordinate := range sortedCoords {
		coordinateIndex[coordinate] = index
	}

	segmentTree := NewSegmentTree(len(sortedCoords))

	result := []int{}
	tallest := 0

	for _, position := range positions {
		left := position[0]
		size := position[1]
		right := left + size

		leftIndex := coordinateIndex[left]
		rightIndex := coordinateIndex[right] - 1

		baseHeight := segmentTree.query(
			1,
			0,
			len(sortedCoords)-1,
			leftIndex,
			rightIndex,
		)

		newHeight := baseHeight + size

		segmentTree.update(
			1,
			0,
			len(sortedCoords)-1,
			leftIndex,
			rightIndex,
			newHeight,
		)

		tallest = max(tallest, newHeight)
		result = append(result, tallest)
	}

	return result
}

The Go implementation follows the same structure as the Python version, but several language-specific differences are worth noting.

Go does not provide a built-in segment tree structure, so the tree and lazy arrays are managed manually. Slices are used instead of Python lists.

Because Go lacks a built-in max function for integers, a helper function is defined.

Maps are used for coordinate compression, and sorting is implemented manually here to keep the solution self-contained. In production code, sort.Ints would normally be preferable.

All arithmetic safely fits within Go's int type under the given constraints.

Worked Examples

Example 1

Input:

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

Step 1: Drop square [1,2]

Interval:

$$[1,3)$$

No previous squares overlap.

Base height:

$$0$$

New height:

$$0 + 2 = 2$$

Current tallest:

$$2$$

Square Interval Base Height New Height Tallest
[1,2] [1,3) 0 2 2

Result:

[2]

Step 2: Drop square [2,3]

Interval:

$$[2,5)$$

This overlaps with [1,3) because the overlap region is [2,3).

Maximum overlapping height:

$$2$$

New height:

$$2 + 3 = 5$$

Current tallest:

$$5$$

Square Interval Base Height New Height Tallest
[2,3] [2,5) 2 5 5

Result:

[2,5]

Step 3: Drop square [6,1]

Interval:

$$[6,7)$$

No overlap with previous intervals.

Base height:

$$0$$

New height:

$$1$$

Tallest remains:

$$5$$

Square Interval Base Height New Height Tallest
[6,1] [6,7) 0 1 5

Final result:

[2,5,5]

Example 2

Input:

positions = [[100,100],[200,100]]

Step 1

First square occupies:

$$[100,200)$$

Height becomes 100.

Tallest:

100

Step 2

Second square occupies:

$$[200,300)$$

The intervals only touch at 200.

Because touching edges do not count as overlap, the second square falls directly to the ground.

Height remains:

100

Final result:

[100,100]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Coordinate compression plus segment tree queries and updates
Space O(n) Compressed coordinates and segment tree storage

Coordinate compression processes 2n endpoints and sorts them, which costs:

$$O(n \log n)$$

Each square performs:

  • One range maximum query
  • One range update

Both operations take:

$$O(\log n)$$

Since there are n squares, the total runtime becomes:

$$O(n \log n)$$

The segment tree stores a constant multiple of the compressed coordinate count, so memory usage remains linear.

Test Cases

from typing import List

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        intervals = []
        result = []
        tallest = 0

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

            base_height = 0

            for prev_left, prev_right, prev_height in intervals:
                if left < prev_right and right > prev_left:
                    base_height = max(base_height, prev_height)

            new_height = base_height + size

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

            tallest = max(tallest, new_height)
            result.append(tallest)

        return result

solution = Solution()

assert solution.fallingSquares(
    [[1, 2], [2, 3], [6, 1]]
) == [2, 5, 5]  # Provided example with overlap

assert solution.fallingSquares(
    [[100, 100], [200, 100]]
) == [100, 100]  # Edge touching does not overlap

assert solution.fallingSquares(
    [[1, 1]]
) == [1]  # Single square

assert solution.fallingSquares(
    [[1, 2], [1, 2], [1, 2]]
) == [2, 4, 6]  # Complete stacking

assert solution.fallingSquares(
    [[1, 2], [4, 2], [7, 2]]
) == [2, 2, 2]  # Completely disjoint intervals

assert solution.fallingSquares(
    [[1, 5], [2, 2], [3, 1]]
) == [5, 7, 8]  # Nested overlaps

assert solution.fallingSquares(
    [[9, 7], [1, 9], [3, 1]]
) == [7, 16, 17]  # Large overlap chain

assert solution.fallingSquares(
    [[1, 1000000], [2, 999999]]
) == [1000000, 1999999]  # Large side lengths

assert solution.fallingSquares(
    [[1, 2], [3, 2], [2, 2]]
) == [2, 2, 4]  # Bridge overlap

assert solution.fallingSquares(
    [[5, 3], [5, 3], [5, 3], [5, 3]]
) == [3, 6, 9, 12]  # Repeated identical intervals
Test Why
[[1,2],[2,3],[6,1]] Validates standard overlap behavior
[[100,100],[200,100]] Confirms touching edges do not overlap
[[1,1]] Smallest valid input
[[1,2],[1,2],[1,2]] Tests repeated vertical stacking
[[1,2],[4,2],[7,2]] Tests independent intervals
[[1,5],[2,2],[3,1]] Tests nested overlaps
[[9,7],[1,9],[3,1]] Tests cascading height accumulation
[[1,1000000],[2,999999]] Tests large values
[[1,2],[3,2],[2,2]] Tests overlap with multiple neighbors
[[5,3],[5,3],[5,3],[5,3]] Tests identical intervals repeatedly

Edge Cases

Squares That Only Touch at Edges

A very common bug is treating touching intervals as overlapping.

For example:

[1,3) and [3,5)

share an endpoint but no positive-width overlap.

The implementation correctly checks overlap using:

left < prev_right and right > prev_left

This ensures edge-touching squares do not stack.

Completely Nested Squares

A smaller square may land entirely inside the horizontal span of a larger square.

Example:

[[1,5],[2,2]]

The second square fully overlaps the first and must stack on top of it.

The algorithm handles this naturally because range maximum queries return the tallest overlapping height regardless of containment relationships.

Large Sparse Coordinates

Coordinates can be extremely large, such as 10^8.

A naive coordinate-by-coordinate height array would be impossible to allocate efficiently.

Coordinate compression solves this by storing only important boundary points, reducing the problem size from potentially hundreds of millions of coordinates down to at most 2n unique endpoints.