997. Stacking Squares
Wooden tiles drop one after another onto a long shelf. Tile i is described by squares[i] = [left, size]: it is a square block whose bottom edge covers the horizontal span from left to left + size (a block of width size), and it falls straight down until it lands on the shelf or on top of earlier tiles. Tiles that only touch along a side edge do not support each other, and a landed tile never moves.
Return an array ans where ans[i] is the height of the tallest stack on the shelf right after tile i has landed. Aim for roughly O(n log n) time.
Example 1
- Input:
- squares = [[8,5],[11,4],[6,3]]
- Output:
- [5,9,9]
- Explanation:
The first tile lands on the shelf with height 5; the second overlaps it on the span 11 to 13 and rests on it, reaching 9; the third spans 6 to 9 and is supported by the first tile, giving 8, so the running tallest is 5, 9, 9.
Example 2
- Input:
- squares = [[2,3],[5,2],[1,10]]
- Output:
- [3,3,13]
- Explanation:
The first two tiles touch only at an edge, so both sit on the shelf (heights 3 and 2); the wide third tile lands on top of both at height 10 + 3 = 13.
Constraints
1 ≤ squares.length ≤ 500
1 ≤ left, size ≤ 106
All heights fit in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)