Sweep Line — The Skyline Problem

↗ LeetCode: The Skyline Problem · Hard · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftBloomberg

Given buildings [left, right, height], return the skyline as key points [x, y] where the height changes.

Example 1 — [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] → [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]Example 2 — [[0,2,3],[2,5,3]] → [[0,3],[5,0]] (adjacent same-height merged) Example 3 — [[1,2,1],[1,2,2],[1,2,3]] → [[1,3],[2,0]] (nested; only outer max matters)

Constraints — 1 ≤ n ≤ 10⁴. Brute per-x-coordinate max is O(coord · n) = 10⁹ ops for a full-range n=10⁴. Sweep line + max-heap is O(n log n) = 10⁵.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Every x

For each x, scan all buildings. O(n·max). TLE.

Approach 2 — Event sweep + max-heap (canonical)

Insight. Create events (x, height, isStart). Sort. Sweep; maintain heap of active heights. When top changes, emit new point.

Start: push height into heap.
End: mark for lazy removal.
Emit (x, currentMax) whenever currentMax changed since last emission.

java

List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2], b[1]}); // start (neg h)
        events.add(new int[]{b[1], 0, 0});         // end marker
    }
    events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
    List<List<Integer>> res = new ArrayList<>();
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
    pq.offer(new int[]{0, Integer.MAX_VALUE});
    int prev = 0;
    for (int[] e : events) {
        if (e[1] < 0) pq.offer(new int[]{-e[1], e[2]});
        while (pq.peek()[1] <= e[0]) pq.poll();
        int cur = pq.peek()[0];
        if (cur != prev) { res.add(Arrays.asList(e[0], cur)); prev = cur; }
    }
    return res;
}

Execution Trace

Sweep — buildings 3 shown

Complexity — Time O(n log n); Space O(n).

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Every x-scan	O(n·max)	O(1)	baseline
Event sweep + heap	O(n log n)	O(n)	canonical

When to use which

"Max active over time" → event sweep + max-heap.
Divide & conquer alternative → merge two half-skylines in O(n log n).
Segment tree with range max → same complexity, different mental model.

✨AI Study CompanionBeta

Was this page helpful?

📚 Related problems

Sweep Line — The Skyline Problem ​

Approach 1 — Every x ​

Approach 2 — Event sweep + max-heap (canonical) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​