The Skyline Problem

HardHeapHeap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively. The geometric information of each building is given in the array buildings where buildings[i] = [left_i, right_i, height_i]. The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x_1,y_1],[x_2,y_2], ...]. Each key point is the left endpoint of some horizontal segment in the skyline. The last point in the list must have height 0 and marks the skyline's termination. There must be no consecutive horizontal lines of equal height in the output skyline.

Examples

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

Constraints

  • 1 <= buildings.length <= 10^4
  • 0 <= left_i < right_i <= 2^31 - 1
  • 1 <= height_i <= 2^31 - 1
  • buildings is sorted by left_i in non-decreasing order.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More Heap problems