This problem requires tracking overlapping squares and calculating the maximum height after each drop. Using a segment tree or ordered set helps efficiently find and update the tallest positions as squares land. The solution handles large coordinate ranges by compressing indices while maintaining O(N log N) performance for dynamic height updates.
Problem Statement
You are given several squares dropped one by one onto the X-axis of a 2D plane. Each square is defined by its left edge and side length in an array positions where positions[i] = [lefti, sideLengthi]. Squares fall downward until they land on the X-axis or on top of previously dropped squares without sliding past edges.
After each drop, the square freezes in place, and you need to return an array representing the tallest height after every drop. Squares that only touch the side of another square do not contribute to stacking height. Constraints include 1 <= positions.length <= 1000, 1 <= lefti <= 10^8, and 1 <= sideLengthi <= 10^6.
Examples
Example 1
Input: positions = [[1,2],[2,3],[6,1]]
Output: [2,5,5]
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]
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
Solution Approach
Coordinate Compression
Map all left and right edges of squares to a smaller index range to efficiently manage large coordinate values. This allows segment tree or ordered set operations to run in O(log N) time rather than depending on potentially huge X-axis values.
Segment Tree for Range Maximum
Use a segment tree to track maximum heights in the current covered intervals. For each square, query the maximum height in its landing interval and update the tree with the new height after placing the square.
Iterative Drop Simulation
Process squares in order. For each square, compute its landing height using the segment tree, update the maximum stack height, and append it to the result array. This captures the tallest stack dynamically as each square lands.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N \log N) |
| Space | O(N) |
Time complexity is O(N log N) because each square involves a log N query and update on the segment tree across N squares. Space complexity is O(N) for storing the compressed coordinates and segment tree nodes.
What Interviewers Usually Probe
- Check if candidates handle very large X coordinates efficiently.
- Look for proper use of range maximum queries using a segment tree or ordered set.
- Watch for mistakes in determining whether squares actually stack or just touch sides.
Common Pitfalls or Variants
Common pitfalls
- Failing to compress coordinates, causing memory overflow for large lefti values.
- Mistaking side contact for stacking, resulting in incorrect height calculation.
- Updating heights incorrectly across overlapping intervals, which produces wrong maximum heights.
Follow-up variants
- Falling rectangles instead of squares, where width varies for each drop.
- Allowing squares to slide horizontally if they touch a side, introducing physics-based landing rules.
- Computing total area covered by all stacked squares after each drop instead of just maximum height.
How GhostInterview Helps
- GhostInterview simulates each square drop and dynamically maintains the tallest stack to guide your logic.
- It highlights overlapping interval handling and coordinate compression for efficient segment tree usage.
- Provides immediate feedback on maximum height updates and common miscalculations for Falling Squares pattern.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What data structure is optimal for solving Falling Squares?
A segment tree or ordered set is optimal for efficiently tracking maximum heights in intervals as squares fall.
Do squares stacking only by side contact count?
No, only squares that fully land on top of another contribute to the height; side contact is ignored.
How do you handle very large X coordinates in Falling Squares?
Coordinate compression maps large positions into a manageable range for segment tree or ordered set operations.
Why use a segment tree instead of simple array scanning?
A segment tree reduces query and update time to O(log N), avoiding slow O(N^2) scans for overlapping intervals.
Can this pattern be applied to rectangles instead of squares?
Yes, the array plus segment tree pattern generalizes to rectangles where widths and heights vary per drop.
Need direct help with Falling Squares instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Falling Squares from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Implement a calendar supporting non-overlapping event bookings using binary search for efficient insertion and conflict detection.
Open problem page#731 My Calendar IIImplement a calendar that allows double bookings but prevents triple bookings, managing overlapping intervals efficiently with binary search.
Open problem page#850 Rectangle Area IIThe problem involves calculating the total area covered by multiple rectangles, ensuring overlap is counted only once.
Open problem page