Falling Squares

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 i^th 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 in the negative Y direction until it either lands on the top side of another square or on the X-axis. A square brushing the left or 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 i^th square.

Example 1

Inputpositions = [[1,2],[2,3],[6,1]]

Output[2,5,5]

After the first two drops, squares 1 and 2 form a stack of height 5, and the third square does not increase the tallest height.

Example 2

Inputpositions = [[100,100],[200,100]]

Output[100,100]

The second square only brushes the right side of the first square, so both stacks have height 100.

Constraints

1 <= positions.length <= 1000
1 <= lefti <= 10^8
1 <= sideLengthi <= 10^6

Falling Squares

Constraints

Asked at 3 companies

Your Solution

Switching Language

AI code evaluation