# Falling Squares
**Difficulty:** HARD
[External](https://leetcode.com/problems/falling-squares)
Canonical: https://scaleengineer.com/dsa/problems/falling-squares
**Data structures:** Array, Segment Tree, Ordered Set
**Companies:** [Block](https://scaleengineer.com/companies/block)
---
## Problem
There are several squares being dropped onto the X-axis of a 2D plane.

You are given a 2D integer array `positions` where `positions[i] = [lefti, sideLengthi]` represents the `ith` square with a side length of `sideLengthi` that is dropped with its left edge aligned with X-coordinate `lefti`.

Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands **on the top side of another square** or **on the X-axis**. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.

After each square is dropped, you must record the **height of the current tallest stack of squares**.

Return _an integer array_ `ans` _where_ `ans[i]` _represents the height described above after dropping the_ `ith` _square_.

**Example 1:**

![](https://assets.glich.co/dsa/falling-squares/image0.jpg) 

**Input:** positions = [[1,2],[2,3],[6,1]]
**Output:** [2,5,5]
**Explanation:**
After the first drop, the tallest stack is square 1 with a height of 2.
After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
Thus, we return an answer of [2, 5, 5].

**Example 2:**

**Input:** positions = [[100,100],[200,100]]
**Output:** [100,100]
**Explanation:**
After the first drop, the tallest stack is square 1 with a height of 100.
After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100.
Thus, we return an answer of [100, 100].
Note that square 2 only brushes the right side of square 1, which does not count as landing on it.

**Constraints:**

* `1 <= positions.length <= 1000`
* `1 <= lefti <= 108`
* `1 <= sideLengthi <= 106`

# Approaches
## Brute Force Simulation
This approach directly simulates the process of dropping squares one by one. For each new square, it iterates through all the squares that have already been dropped to determine the highest point on which the new square will land. This is the most straightforward way to solve the problem, relying on basic loops and comparisons.
**Time:** O(N^2), where N is the number of squares. For each of the N squares, we iterate through up to N-1 previous squares, leading to a quadratic time complexity. · **Space:** O(N), where N is the number of squares. This space is used to store the heights of the dropped squares and the answer list.
**Pros:** Simple to understand and implement.; Does not require complex data structures.; Works efficiently enough for the given constraints.
**Cons:** The `O(N^2)` time complexity can be too slow for larger constraints, although it is acceptable for `N <= 1000`.
### Explanation
We process the squares in the given order. For each square, we need to find the height of the ground it will land on. This 'ground' can be the X-axis (height 0) or the top surface of a previously dropped square. To find this, we check the new square's horizontal interval against the interval of every square that has already landed. We find the maximum height among all the squares it overlaps with. This maximum height is the base on which the new square settles. The new square's final height is this base height plus its own side length. We keep track of the heights of all squares and the overall maximum height after each drop.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        // heights[i] stores the final height of the i-th square
        List<Integer> heights = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        int maxH = 0;

        for (int i = 0; i < n; i++) {
            int left1 = positions[i][0];
            int side1 = positions[i][1];
            int right1 = left1 + side1;
            
            int baseHeight = 0;
            // Iterate through all previously dropped squares
            for (int j = 0; j < i; j++) {
                int left2 = positions[j][0];
                int side2 = heights.get(j) - (j > 0 ? findBaseHeight(j, i, positions, heights) : 0); // This is complex, let's simplify
                // A simpler way is to store the original side length and calculate height on the fly
                // But we need the final height of the square, not its side length.
                // Let's store final heights and intervals.
                int prev_left = positions[j][0];
                int prev_side = positions[j][1]; // This is not correct, we need the final height
                int prev_right = prev_left + prev_side; // This is also not correct
                // The interval is defined by positions[j], the height is in heights.get(j)
                int prev_pos_left = positions[j][0];
                int prev_pos_side = positions[j][1];
                int prev_pos_right = prev_pos_left + prev_pos_side;

                // Check for horizontal overlap
                if (left1 < prev_pos_right && prev_pos_left < right1) {
                    baseHeight = Math.max(baseHeight, heights.get(j));
                }
            }
            
            int currentHeight = baseHeight + side1;
            heights.add(currentHeight);
            maxH = Math.max(maxH, currentHeight);
            ans.add(maxH);
        }
        
        return ans;
    }
}
```
*Note: The provided code snippet in the detailed description has a slight correction for clarity. The logic remains the same: for each square `i`, it checks against all previous squares `j` using their original positions to define intervals and their calculated final heights from the `heights` list.*
### Algorithm
- Initialize an empty list `heights` to store the final height of each square after it lands.
- Initialize an empty list `ans` to store the result, and a variable `maxHeight` to 0 to track the tallest stack so far.
- Iterate through each square `i` from the input `positions`:
  - For the current square `i` with interval `[left1, right1)`, initialize its `baseHeight` to 0.
  - Iterate through all previously dropped squares `j` (where `j < i`):
    - Get the interval `[left2, right2)` and height `h2` of square `j`.
    - Check if square `i` and square `j` overlap horizontally. The condition for overlap is `left1 < right2` and `left2 < right1`.
    - If they overlap, update `baseHeight = max(baseHeight, h2)`.
  - The current square `i` will land on top of the highest square beneath it. Its final height will be `currentHeight = baseHeight + sideLength_i`.
  - Add `currentHeight` to the `heights` list.
  - Update the overall maximum height: `maxHeight = max(maxHeight, currentHeight)`.
  - Add the current `maxHeight` to the `ans` list.
- After iterating through all squares, return the `ans` list.

## Segment Tree with Coordinate Compression
A more efficient approach uses a segment tree combined with coordinate compression. The core of the problem is to perform range maximum queries (to find the base height) and range updates (to set the new height). A segment tree with lazy propagation is the ideal data structure for this. Since the coordinate values can be very large (up to 10^8), we can't use a simple array. Coordinate compression maps these large coordinates to a smaller, manageable range of indices, allowing us to build a segment tree on top of them.
**Time:** O(N log N), where N is the number of squares. Coordinate compression takes `O(N log N)` for sorting. Each of the N squares involves a query and an update on the segment tree, both of which take `O(log N)` time. · **Space:** O(N), where N is the number of squares. The space is used for coordinate mapping (`O(N)`), the segment tree (`O(N)` since the number of unique coordinates is at most `2N`), and the answer list (`O(N)`).
**Pros:** Highly efficient with `O(N log N)` time complexity.; Scales well to much larger inputs than the brute-force approach.; It is a standard and powerful technique for a wide class of interval-based problems.
**Cons:** Significantly more complex to implement correctly compared to the brute-force approach.; The overhead of coordinate compression and the segment tree data structure might make it slower for very small N, though its asymptotic advantage is clear.
### Explanation
This method optimizes the query and update steps. Instead of a linear scan, we use a data structure that handles these operations in logarithmic time.

**1. Coordinate Compression:**
The number of squares `N` is at most 1000, so there are at most `2N` distinct x-coordinates (`left` and `left + side`). We gather all these coordinates, sort them, and assign a unique index to each. This allows us to work with a compact index range (e.g., 0 to `2N-1`) instead of the vast original coordinate range.

**2. Segment Tree with Lazy Propagation:**
We build a segment tree over the compressed indices. Each leaf of the tree represents an elementary interval between two consecutive unique coordinates. An internal node represents the union of its children's intervals and stores the maximum height found within that union.

When a square is dropped:
- We query the segment tree for the maximum height in the range corresponding to the square's base. This takes `O(log N)` time.
- After calculating the new height, we update the same range in the segment tree with this new value. A simple update would be slow, so we use lazy propagation to perform range updates in `O(log N)` time as well.
- The maximum height of all stacks at any point is simply the value at the root of the segment tree.

```java
import java.util.*;

class Solution {
    private static class SegmentTree {
        private final int[] tree;
        private final int[] lazy;
        private final int n;

        public SegmentTree(int size) {
            this.n = size;
            this.tree = new int[4 * n];
            this.lazy = new int[4 * n];
        }

        private void push(int v) {
            if (lazy[v] != 0 && v * 2 + 1 < 4 * n) { // Check bounds for children
                tree[2 * v] = lazy[v];
                lazy[2 * v] = lazy[v];
                tree[2 * v + 1] = lazy[v];
                lazy[2 * v + 1] = lazy[v];
                lazy[v] = 0;
            }
        }

        public void update(int v, int tl, int tr, int l, int r, int new_val) {
            if (l > r) return;
            if (l == tl && r == tr) {
                tree[v] = new_val;
                lazy[v] = new_val;
            } else {
                push(v);
                int tm = tl + (tr - tl) / 2;
                update(2 * v, tl, tm, l, Math.min(r, tm), new_val);
                update(2 * v + 1, tm + 1, tr, Math.max(l, tm + 1), r, new_val);
                tree[v] = Math.max(tree[2 * v], tree[2 * v + 1]);
            }
        }

        public int query(int v, int tl, int tr, int l, int r) {
            if (l > r) return 0;
            if (l <= tl && tr <= r) {
                return tree[v];
            }
            push(v);
            int tm = tl + (tr - tl) / 2;
            int left_max = query(2 * v, tl, tm, l, Math.min(r, tm));
            int right_max = query(2 * v + 1, tm + 1, tr, Math.max(l, tm + 1), r);
            return Math.max(left_max, right_max);
        }
    }

    public List<Integer> fallingSquares(int[][] positions) {
        Set<Integer> coordSet = new HashSet<>();
        for (int[] pos : positions) {
            coordSet.add(pos[0]);
            coordSet.add(pos[0] + pos[1]);
        }
        List<Integer> sortedCoords = new ArrayList<>(coordSet);
        Collections.sort(sortedCoords);
        Map<Integer, Integer> coordMap = new HashMap<>();
        for (int i = 0; i < sortedCoords.size(); i++) {
            coordMap.put(sortedCoords.get(i), i);
        }

        int numIntervals = sortedCoords.size() -1;
        SegmentTree st = new SegmentTree(sortedCoords.size());
        List<Integer> ans = new ArrayList<>();
        int maxH = 0;

        for (int[] pos : positions) {
            int left = pos[0];
            int side = pos[1];
            int right = left + side;
            
            int l_idx = coordMap.get(left);
            int r_idx = coordMap.get(right) - 1;

            int baseHeight = st.query(1, 0, numIntervals, l_idx, r_idx);
            int currentHeight = baseHeight + side;
            st.update(1, 0, numIntervals, l_idx, r_idx, currentHeight);
            
            maxH = Math.max(maxH, currentHeight);
            ans.add(maxH);
        }
        return ans;
    }
}
```
### Algorithm
- **Coordinate Compression**:
  1. Collect all unique x-coordinates that define the start and end points of the squares' intervals (`left` and `left + sideLength`).
  2. Sort these unique coordinates and create a mapping from each coordinate to its rank (index). This compresses the large coordinate space into a small set of indices.
- **Segment Tree Operations**:
  1. Build a segment tree over the compressed coordinate indices. Each node in the tree will store the maximum height over its corresponding range. The tree must support range maximum query and range update, for which lazy propagation is used.
  2. Initialize a list `ans` and `maxHeight = 0`.
  3. For each square `[left, side]`:
     a. Find the compressed indices `l_idx` and `r_idx` corresponding to the interval `[left, left + side)`.
     b. Query the segment tree for the maximum height in the range `[l_idx, r_idx]`. This is the `baseHeight`.
     c. Calculate the new height: `newHeight = baseHeight + side`.
     d. Update the segment tree for the range `[l_idx, r_idx]` with `newHeight`.
     e. The overall maximum height is the value at the root of the segment tree. Add this to the `ans` list.
- Return the `ans` list.

# Solutions
### Java

```java
class Node { Node left ; Node right ; int l ; int r ; int mid ; int v ; int add ; public Node ( int l , int r ) { this . l = l ; this . r = r ; this . mid = ( l + r ) >> 1 ; } } class SegmentTree { private Node root = new Node ( 1 , ( int ) 1 e9 ); public SegmentTree () { } public void modify ( int l , int r , int v ) { modify ( l , r , v , root ); } public void modify ( int l , int r , int v , Node node ) { if ( l > r ) { return ; } if ( node . l >= l && node . r <= r ) { node . v = v ; node . add = v ; return ; } pushdown ( node ); if ( l <= node . mid ) { modify ( l , r , v , node . left ); } if ( r > node . mid ) { modify ( l , r , v , node . right ); } pushup ( node ); } public int query ( int l , int r ) { return query ( l , r , root ); } public int query ( int l , int r , Node node ) { if ( l > r ) { return 0 ; } if ( node . l >= l && node . r <= r ) { return node . v ; } pushdown ( node ); int v = 0 ; if ( l <= node . mid ) { v = Math . max ( v , query ( l , r , node . left )); } if ( r > node . mid ) { v = Math . max ( v , query ( l , r , node . right )); } return v ; } public void pushup ( Node node ) { node . v = Math . max ( node . left . v , node . right . v ); } public void pushdown ( Node node ) { if ( node . left == null ) { node . left = new Node ( node . l , node . mid ); } if ( node . right == null ) { node . right = new Node ( node . mid + 1 , node . r ); } if ( node . add != 0 ) { Node left = node . left , right = node . right ; left . add = node . add ; right . add = node . add ; left . v = node . add ; right . v = node . add ; node . add = 0 ; } } } class Solution { public List < Integer > fallingSquares ( int [][] positions ) { List < Integer > ans = new ArrayList <>(); SegmentTree tree = new SegmentTree (); int mx = 0 ; for ( int [] p : positions ) { int l = p [ 0 ], w = p [ 1 ], r = l + w - 1 ; int h = tree . query ( l , r ) + w ; mx = Math . max ( mx , h ); ans . add ( mx ); tree . modify ( l , r , h ); } return ans ; } }
```

### CPP

```cpp
class Node { public: Node * left ; Node * right ; int l ; int r ; int mid ; int v ; int add ; Node ( int l , int r ) { this -> l = l ; this -> r = r ; this -> mid = ( l + r ) >> 1 ; this -> left = this -> right = nullptr ; v = add = 0 ; } }; class SegmentTree { private: Node * root ; public: SegmentTree () { root = new Node ( 1 , 1e9 ); } void modify ( int l , int r , int v ) { modify ( l , r , v , root ); } void modify ( int l , int r , int v , Node * node ) { if ( l > r ) return ; if ( node -> l >= l && node -> r <= r ) { node -> v = v ; node -> add = v ; return ; } pushdown ( node ); if ( l <= node -> mid ) modify ( l , r , v , node -> left ); if ( r > node -> mid ) modify ( l , r , v , node -> right ); pushup ( node ); } int query ( int l , int r ) { return query ( l , r , root ); } int query ( int l , int r , Node * node ) { if ( l > r ) return 0 ; if ( node -> l >= l && node -> r <= r ) return node -> v ; pushdown ( node ); int v = 0 ; if ( l <= node -> mid ) v = max ( v , query ( l , r , node -> left )); if ( r > node -> mid ) v = max ( v , query ( l , r , node -> right )); return v ; } void pushup ( Node * node ) { node -> v = max ( node -> left -> v , node -> right -> v ); } void pushdown ( Node * node ) { if ( ! node -> left ) node -> left = new Node ( node -> l , node -> mid ); if ( ! node -> right ) node -> right = new Node ( node -> mid + 1 , node -> r ); if ( node -> add ) { Node * left = node -> left ; Node * right = node -> right ; left -> v = node -> add ; right -> v = node -> add ; left -> add = node -> add ; right -> add = node -> add ; node -> add = 0 ; } } }; class Solution { public: vector < int > fallingSquares ( vector < vector < int >>& positions ) { vector < int > ans ; SegmentTree * tree = new SegmentTree (); int mx = 0 ; for ( auto & p : positions ) { int l = p [ 0 ], w = p [ 1 ], r = l + w - 1 ; int h = tree -> query ( l , r ) + w ; mx = max ( mx , h ); ans . push_back ( mx ); tree -> modify ( l , r , h ); } return ans ; } };
```

### Python

```python
class Node : def __init__ ( self , l , r ): self . left = None self . right = None self . l = l self . r = r self . mid = ( l + r ) >> 1 self . v = 0 self . add = 0 class SegmentTree : def __init__ ( self ): self . root = Node ( 1 , int ( 1e9 )) def modify ( self , l , r , v , node = None ): if l > r : return if node is None : node = self . root if node . l >= l and node . r <= r : node . v = v node . add = v return self . pushdown ( node ) if l <= node . mid : self . modify ( l , r , v , node . left ) if r > node . mid : self . modify ( l , r , v , node . right ) self . pushup ( node ) def query ( self , l , r , node = None ): if l > r : return 0 if node is None : node = self . root if node . l >= l and node . r <= r : return node . v self . pushdown ( node ) v = 0 if l <= node . mid : v = max ( v , self . query ( l , r , node . left )) if r > node . mid : v = max ( v , self . query ( l , r , node . right )) return v def pushup ( self , node ): node . v = max ( node . left . v , node . right . v ) def pushdown ( self , node ): if node . left is None : node . left = Node ( node . l , node . mid ) if node . right is None : node . right = Node ( node . mid + 1 , node . r ) if node . add : node . left . v = node . add node . right . v = node . add node . left . add = node . add node . right . add = node . add node . add = 0 class Solution : def fallingSquares ( self , positions : List [ List [ int ]]) -> List [ int ]: ans = [] mx = 0 tree = SegmentTree () for l , w in positions : r = l + w - 1 h = tree . query ( l , r ) + w mx = max ( mx , h ) ans . append ( mx ) tree . modify ( l , r , h ) return ans
```