> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.
> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.
# Falling Squares Python Solution with Tests
> Tested Python solution for LeetCode 699 with 20 pytest cases. Generate a practice environment with lcpy.
LeetCode 699, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Segment Tree](/catalog/topics/segment-tree), [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/falling-squares/description/).
Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:
```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 699 # by problem number
lcpy gen -s falling_squares # by problem name
```
## 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] = \[left\i\, sideLength\i\]\ represents the \i\th\\ square with a side length of \sideLength\i\\ that is dropped with its left edge aligned with X-coordinate \left\i\\.
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 \i\th\\\ square\.
### Examples
```
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].
```
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 <= 10^8`
* `1 <= sideLengthi <= 10^6`
## Solution
Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/falling_squares/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/falling_squares/test_solution.py):
```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class _MaxSegmentTree:
"""Segment tree supporting range chmax updates and range max queries."""
def __init__(self, size: int) -> None:
self.size = size
self.tree = [0] * (4 * size)
self.lazy = [0] * (4 * size)
def _push_down(self, node: int) -> None:
pending = self.lazy[node]
if pending == 0:
return
for child in (2 * node, 2 * node + 1):
if self.tree[child] < pending:
self.tree[child] = pending
if self.lazy[child] < pending:
self.lazy[child] = pending
self.lazy[node] = 0
def update(self, left: int, right: int, value: int) -> None:
self._update(1, 0, self.size - 1, left, right, value)
def _update(self, node: int, start: int, end: int, left: int, right: int, value: int) -> None:
if right < start or end < left:
return
if left <= start and end <= right:
if self.tree[node] < value:
self.tree[node] = value
if self.lazy[node] < value:
self.lazy[node] = value
return
self._push_down(node)
mid = (start + end) // 2
self._update(2 * node, start, mid, left, right, value)
self._update(2 * node + 1, mid + 1, end, left, right, value)
self.tree[node] = max(self.tree[2 * node], self.tree[2 * node + 1])
def query(self, left: int, right: int) -> int:
return self._query(1, 0, self.size - 1, left, right)
def _query(self, node: int, start: int, end: int, left: int, right: int) -> int:
if right < start or end < left:
return 0
if left <= start and end <= right:
return self.tree[node]
self._push_down(node)
mid = (start + end) // 2
return max(
self._query(2 * node, start, mid, left, right),
self._query(2 * node + 1, mid + 1, end, left, right),
)
class Solution:
# Time: O(n log n) with coordinate compression
# Space: O(n)
def falling_squares(self, positions: list[list[int]]) -> list[int]:
coords: set[int] = set()
for left, side in positions:
coords.add(left)
coords.add(left + side - 1)
axis = sorted(coords)
rank = {value: index for index, value in enumerate(axis)}
tree = _MaxSegmentTree(len(axis))
ans: list[int] = []
tallest = 0
for left, side in positions:
lo = rank[left]
hi = rank[left + side - 1]
height = tree.query(lo, hi) + side
tree.update(lo, hi, height)
tallest = max(tallest, height)
ans.append(tallest)
return ans
```
## Complexity
| Time | Space |
| - | - |
| O(n log n) with coordinate compression | O(n) |
## Tags
This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.