The Skyline Problem LeetCode 218 Guide

LeetCode 218 The Skyline Problem takes a list of buildings, each described as [left, right, height], and asks you to output the skyline silhouette as a list of key points. Each key point [x, h] marks an x-coordinate where the visible skyline height changes: h is the new height after the change. The output is the minimal list of such points that fully describes the silhouette outline when looking at all buildings from the front.

For example, given buildings [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]], the skyline is [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]. Each key point records the x where the outline profile transitions to a new height. The final key point in any valid output must end with height 0, signaling that the skyline returns to ground level.

The key challenge is that buildings can overlap arbitrarily. A tall building might be fully contained within a wide short one, two buildings might share only one edge, or many buildings might all start at the same x. An efficient solution must identify exactly those x-positions where the maximum visible height changes — skipping positions where overlapping buildings maintain a constant peak — and do so in O(n log n) time.

The line sweep approach transforms each building into two events: a start event at the left edge and an end event at the right edge. Instead of reasoning about all x-coordinates continuously, the algorithm only visits the finite set of x-values where something changes — the building edges. Between consecutive events, the set of active buildings and therefore the skyline height remains constant.

At each x-coordinate, the skyline height equals the maximum height among all currently active buildings — those whose left edge has been passed but whose right edge has not yet been reached. By sweeping events left to right and maintaining a data structure of active heights, the algorithm can detect each height change in O(log n) per event, giving O(n log n) total for n buildings generating 2n events.

The event list is built by iterating over buildings: each building [l, r, h] produces a start event at x=l with height h and an end event at x=r with height h. After sorting all events by x, the sweep processes them in order, updating the active heights set and checking whether the current maximum changed. If it did, a new key point is added to the output.

A max-heap efficiently tracks the current maximum active height. As events are processed left to right, start events push a height onto the heap and end events mark that height for removal. After processing all events at a given x-coordinate, the heap top gives the current maximum height. If this maximum differs from the previous step's maximum, a key point [x, new_max] is appended to the result.

The algorithm initializes with an empty heap and prev_max = 0 (ground level). For each group of events at the same x, all starts are processed first (pushing their heights) and then all ends are processed (marking heights for removal). After the group, the heap top is queried: if it differs from prev_max, emit [x, heap_top] and update prev_max. This ensures that positions where starts and ends at the same x cancel out do not generate spurious key points.

The max-heap guarantees O(log n) push and O(log n) for extracting the maximum. With 2n events and O(log n) work per event, total time is O(n log n). The result list grows only when height changes occur, so its size is at most 2n but typically much smaller for non-degenerate inputs.

When multiple buildings share the same left or right edge, the order of event processing at that x-coordinate critically determines correctness. If a building starts and another ends at the same x, processing the end before the start would temporarily show the ground height between them and generate a spurious key point for a dip that does not exist in the actual skyline. The rule is: always process start events before end events at the same x.

Among multiple start events at the same x, process taller buildings first. This ensures the heap top reflects the tallest new building immediately and avoids recording an intermediate lower height. Among multiple end events at the same x, process shorter buildings first (or equivalently, process them all before querying the heap, since lazy deletion defers the actual removal to the heap top query). The critical check only happens once per x-group after all events at that x are processed.

A subtle edge case is a building of zero height or a point building where left equals right. Such buildings contribute no visible area to the skyline, so their events cancel exactly at the same x-coordinate and produce no key point as long as start-before-end ordering is maintained. Another edge case is buildings that perfectly share a boundary: building A ends at x=5 and building B starts at x=5. If A is taller than B, the skyline at x=5 transitions from A's height to B's height with a single key point.

Python's heapq module implements a min-heap with no built-in support for arbitrary element removal. To remove a specific height when a building ends, the standard technique is lazy deletion: instead of removing the height immediately, record it in a "to-remove" multiset (a Counter or dict). When querying the heap top, pop elements from the heap until the top is not in the to-remove set (or its to-remove count is zero). This amortizes removal work across future queries.

Lazy deletion is correct because a height in the to-remove set has logically been removed even if it still sits in the heap. The heap top represents the current maximum only when it is not in the to-remove set. Each element is pushed at most once and popped at most once, so the total heap operations across all events are O(n), and each operation is O(log n), preserving the overall O(n log n) bound despite the deferred removal.

Java offers a cleaner alternative: TreeMap<Integer, Integer> where keys are heights and values are counts. Adding a building increments count at its height; removing a building decrements count and removes the key if count reaches zero. The current maximum is simply treeMap.lastKey(), which is O(log n). This avoids lazy deletion entirely and makes the implementation more readable, at the cost of slightly higher constant factors due to TreeMap's balanced BST overhead compared to a heap.

In Python, the solution builds an events list with (x, -h) for starts and (x, h) for ends, sorts it, and iterates with a heap and Counter. A negated min-heap simulates a max-heap: push -h for each start. For lazy deletion, push -h into to_remove for each end. After processing each group of same-x events, clean the heap top. Emit a key point when -heap[0] != prev_max. The total code is around 20 lines. Time is O(n log n); space is O(n) for the heap, events list, and to_remove counter.

In Java, the cleanest approach uses a TreeMap<Integer, Integer> for active heights. Build a list of int[] events where [x, -h] means start and [x, h] means end. Sort with Arrays.sort using a lambda: compare by x first, then by height (so negative heights come first). Process each event: if height < 0, add -height to treemap; else decrement and possibly remove height from treemap. After each event, check if treemap.lastKey() changed. Emit [x, newMax] when it does. Java's TreeMap handles all tie-breaking and removal cleanly without lazy deletion.

The most subtle correctness point in both implementations is the interaction between sorting and grouping. Sorting ensures events at the same x are processed in the correct order, but the height-change check must happen after all events at a given x are processed — not after each individual event. In the Java TreeMap approach, check after each event whether the current max differs from the previous x's max, and only emit if x has changed or all events at x are processed. Python implementations often process all same-x events in a batch using itertools.groupby.

Meeting Rooms II (LeetCode 253) applies the same event-driven sweep idea: create start and end events for each interval, sweep left to right, and track the current count of overlapping intervals with a counter rather than a max-heap. The minimum number of conference rooms equals the maximum overlap count seen during the sweep. Understanding the skyline problem deepens intuition for why the sweep approach generalizes across interval and geometry problems.

Merge Intervals (LeetCode 56) and Insert Interval (LeetCode 57) are simpler members of the sweep family that operate on sorted intervals without needing a heap. Count Smaller After Self (LeetCode 315) uses a different data structure (merge sort or BIT) but shares the event-driven, process-in-sorted-order philosophy. The skyline problem sits at the harder end of the sweep line family because it combines coordinate-based event sorting, heap-based maximum tracking, and careful tie-breaking at shared boundaries.

The event-driven algorithm family — skyline, meeting rooms, employee free time, rectangle area union — all share the same blueprint: transform the input into events at critical points, sort events, maintain a state data structure, and emit results when state changes. Mastering this blueprint with the skyline problem, which requires the full suite of techniques, gives a strong foundation for all other event-driven problems at the hard difficulty level.