FunctionRacerProblemsRace

Outline of the Skyline

HardSorting and searchingPython, JavaScript, TypeScript, Java, C++

Each building is [left, right, height]: a rectangle that stands on the ground from x = left to x = right. Seen from far away, the buildings merge into one outline.

Describe the outline from left to right as a list of points [x, height]: one point for every x where the height of the outline changes, with the height it changes to. Where the outline drops to the ground the height is 0, so the last point always has height 0.

Example 1

buildings [[1,5,3],[2,4,6],[7,9,2]]
returns [[1,3],[2,6],[4,3],[5,0],[7,2],[9,0]]

The outline rises to 3 at x = 1 and to 6 at x = 2, falls back to 3 at x = 4 and to the ground at x = 5. The last building stands alone from 7 to 9.

Example 2

buildings [[0,2,3],[2,5,3]]
returns [[0,3],[5,0]]

The two buildings touch and are equally tall, so nothing changes at x = 2.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Sorting and searching problems