Problem statement

A city is drawn as rectangles standing on flat ground at height 0. Building i is buildings[i] = [left, right, height]: it covers every x with left <= x < right up to height.

The skyline is the outline you see from far away — the upper contour of the union of all rectangles. Describe it as a list of key points [x, y], sorted by x: each key point is where the outline jumps to height y and stays there until the next key point. The last key point always has y = 0, marking where the rightmost building ends, and ground between separate groups of buildings shows up as a key point with y = 0 as well.

The list must be minimal: two consecutive key points never have the same height ([[2,3],[4,3]] is wrong — the second point is redundant).

The buildings are given sorted by left.

Example 1

Input: buildings = [[1,5,3],[2,4,6],[6,8,2]]
Output: [[1,3],[2,6],[4,3],[5,0],[6,2],[8,0]]
Explanation: The tall building on [2,4) hides the first one there; ground shows on [5,6).

Example 2

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]
Explanation: The two buildings touch at the same height, so the outline is one flat segment.

Example 3

Input: buildings = [[1,3,4],[1,3,7]]
Output: [[1,7],[3,0]]

Constraints

• 1 <= buildings.length <= 10^4
• 0 <= left < right <= 2^31 - 1
• 1 <= height <= 2^31 - 1
• buildings is sorted by left in non-decreasing order

Hints for The Skyline Problem

1. Hint 1

   The outline can only change height at an x where some building starts or ends — sweep those points from left to right.

2. Hint 2

   At each such x you need the tallest building that has started (left <= x) and not yet ended (right > x).

3. Hint 3

   Keep started buildings in a max-heap by height and throw away the top while it has already ended (right <= x); the top that survives is the height. Emit a key point only when it differs from the previous height.

How to solve The Skyline Problem

Sweep the distinct x coordinates where buildings begin or end. Between two consecutive ones the outline is flat, at the height of the tallest building covering that stretch — and a max-heap with lazy deletion answers that query without ever searching the middle of the heap.

Approach

1. Collect every left and right, sort them, and walk the distinct values x.
2. Push every building whose left <= x (the input is sorted by left, so a pointer suffices) into a max-heap ordered by height.
3. While the top building has right <= x, pop it — it has ended.
4. The current height is the top's height, or 0 if the heap is empty. If it differs from the last emitted height, append [x, height].

Why it works

The height on [x, x') (with x' the next event) is the maximum over buildings with left <= x < right. Every such building has been pushed. Buildings that ended may still sit deep inside the heap, but they are harmless until they reach the top, and the moment they do they are popped — so the surviving top is exactly the maximum over live buildings. Emitting only on a change keeps the list minimal.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Process all starts and ends at the same x before reading the height, or touching buildings produce a spurious dip ([2,0] then [2,3]).
• A building covers [left, right): at x = right it no longer counts, so pop on right <= x, not right < x.
• Heights reach 2^31 - 1; packing height and index into one key needs 64-bit arithmetic.

Reference solution

Python

from typing import List
import heapq

def getSkyline(buildings: List[List[int]]) -> List[List[int]]:
    xs = sorted(set([b[0] for b in buildings] + [b[1] for b in buildings]))
    heap = []  # (-height, right): tallest started building on top
    res = []
    at, n, prev = 0, len(buildings), 0
    for x in xs:
        while at < n and buildings[at][0] <= x:
            heapq.heappush(heap, (-buildings[at][2], buildings[at][1]))
            at += 1
        while heap and heap[0][1] <= x:
            heapq.heappop(heap)
        cur = -heap[0][0] if heap else 0
        if cur != prev:
            res.append([x, cur])
            prev = cur
    return res

Java

public static int[][] getSkyline(int[][] buildings) {
    int n = buildings.length;
    int[] xs = new int[2 * n];
    for (int i = 0; i < n; i++) {
        xs[2 * i] = buildings[i][0];
        xs[2 * i + 1] = buildings[i][1];
    }
    Arrays.sort(xs);
    // Indices of started buildings, tallest on top; ended ones are dropped lazily.
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> Integer.compare(buildings[b][2], buildings[a][2]));
    List<int[]> res = new ArrayList<>();
    int at = 0, prev = 0;
    for (int t = 0; t < xs.length; t++) {
        int x = xs[t];
        if (t > 0 && xs[t - 1] == x) continue;
        while (at < n && buildings[at][0] <= x) heap.add(at++);
        while (!heap.isEmpty() && buildings[heap.peek()][1] <= x) heap.poll();
        int cur = heap.isEmpty() ? 0 : buildings[heap.peek()][2];
        if (cur != prev) {
            res.add(new int[] { x, cur });
            prev = cur;
        }
    }
    return res.toArray(new int[0][]);
}

C++

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    int n = buildings.size();
    vector<int> xs;
    for (auto& b : buildings) {
        xs.push_back(b[0]);
        xs.push_back(b[1]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    priority_queue<pair<int, int>> heap; // (height, right), tallest on top
    vector<vector<int>> res;
    int at = 0, prev = 0;
    for (int x : xs) {
        while (at < n && buildings[at][0] <= x) {
            heap.push({buildings[at][2], buildings[at][1]});
            at++;
        }
        while (!heap.empty() && heap.top().second <= x) heap.pop();
        int cur = heap.empty() ? 0 : heap.top().first;
        if (cur != prev) {
            res.push_back({x, cur});
            prev = cur;
        }
    }
    return res;
}

JavaScript

var getSkyline = function(buildings) {
    var n = buildings.length;
    var xs = [];
    for (var i = 0; i < n; i++) xs.push(buildings[i][0], buildings[i][1]);
    xs.sort(function(a, b) { return a - b; });
    // Tallest started building on top: a min-heap of -(height * 16384 + index).
    var heap = [];
    var res = [];
    var at = 0, prev = 0;
    for (var t = 0; t < xs.length; t++) {
        var x = xs[t];
        if (t > 0 && xs[t - 1] === x) continue;
        while (at < n && buildings[at][0] <= x) {
            heapPush(heap, -(buildings[at][2] * 16384 + at));
            at++;
        }
        while (heap.length > 0 && buildings[(-heap[0]) % 16384][1] <= x) heapPop(heap);
        var cur = heap.length > 0 ? buildings[(-heap[0]) % 16384][2] : 0;
        if (cur !== prev) {
            res.push([x, cur]);
            prev = cur;
        }
    }
    return res;
};

var heapPush = function(h, v) {
    h.push(v);
    var i = h.length - 1;
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] <= h[i]) break;
        var t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
};

var heapPop = function(h) {
    var top = h[0];
    var last = h.pop();
    if (h.length > 0) {
        h[0] = last;
        var j = 0;
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < h.length && h[l] < h[s]) s = l;
            if (r < h.length && h[r] < h[s]) s = r;
            if (s === j) break;
            var t = h[s]; h[s] = h[j]; h[j] = t;
            j = s;
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard