Problem Description
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 ith 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 until it either lands on the top side of another square or on the X-axis. 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.
Key Insights
- Each square can potentially affect the height of previously dropped squares.
- The problem can be visualized as managing a series of intervals on the Y-axis, where each square represents an interval that can change the maximum height.
- Efficiently determining the maximum height that a new square can land on requires keeping track of the heights of overlapping intervals.
- A data structure like a segment tree or ordered set can be used to manage and query the heights.
Space and Time Complexity
Time Complexity: O(n log n) - where n is the number of squares, due to the need to maintain and query the height intervals efficiently. Space Complexity: O(n) - to store the heights of the squares.
Solution
To solve the problem, we can use a list to keep track of the heights of the dropped squares. Each time a square is dropped, we check the current heights of any squares that overlap with the square being dropped. If it overlaps, we calculate the maximum height it can land on and update the height of the new square accordingly. We then append the height of the tallest stack to the result list.