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.
This approach involves simulating the falling of each square by considering where each newly falling square intersects with squares that have already been dropped. We track the maximum heights over ranges and update them accordingly.
We use an array to maintain the maximum height for each position on the x-axis covered by the squares. For each square, we determine its position range on the x-axis, evaluate the highest point it will land on, update the height range, and then calculate the tallest height by comparing it to all other known heights.
This solution defines a function fallingSquares that takes positions as input. For each square, it calculates the position, checks for overlaps with previously dropped squares, determines where it will land, updates the height, and maintains a list of tuples that record left position, size, and current height. The heights are calculated cumulatively, and the results are generated by iterating through the list of positions.
Python
Time Complexity: O(n^2), where n is the number of positions, due to checking each new square against all previous squares.
Space Complexity: O(n), for storing heights.
This approach optimizes the brute force simulation by utilizing a segment tree to efficiently manage and query intervals. The segment tree helps update and retrieve maximum heights for given x-ranges effectively.
We map the positions along the X-axis to a discrete set, construct a segment tree to cover those discrete positions, and then for each new square, we update the segment tree with the height of the square added to the current maximum height for its X-range. This is performed in logarithmic time due to the properties of the segment tree, enabling us to handle large input sizes more rapidly.
This Java solution uses a segment tree to accomplish efficient range maximum queries and updates. The fallingSquares function first discretizes the x-coordinates for better management, then it processes each square's x-range to find the current maximum height via rangeQuery and updates this range using rangeUpdate. This allows determination of the highest structure after each square drops, maintaining optimal time complexity due to the segment tree structure.
Java
Time Complexity: O(n log n), due to the logarithmic operations with the segment tree.
Space Complexity: O(n), for storing distinct coordinates and segment tree data structures.
This approach involves using a hash map (or dictionary) to count the frequency of elements in the array. This will help us to easily keep track of the occurrences of each element, allowing us to efficiently determine if duplicates are present.
This C program uses a hash table to track the presence of elements. We compute a hash index for each number and check if that index is already set, indicating a duplicate.
Time Complexity: O(n), Space Complexity: O(n)
In this approach, we first sort the array. Then we check consecutive elements. If two consecutive elements are the same, then there is a duplicate in the array.
This C solution sorts the array first. It then checks for adjacent identical numbers, which indicates a duplicate presence.
Time Complexity: O(n log n), Space Complexity: O(1)
According to the problem description, we need to maintain a set of intervals that support modification and query operations. In this case, we can use a segment tree to solve the problem.
A segment tree divides the entire interval into multiple non-contiguous sub-intervals, with the number of sub-intervals not exceeding log(width), where width is the length of the interval. To update the value of an element, we only need to update log(width) intervals, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, we need to use lazy propagation to ensure efficiency.
[1, n];[x, x];[l, r], its left child is [l, mid], and its right child is [mid + 1, r], where mid = \frac{l + r}{2};For this problem, the information maintained by the segment tree nodes includes:
v of the blocks in the intervaladdAdditionally, since the range of the number line is very large, up to 10^8, we use dynamic node creation.
In terms of time complexity, each query and modification has a time complexity of O(log n), and the total time complexity is O(n log n). The space complexity is O(n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Simulation | Time Complexity: O(n^2), where n is the number of positions, due to checking each new square against all previous squares. |
| Using Segment Tree | Time Complexity: O(n log n), due to the logarithmic operations with the segment tree. |
| Approach 1: Use a Hash Map for Frequency Counting | Time Complexity: O(n), Space Complexity: O(n) |
| Approach 2: Sorting the Array | Time Complexity: O(n log n), Space Complexity: O(1) |
| Segment Tree | — |
| 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 |
花花酱 LeetCode 699. Falling Squares - 刷题找工作 EP97 • Hua Hua • 4,252 views views
Watch 6 more video solutions →Practice Falling Squares with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor