FastPrepThe Skyline Problem
Problem · Array

The Skyline Problem

Learn this problem
● HardGoogle logoGoogleFULLTIMEPHONE SCREEN
See Google hiring insights

Problem statement

Each building is represented by [left, right, height] and covers the half-open horizontal interval [left, right). The skyline is the outer contour formed by the union of all buildings.

Return its critical points as rows [x, height] in increasing x order. A critical point records every x coordinate where the visible maximum height changes. Do not return adjacent points with equal heights, and include the final point where the skyline returns to height 0. Return an empty matrix when there are no buildings.

Function

getSkyline(buildings: int[][]) → int[][]

Examples

Example 1

buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]return = [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

The tallest active building changes at x coordinates 2, 3, 7, 12, 15, 20, and 24.

Example 2

buildings = [[0,2,3],[2,5,3]]return = [[0,3],[5,0]]

The touching buildings have equal height, so x = 2 does not change the skyline and is not a critical point.

Constraints

  • 0 <= buildings.length <= 100000
  • Every building is [left, right, height] with 0 <= left < right <= 1000000000 and 1 <= height <= 1000000000.
  • Buildings may overlap, touch, or repeat, and the input need not be sorted.

More Google problems

drafts saved locally
public int[][] getSkyline(int[][] buildings) {
    // Write your code here.
}
buildings[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
expected[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
checking account