The Skyline Problem is the hardest thing on this track so far, and almost none of the difficulty is in the algorithm. Sweep left to right tracking the tallest active building and emit a point whenever that maximum changes — that is the whole idea. The difficulty is in tie-breaking the sort and in deleting from a heap, and both have to be right or the output is subtly wrong rather than obviously broken.
The problem
Given buildings as [left, right, height], return the skyline as a list of
[x, height] key points — the left endpoint of each horizontal segment, in order, with
the last point at height 0.
[[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]]
15 ┤ ┌───┐
12 ┤ │ └───┐
10 ┤ ┌─┘ │ ┌────┐
8 ┤ │ │ │ └──┐
0 ┼─┴─────────┴────────┴───────┴──
2 3 7 12 15 19 20 24Note that 19 produces no point even though a building starts there — the taller
[15,20,10] still covers it, so the skyline does not change until that building ends at
20. A key point marks a change in the visible outline, not a building edge.
No two consecutive points may share a height — the output describes changes, so emitting
[7,12] followed by [8,12] is wrong even though the picture is the same.
That constraint is the source of most failed submissions.
The sweep
Convert each building into two events and process them left to right:
[left, right, height] -> (left, START, height)
(right, END, height)
at each x:
apply every event at that x
look at the tallest active building
if it differs from the last emitted height, emit [x, newMax]The active set needs the maximum, so it is a heap — or anything with an efficient "largest element" query. Everything below is about making that work.
The three tie-breaking rules
Events sharing an x must be ordered carefully, and each rule fixes a specific wrong
output:
1. all STARTS before all ENDS at the same x
two buildings touching at x -- one ending, one starting at the same
height -- must not produce a spurious drop to 0 and back.
2. among STARTS, TALLER first
otherwise a short building emits a point that the taller one
immediately overwrites: [x, 5] then [x, 9].
3. among ENDS, SHORTER first
same reason mirrored: removing the short one first leaves the max
unchanged and emits nothing.The standard encoding gets all three from a single sort. Represent a start as
(x, −height) and an end as (x, +height), then sort the pairs
lexicographically:
starts carry NEGATIVE heights, so they sort before ends at the same x (rule 1)
among starts, -9 < -5, so taller comes first (rule 2)
among ends, 5 < 9, so shorter comes first (rule 3)One sort key, three rules. Being able to explain why the sign trick produces all three is the single best thing to say about this problem — it is the part that looks like magic in published solutions.
Lazy deletion
The other difficulty: a binary heap has no "remove this particular element" in less than
O(n). When a building ends, its height must leave the active set — and you cannot reach
into the middle of the heap to take it.
The standard fix is lazy deletion: do not remove it. Record it in a "to be removed" multiset, and whenever the heap's top is something that should already be gone, pop and discard it. Only the top ever matters, so anything stale deeper down is harmless until it surfaces.
on END(h): toRemove[h] += 1
before reading the max:
while heap is non-empty and toRemove[heap.top] > 0:
toRemove[heap.top] -= 1
heap.pop()Each height is pushed once and popped at most once, so the cleanup is amortised
O(log n) per event despite the inner loop.
Java
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
// (x, -height) for a start, (x, +height) for an end.
// Sorting these lexicographically gives all three tie-break rules at once.
List<int[]> events = new ArrayList<>();
for (int[] b : buildings) {
events.add(new int[]{b[0], -b[2]});
events.add(new int[]{b[1], b[2]});
}
events.sort((p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0])
: Integer.compare(p[1], q[1]));
PriorityQueue<Integer> active = new PriorityQueue<>(Comparator.reverseOrder());
Map<Integer, Integer> pendingRemoval = new HashMap<>();
active.offer(0); // ground level: the skyline is never below 0
List<List<Integer>> skyline = new ArrayList<>();
int previousMax = 0;
for (int[] event : events) {
int x = event[0], signed = event[1];
if (signed < 0) {
active.offer(-signed); // a building starts
} else {
pendingRemoval.merge(signed, 1, Integer::sum); // lazy delete
}
// Discard anything on top that has already ended.
while (!active.isEmpty() && pendingRemoval.getOrDefault(active.peek(), 0) > 0) {
pendingRemoval.merge(active.peek(), -1, Integer::sum);
active.poll();
}
int currentMax = active.peek();
if (currentMax != previousMax) { // only CHANGES are points
skyline.add(List.of(x, currentMax));
previousMax = currentMax;
}
}
return skyline;
}
}Seeding the heap with 0 is what makes the final point work. When the last building
ends the heap would otherwise be empty and peek() would throw; with the ground level
always present, the max drops to 0 and [x, 0] is emitted like any other change.
Integer.compare rather than subtraction in the comparator, for the overflow reason
from Merge Intervals.
The currentMax != previousMax guard is what enforces "no two consecutive points at
the same height". Every event is processed; only some produce output.
Python
import heapq
class Solution:
def getSkyline(self, buildings: list[list[int]]) -> list[list[int]]:
# (x, -h) starts sort before (x, +h) ends; taller starts and shorter ends first.
events = sorted([(left, -height) for left, _, height in buildings]
+ [(right, height) for _, right, height in buildings])
# heapq is a MIN-heap, so heights are stored negated: heap[0] is the tallest.
heap = [0] # ground level, so the last point can be emitted
pending: dict[int, int] = {}
skyline: list[list[int]] = []
previous_max = 0
for x, signed in events:
if signed < 0:
heapq.heappush(heap, signed) # push the negative directly
else:
pending[-signed] = pending.get(-signed, 0) + 1
while heap and pending.get(heap[0], 0) > 0:
pending[heap[0]] -= 1
heapq.heappop(heap)
current_max = -heap[0]
if current_max != previous_max:
skyline.append([x, current_max])
previous_max = current_max
return skylineheapq is a min-heap, so heights are stored negated and the smallest stored value is
the tallest building. The pending map is keyed by the same negated values, which keeps
the comparison in one representation — mixing the two is the easiest way to break this.
Complexity
| Time | Space | |
|---|---|---|
| Sort the events | O(n log n) | O(n) |
| Sweep with a heap | O(n log n) | O(n) |
2n events, each doing O(log n) heap work, plus the sort. The lazy
deletion adds nothing asymptotically because each pushed height is popped at most once — that
amortised argument is the same one behind
BST Iterator and
Flatten Binary
Tree, and it keeps recurring for a reason.
The heap can hold stale entries, so its size is O(n) rather than the number of
genuinely active buildings. With a TreeMap of height counts instead, deletion is
immediate and the structure holds only live buildings — same complexity, less garbage, and a
reasonable answer if the interviewer asks about the accumulation.
The divide-and-conquer alternative
There is a second standard solution: split the buildings in half, compute each skyline
recursively, and merge the two the way merge sort merges lists — walking both and taking the
pointwise maximum. It is O(n log n) as well, and the merge step has its own
tie-breaking to get right.
Mention it. The sweep is easier to reason about under time pressure and easier to explain, but knowing the problem has a divide-and-conquer shape is what connects it to Merge k Sorted Lists — which has exactly the same two solutions, heap and pairwise merge, for the same reason.
The pattern
Sweep line with an active set solves a whole class of interval problems:
Meeting Rooms II (253) sweeps +1/−1 and tracks the peak;
Employee Free Time (759) sweeps for gaps;
Merge Intervals (56) is the
degenerate case where the active set is just a counter.
The recurring shape: turn each interval into two events, sort them, and carry a structure that answers one question about whatever is currently open. What changes between problems is only that question — the count, the maximum, the gap.
What the interviewer is checking
- That you convert buildings into events and sweep.
- All three tie-break rules, and ideally the sign trick that gives them from one sort.
- Lazy deletion, or a structure that supports removal.
- The ground-level 0 in the heap, so the final point is emitted.
- That only changes in the maximum become output points.
- Buildings that touch exactly, that nest, and that are identical.
- That the amortised cost of lazy deletion is still
O(log n).