Falling Squares

Falling Squares

What is this problem about?

The Falling Squares interview question describes a physical simulation where squares are dropped onto an infinite X-axis. Each square has a starting position and a side length. When a square falls, it lands on the highest existing surface below its span. This creates a "stacking" effect. After each square is dropped, you need to report the current maximum height of any part of the built structure.

Why is this asked in interviews?

Companies like Uber and Amazon ask the Falling Squares coding problem to test your knowledge of Range Query data structures. It's a "Hard" difficulty problem because it requires efficiently finding the maximum height in a range and updating that range with a new height. It evaluates whether you can move beyond O(N^2) complexity to O(N log N) using advanced structures like Segment Trees or coordinate compression.

Algorithmic pattern used

This problem is a classic application of Coordinate Compression and Segment Tree with Lazy Propagation.

1. Coordinate Compression: Since the positions can be up to 10^8 but there are only O(N) squares, collect all start and end points and map them to a small range [0, 2N].
2. Segment Tree:
   • Use a Segment Tree to store the maximum height in a range.
   • For each square [left, right, size]:
     • Query the Segment Tree for the max height h in range [left, right].
     • Update the range [left, right] with the new height h + size.
   • Record the global maximum height.

Example explanation

1. Square 1: pos=1, size=2. Range [1, 3]. Max height in range is 0. New height = 2. Global max = 2.
2. Square 2: pos=2, size=3. Range [2, 5]. Max height in [2, 5] is currently 2 (from Square 1). New height = 2 + 3 = 5. Global max = 5.
3. Square 3: pos=6, size=1. Range [6, 7]. Max height in range is 0. New height = 1. Global max remains 5. Output: [2, 5, 5].

Common mistakes candidates make

• Linear Scan: Checking every previously dropped square for every new drop, resulting in O(N^2) time. This will time out for large N.
• Off-by-one: Mistakes in handling range boundaries (is the end left + size or left + size - 1?).
• Incorrect Update: Forgetting that a square lands on top of the highest point in its entire span, not just its starting point.

Interview preparation tip

Whenever you see "intervals" or "ranges" and "maximum value," think of a Segment Tree. Even if you implement a simpler O(N log N) solution using a sorted list of intervals, mentioning Segment Trees shows deep technical knowledge.