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 <= 106This 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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), Space Complexity: O(1)
| 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) |
8 patterns to solve 80% Leetcode problems • Sahil & Sarra • 656,569 views views
Watch 9 more video solutions →Practice Falling Squares with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor