218. The Skyline Problem
hardAsked at UberGiven buildings as (left, right, height) triples, return the skyline outline as a list of key points. Uber asks this to test sweep-line + max-heap (or divide-and-conquer like merge-sort).
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Uber loops.
- Glassdoor (2026-Q1)— Uber senior+ onsite reports include this as a recurring hard.
- Blind (2025-10)— Mentioned in Uber map / geospatial team interviews.
Problem
A city's skyline is the outer contour of the silhouette formed by all the buildings 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] = [lefti, righti, heighti]. The skyline should be represented as a list of 'key points' sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...].
Constraints
1 <= buildings.length <= 10^40 <= lefti < righti <= 2^31 - 11 <= heighti <= 2^31 - 1buildings is sorted by lefti in non-decreasing order.
Examples
Example 1
buildings = [[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
buildings = [[0,2,3],[2,5,3]][[0,3],[5,0]]Approaches
1. Sweep line with max-heap (optimal)
Convert each building to two events: (left, -h) and (right, h). Sort. Maintain a max-heap of active heights; lazy-delete when the top has expired. Emit a key point whenever the heap top changes.
- Time
- O(n log n)
- Space
- O(n)
class MaxHeap {
constructor() { this.data = []; }
push(x) {
this.data.push(x);
let i = this.data.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.data[p][0] >= this.data[i][0]) break;
[this.data[p], this.data[i]] = [this.data[i], this.data[p]];
i = p;
}
}
top() { return this.data[0]; }
pop() {
const t = this.data[0];
const last = this.data.pop();
if (this.data.length) {
this.data[0] = last;
let i = 0;
while (true) {
let l = 2 * i + 1, r = 2 * i + 2, best = i;
if (l < this.data.length && this.data[l][0] > this.data[best][0]) best = l;
if (r < this.data.length && this.data[r][0] > this.data[best][0]) best = r;
if (best === i) break;
[this.data[best], this.data[i]] = [this.data[i], this.data[best]];
i = best;
}
}
return t;
}
}
function getSkyline(buildings) {
const events = [];
for (const [l, r, h] of buildings) {
events.push([l, -h, r]);
events.push([r, 0, 0]);
}
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const heap = new MaxHeap();
heap.push([0, Infinity]);
const result = [];
let prev = 0;
for (const [x, h, r] of events) {
if (h < 0) heap.push([-h, r]);
while (heap.data.length && heap.top()[1] <= x) heap.pop();
const cur = heap.top()[0];
if (cur !== prev) { result.push([x, cur]); prev = cur; }
}
return result;
}Tradeoff: Each event is processed O(log n) — push, lazy-pop. Lazy deletion (pop only when the top has expired) is what keeps it O(n log n) instead of O(n^2).
2. Divide and conquer (merge skylines)
Recursively compute the skylines of left and right halves; merge them with a two-pointer pass that tracks current heights on each side.
- Time
- O(n log n)
- Space
- O(n)
function getSkylineDC(buildings) {
function merge(a, b) {
let i = 0, j = 0, h1 = 0, h2 = 0;
const out = [];
while (i < a.length && j < b.length) {
const [x1, y1] = a[i], [x2, y2] = b[j];
let x, h;
if (x1 < x2) { h1 = y1; x = x1; i++; }
else if (x2 < x1) { h2 = y2; x = x2; j++; }
else { h1 = y1; h2 = y2; x = x1; i++; j++; }
h = Math.max(h1, h2);
if (out.length === 0 || out[out.length - 1][1] !== h) out.push([x, h]);
}
while (i < a.length) out.push(a[i++]);
while (j < b.length) out.push(b[j++]);
return out;
}
function solve(l, r) {
if (l === r) {
const [bl, br, h] = buildings[l];
return [[bl, h], [br, 0]];
}
const m = (l + r) >> 1;
return merge(solve(l, m), solve(m + 1, r));
}
if (!buildings.length) return [];
return solve(0, buildings.length - 1);
}Tradeoff: Same asymptotic complexity as the sweep-line version. Often cleaner code if you've internalized the merge-sort template. Avoids the heap entirely.
Uber-specific tips
Uber's bar on this is the event-based framing for the sweep-line version: 'Each building generates a start event (height enters the active set) and an end event (height leaves). The skyline changes only at events. The current outline is the max of the active heights.' For D&C, emphasize that you're merging two skylines the way merge-sort merges two sorted arrays.
Common mistakes
- Tie-breaking events at the same x-coordinate wrong (start events should come before end events at the same x).
- Forgetting to skip duplicate y values in the output.
- Using a max-heap without lazy deletion — eager deletion is O(n) per op and times out.
Follow-up questions
An interviewer at Uber may pivot to one of these next:
- What if buildings have curved roofs (not rectangles)?
- What if there are millions of buildings? (Sweep-line still works; D&C parallelizes naturally.)
- Rectangle Area II (LC 850) — total area covered, related sweep-line problem.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why lazy deletion in the heap?
Eager removal of a specific element from a heap is O(n) — you'd have to scan to find it. Lazy means you only pop expired entries when they reach the top; total work is still O(n log n).
D&C or sweep-line — which does Uber prefer?
Both pass equivalently. Sweep-line is the more naturally framed answer for interview narration. D&C is sometimes shorter code if you've already practiced the merge step.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill The Skyline Problem and other Uber interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →