The Skyline Problem

HardSweep Line · Heap · Divide & Conquer🧩 Intervals & Line Sweep LeetCode #218 ↗Updated Oct 30, 2026

Problem

Each building is a rectangle on flat ground given as [left, right, height]. Return the city's outline seen from far away as a list of key points [x, y] sorted by x: each point is where the outline jumps to height y, and the final point has y = 0. Two consecutive key points must never share the same height.

Input[[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[[0,2,3],[2,5,3]]Output[[0,3],[5,0]]

1 ≤ n ≤ 10⁴ · 0 ≤ left < right ≤ 2³¹-1 · 1 ≤ height ≤ 2³¹-1 · buildings sorted by left

Try it yourself

Java

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The outline can only change at a building edge, and its height there is simply the tallest building still covering that x. Sweep the edges left to right and keep the “currently standing” heights in a max-heap.

PatternIntervals & Line Sweep

Instinct See [start, end] pairs, meetings, bookings or the word "overlap"? Sort by an endpoint, then sweep left to right carrying one running fact.

Memory hack Sort, then sweep - start time to merge, end time to choose, +1/-1 events to count the crowd.

Open the Intervals & Line Sweep guide →

Approaches

Brute ForceCheck Every Edge Against Every Building

Time O(n²)Space O(n)

Only edge coordinates can be key points. For each distinct edge x (in order), scan all buildings and take the max height of those with left ≤ x < right. Emit [x, h] whenever h differs from the previous height.

Java

public List<List<Integer>> getSkyline(int[][] buildings) {
    TreeSet<Integer> xs = new TreeSet<>();
    for (int[] b : buildings) {
        xs.add(b[0]);
        xs.add(b[1]);
    }
    List<List<Integer>> res = new ArrayList<>();
    int prev = 0;
    for (int x : xs) {
        int h = 0; // tallest building covering [x, x+1)
        for (int[] b : buildings) {
            if (b[0] <= x && x < b[1]) h = Math.max(h, b[2]);
        }
        if (h != prev) {
            res.add(List.of(x, h));
            prev = h;
        }
    }
    return res;
}

Obviously correct and a great reference, but 2n × n work is too slow at scale.

BetterDivide & Conquer — Merge Skylines

Time O(n log n)Space O(n)

Like merge sort: one building's skyline is two points; split the list, solve both halves, then merge two skylines with two pointers. While merging, track the latest height of each side; the merged height at any x is max(hLeft, hRight), emitted only when it changes.

Java

public List<List<Integer>> getSkyline(int[][] buildings) {
    return solve(buildings, 0, buildings.length - 1);
}
private List<List<Integer>> solve(int[][] b, int lo, int hi) {
    if (lo == hi) {
        List<List<Integer>> one = new ArrayList<>();
        one.add(List.of(b[lo][0], b[lo][2]));
        one.add(List.of(b[lo][1], 0));
        return one;
    }
    int mid = (lo + hi) >>> 1;
    return merge(solve(b, lo, mid), solve(b, mid + 1, hi));
}
private List<List<Integer>> merge(List<List<Integer>> a, List<List<Integer>> b) {
    List<List<Integer>> res = new ArrayList<>();
    int i = 0, j = 0, ha = 0, hb = 0;
    while (i < a.size() || j < b.size()) {
        int x;
        if (j == b.size() || (i < a.size() && a.get(i).get(0) < b.get(j).get(0))) {
            x = a.get(i).get(0);
            ha = a.get(i++).get(1);
        } else if (i == a.size() || b.get(j).get(0) < a.get(i).get(0)) {
            x = b.get(j).get(0);
            hb = b.get(j++).get(1);
        } else { // same x on both sides: advance both
            x = a.get(i).get(0);
            ha = a.get(i++).get(1);
            hb = b.get(j++).get(1);
        }
        int h = Math.max(ha, hb);
        if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) res.add(List.of(x, h));
    }
    return res;
}

Optimal complexity, but the merge has fiddly tie cases and lots of list copying.

OptimalSweep Line + Max-Heap (Lazy Removal)

Time O(n log n)Space O(n)

Visit the sorted distinct edge coordinates. At each x, push every building starting there as {height, right}, then pop heap tops whose right ≤ x (expired). Buried expired entries are harmless — only the top matters, and it is removed once it surfaces. The valid top is the outline height at x.

Java

public List<List<Integer>> getSkyline(int[][] buildings) {
    int n = buildings.length;
    int[] xs = new int[2 * n];
    for (int k = 0; k < n; k++) {
        xs[2 * k] = buildings[k][0];
        xs[2 * k + 1] = buildings[k][1];
    }
    Arrays.sort(xs);
    // {height, right}, tallest on top
    PriorityQueue<int[]> heap = new PriorityQueue<>((p, q) -> Integer.compare(q[0], p[0]));
    List<List<Integer>> res = new ArrayList<>();
    int next = 0; // next building to start (input is sorted by left)
    for (int k = 0; k < xs.length; k++) {
        int x = xs[k];
        if (k > 0 && xs[k - 1] == x) continue; // each edge x once
        while (next < n && buildings[next][0] == x) {
            heap.offer(new int[] {buildings[next][2], buildings[next][1]});
            next++;
        }
        while (!heap.isEmpty() && heap.peek()[1] <= x) heap.poll(); // expired
        int h = heap.isEmpty() ? 0 : heap.peek()[0];
        if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) res.add(List.of(x, h));
    }
    return res;
}

Same Big-O as merging, but short, iterative and the standard interview answer.

Pro tip

Process all edges at the same x before reading the height — that single rule removes every tie-breaking headache.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Edge Against Every Building	`O(n²)`	`O(n)`
Better	Divide & Conquer — Merge Skylines	`O(n log n)`	`O(n)`
Optimal	Sweep Line + Max-Heap (Lazy Removal)	`O(n log n)`	`O(n)`

Common pitfalls

Emitting a point per edge without merging equal heights — adjacent same-height blocks give duplicates.
Reading the height between a start and an end at the same x → spurious dips.
Using heap.remove(obj) for ends — O(n) per removal; lazy deletion keeps O(log n).

Interview tips

Start from “the outline only changes at an edge” — it justifies the brute force and the sweep.
Say what the heap stores ({height, right}) and why lazy expiry is safe.
Mention a TreeMap height-count multiset as the alternative with eager removal.

Pattern

Sweep line + max-heap → “what is the max over all intervals covering x” as x moves across sorted event points.

My notes saved in this browser