Falling squares

Array Segment Tree Ordered Set

47.4% acceptance

Feb 20, 2026

679

Squares fall onto the X-axis. After each drop, record the height of the tallest stack.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn falling_squares(positions: Vec<Vec<i32>>) -> Vec<i32> {
    // intervals: (left, right, height)
    let mut intervals: Vec<(i32, i32, i32)> = Vec::new();
    let mut result = Vec::new();
    let mut max_height = 0;

    for pos in &positions {
      let left = pos[0];
      let size = pos[1];
      let right = left + size;
      // Find max height of all overlapping intervals
      let base: i32 = intervals.iter()
        .filter(|&&(l, r, _)| l < right && left < r)
        .map(|&(_, _, h)| h)
        .max()
        .unwrap_or(0);
      let new_height = base + size;
      intervals.push((left, right, new_height));
      max_height = max_height.max(new_height);
      result.push(max_height);
    }
    result
  }
}