Watch 7 video solutions for Falling Squares, a hard level problem involving Array, Segment Tree, Ordered Set. This walkthrough by Hua Hua has 4,252 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 <= 10001 <= lefti <= 1081 <= sideLengthi <= 106Problem Overview: You drop squares onto a 1D number line. Each square lands on the highest structure it overlaps with, stacking vertically. After every drop, return the maximum height of the stacked structure so far.
Approach 1: Brute Force Simulation (O(n²) time, O(n) space)
Track previously placed squares and simulate each new drop. For the current square [left, size], compute its interval [left, left + size). Iterate through all earlier squares and check for interval overlap. If two intervals intersect, update the landing height using the maximum height among overlapping squares. Store the resulting height and update the running global maximum. This approach uses simple array iteration and works well for small inputs but becomes slow as the number of squares grows.
Approach 2: Using Segment Tree with Coordinate Compression (O(n log n) time, O(n) space)
Map all square boundaries to compressed coordinates and maintain heights using a segment tree. For each square, query the maximum height in its interval and place the new square on top of that height. Then update the segment tree range with the new height value. The segment tree supports fast range maximum queries and updates in O(log n), which keeps the total complexity manageable even for large inputs.
Approach 3: Hash Map Based Height Tracking (O(n²) time, O(n) space)
Instead of a structured tree, store interval heights in a hash map keyed by square index or coordinate ranges. For each new square, scan existing entries and compute overlaps to determine the highest supporting base. Update the hash map with the resulting height and track the global maximum. This method trades structured queries for simpler implementation but still requires checking overlaps against many previously stored intervals.
Approach 4: Sorting Intervals by Position (O(n²) time, O(n) space)
Sort squares by their left coordinate and process them sequentially. Maintain a list of placed intervals and compare each new square against earlier ones that may overlap in the sorted order. Sorting reduces unnecessary comparisons for non-overlapping regions, but worst‑case complexity remains quadratic because overlapping intervals still require repeated checks. This approach helps build intuition before moving to tree-based structures or an ordered set.
Recommended for interviews: The segment tree approach is the expected optimal solution. Interviewers want to see that you recognize the repeated range maximum query pattern and apply coordinate compression with a segment tree. Starting with the brute force simulation shows understanding of the stacking mechanics, but the optimized range-query solution demonstrates stronger algorithmic design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(n) | Small inputs or when first understanding the stacking logic |
| Segment Tree with Coordinate Compression | O(n log n) | O(n) | General case with large input sizes and repeated range queries |
| Hash Map Height Tracking | O(n²) | O(n) | Simpler implementation when structured trees are unnecessary |
| Sorting Intervals | O(n²) | O(n) | When preprocessing by position helps reduce comparisons |