Show problems as
Classic problem #218HardArrayDivide and ConquerBinary Indexed TreeSegment TreeSweep LineSortingHeap (Priority Queue)Ordered Set

The Skyline Problem

Real-world version: Outline of a Row of Blocks
Tracked in this browser only
Read The Skyline Problem on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Blocks stand in a row along a line. Each entry of buildings is [left, right, height] for one block, standing on the ground between those two positions with that height. The list is given in non-decreasing order of left.

The outline is the shape of the row seen from a distance. Return it as a list of [position, height] turning points, in increasing order of position: each turning point marks a position where the outline's height changes, giving the new height. The height after the last block is 0, so the final turning point always has height 0. No two turning points share a position, and no two neighbouring turning points have the same height.

Examples

Example 1

Input
buildings = [[3, 9, 14], [5, 12, 27], [11, 18, 6], [20, 24, 31]]
Output
[[3, 14], [5, 27], [12, 6], [18, 0], [20, 31], [24, 0]]

The outline rises to 14 at position 3, to 27 at 5 where the taller block starts, drops to 6 at 12 where that block ends, falls to nothing at 18, and then rises to 31 at 20 before ending at 24.

Example 2

Input
buildings = [[0, 5, 3], [5, 10, 3]]
Output
[[0, 3], [10, 0]]

The two blocks are the same height and meet exactly, so the outline shows one step up and one step down with no turning point in the middle.

Example 3

Input
buildings = [[0, 1, 1]]
Output
[[0, 1], [1, 0]]

A single block gives one step up and one step back down to nothing.

Constraints

  • 1 <= buildings.length <= 10^4
  • buildings[i].length == 3
  • 0 <= buildings[i][0] < buildings[i][1] <= 2^31 - 1
  • 1 <= buildings[i][2] <= 2^31 - 1
  • buildings is given in non-decreasing order of buildings[i][0]

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def get_skyline(buildings: list[list[int]]) -> list[list[int]]:
Java
public List<List<Integer>> getSkyline(int[][] buildings)

More on the same topics