Code Implementation

class Solution:
    def fallingSquares(self, positions):
        intervals = []
        result = []
        max_height = 0
        for left, size in positions:
            right = left + size
            base = 0
            for l, r, h in intervals:
                if r > left and l < right:
                    base = max(base, h)
            height = base + size
            intervals.append((left, right, height))
            max_height = max(max_height, height)
            result.append(max_height)
        return result
      

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<tuple<int, int, int>> intervals;
        vector<int> result;
        int maxHeight = 0;
        for (const auto& pos : positions) {
            int left = pos[0], size = pos[1];
            int right = left + size;
            int base = 0;
            for (const auto& interval : intervals) {
                int l, r, h;
                tie(l, r, h) = interval;
                if (r > left && l < right) {
                    base = max(base, h);
                }
            }
            int height = base + size;
            intervals.emplace_back(left, right, height);
            maxHeight = max(maxHeight, height);
            result.push_back(maxHeight);
        }
        return result;
    }
};
      

class Solution {
    public List<Integer> fallingSquares(int[][] positions) {
        List<int[]> intervals = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        int maxHeight = 0;
        for (int[] pos : positions) {
            int left = pos[0], size = pos[1], right = left + size;
            int base = 0;
            for (int[] interval : intervals) {
                int l = interval[0], r = interval[1], h = interval[2];
                if (r > left && l < right) {
                    base = Math.max(base, h);
                }
            }
            int height = base + size;
            intervals.add(new int[]{left, right, height});
            maxHeight = Math.max(maxHeight, height);
            result.add(maxHeight);
        }
        return result;
    }
}
      

var fallingSquares = function(positions) {
    let intervals = [];
    let result = [];
    let maxHeight = 0;
    for (let [left, size] of positions) {
        let right = left + size;
        let base = 0;
        for (let [l, r, h] of intervals) {
            if (r > left && l < right) {
                base = Math.max(base, h);
            }
        }
        let height = base + size;
        intervals.push([left, right, height]);
        maxHeight = Math.max(maxHeight, height);
        result.push(maxHeight);
    }
    return result;
};
      

Problem Description

The "Falling Squares" problem asks you to simulate dropping a sequence of squares onto a number line. Each square is described by a pair [left, size], meaning it starts at position left and has a side length of size. Each square falls straight down until it either lands on the ground (height zero) or on top of previous squares, stacking up if it overlaps with them.

After each square falls, you need to record the current maximum height of all stacked squares so far. The final output is a list of these heights after each drop.

• Each square can overlap with multiple previous squares.
• The squares do not interact unless their projections on the number line overlap.
• Input: a list of positions where each element is [left, size].
• Output: a list of integers, each representing the tallest stack after each drop.

Thought Process

At first glance, it might seem like you can just keep track of the heights of each square independently. However, since squares can overlap and stack, we have to consider all the intervals on the number line where heights change.

A brute-force approach would be to, for each new square, check all previous squares and see if their intervals overlap. If they do, the new square must stack on top of the highest one it overlaps with. This works, but as the number of squares grows, it becomes slow.

To optimize, we consider representing the current "skyline" as a set of intervals, each with a height. When a new square falls, we only need to find the maximum height in the overlapping region, then add the square on top of that. This reduces the problem to interval management and querying.

The main challenge is efficiently finding the maximum height for overlapping intervals and updating the intervals after each drop.

Solution Approach

• Step 1: Model the intervals
  • Each fallen square creates a new interval on the number line: [left, right) with a certain height.
  • We keep a list of all intervals that have been dropped so far, each with (left, right, height).
• Step 2: For each new square
  • Calculate its left and right positions.
  • Check all previous intervals to find the maximum height among those that overlap with the new square's interval.
  • The new square's base will be at this maximum height; its own top will be base + size.
• Step 3: Update intervals and result
  • Add the new interval to the list of intervals, with its computed height.
  • Update the running maximum height so far, and append it to the result list.
• Step 4: Return the result
  • After processing all squares, return the result list of maximum heights after each drop.

This straightforward approach is easy to implement and works well for moderate input sizes. For much larger inputs, segment trees or coordinate compression can further optimize the interval queries, but the above approach is sufficient for most practical cases.

Example Walkthrough

Let's walk through an example with input positions = [[1, 2], [2, 3], [6, 1]].

• First square: [1, 2]
  • Interval: [1, 3), height: 2 (falls to the ground)
  • Intervals: [(1, 3, 2)]
  • Max height so far: 2
  • Result: [2]
• Second square: [2, 3]
  • Interval: [2, 5), size: 3
  • Overlaps with (1, 3, 2) because 3 > 2 and 1 < 5
  • Base height: 2 (from previous square)
  • New height: 2 + 3 = 5
  • Intervals: [(1, 3, 2), (2, 5, 5)]
  • Max height so far: 5
  • Result: [2, 5]
• Third square: [6, 1]
  • Interval: [6, 7), size: 1
  • No overlap with previous intervals
  • Base height: 0 (falls to ground)
  • New height: 1
  • Intervals: [(1, 3, 2), (2, 5, 5), (6, 7, 1)]
  • Max height so far: 5
  • Result: [2, 5, 5]

The final output is [2, 5, 5].

Time and Space Complexity

• Brute-force approach:
  • For each new square, we check all previous intervals for overlap. This is O(N^2) time for N squares.
  • Space is O(N) for storing the intervals.
• Optimized approach (with segment tree or coordinate compression):
  • With advanced data structures, overlap queries and updates can be reduced to O(log N) per square, making the overall time O(N log N).
  • Space remains O(N) for the intervals and data structures.

For most interview or contest settings, the O(N^2) approach is acceptable unless N is very large.

Summary

The Falling Squares problem is a simulation of stacking blocks on a number line, requiring careful interval and height management. By modeling the skyline as a list of intervals and updating heights as each square falls, we can efficiently track the maximum stack height after each drop. The key insight is to check overlaps and stack on top of the highest overlapping interval, updating the result after each step. While optimizations exist for large input sizes, the basic approach is both intuitive and effective for most scenarios.