AlgoMaster Logo

Falling Squares

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We're simulating squares being dropped onto the X-axis. Each square has a left coordinate and a side length. When a square is dropped, it falls until it either hits the top of a previously dropped square or the ground. Two squares overlap only if they share a range of X-coordinates with nonzero length. Touching at a single edge does not count.

So when square i occupies the interval [left_i, left_i + sideLength_i), it will land on top of any previously placed square whose interval overlaps with this range. Its landing height is the maximum top of all overlapping squares, plus its own side length.

After each drop, we need to report the global maximum height across all placed squares so far. The challenge is efficiently determining which previously placed squares overlap with the new one and what the maximum height is in that overlapping region.

Key Constraints:

  • 1 <= positions.length <= 1000. With at most 1000 squares, an O(n^2) solution runs in about 1 million operations, which is fast enough.
  • 1 <= left_i <= 10^8. Coordinates can be large, so we cannot index an array directly by position. With at most 1000 squares there are at most 2000 distinct coordinate values, which coordinate compression can map to a small range.
  • 1 <= sideLength_i <= 10^6. The rightmost coordinate reaches left + side, up to about 1.01 x 10^8, and stacked heights reach up to 1000 x 10^6 = 10^9, which still fits in a 32-bit signed integer.

Approach 1: Brute Force (Interval Tracking)

Intuition

Maintain a list of all previously placed squares, each described by its interval [left, right) and its top height. When a new square drops, scan through every previous square, check whether its interval overlaps with the new square's interval, and track the maximum height among all overlapping squares. The new square's top is that maximum plus its own side length.

Since n is at most 1000, scanning all previous squares for each new drop is O(n) per drop, giving O(n^2) total, about a million operations.

Algorithm

  1. Initialize an empty list to store placed squares as (left, right, height) tuples.
  2. Initialize maxHeight = 0 to track the global tallest stack.
  3. For each position [left, sideLength] in the input:
    • Compute right = left + sideLength.
    • Set base = 0 (the height this square will land on).
    • Scan all previously placed squares. If a square's interval overlaps with [left, right), update base = max(base, that square's top height).
    • The new square's top height is base + sideLength.
    • Add (left, right, base + sideLength) to the placed squares list.
    • Update maxHeight = max(maxHeight, base + sideLength).
    • Record maxHeight in the answer.
  4. Return the answer list.

Example Walkthrough

1Drop [1,2]: interval [1,3), no previous squares, base=0
0
[1,3,2]
new
1/6

Code

The scan over all previous squares is the bottleneck. The next approach replaces it with a data structure that answers "what is the maximum height in this interval?" and applies a range update, both in O(log n) time.

Approach 2: Coordinate Compression + Segment Tree

Intuition

A segment tree supports both operations the brute force struggles with: the maximum value over any range and a range update, each in O(log n) time. The new square's landing height is the maximum over its interval, and placing the square is a range update of that interval to the new top height.

The obstacle is that coordinates reach 10^8, so a segment tree indexed directly by X-coordinate would need 10^8 leaves. With at most 1000 squares there are at most 2000 distinct coordinate values, since each square contributes a left and a right. Coordinate compression maps these values to a compact range of indices, and the segment tree is built over those indices instead.

Coordinate compression works as follows: collect all left and right endpoints, sort and deduplicate them, then map each coordinate to its position in this sorted list. The tree then has at most 2000 leaves, each representing the gap between two consecutive coordinates.

For each new square dropping onto interval [left, right):

  1. Map left and right to their compressed indices.
  2. Query the segment tree for the maximum height in that compressed range.
  3. The new square's top is that max plus its side length.
  4. Update the segment tree: raise every position in the compressed range to this new top height.
  5. Update the running global maximum with this top and record it.

Algorithm

  1. Collect all left and right coordinates from every position. Sort and deduplicate them to create a compressed coordinate list.
  2. Build a mapping from each coordinate to its index in the sorted list.
  3. Build a segment tree of size equal to the number of compressed coordinates, initialized to 0.
  4. For each position [left, sideLength]:
    • Compute right = left + sideLength.
    • Find the compressed indices for left and for the last coordinate before right.
    • Query the segment tree for the max height in this compressed range.
    • Set the new height to queryResult + sideLength.
    • Update the segment tree: set every index in the range to the new height.
    • Track the global max and record it.
  5. Return the answer list.

Example Walkthrough

1Compress: {1:0, 2:1, 3:2, 5:3, 6:4, 7:5}. All heights = 0
0
0
1
0
2
0
3
0
4
0
5
0
1/8

Code