Skip to main content

218 - The Skyline Problem

Difficulty: Hard | Pattern: Sweep Line + Sorted Container | Company tags: Microsoft, Google, LinkedIn

Problem Statement​

A city's skyline is the outer contour of the silhouette formed by all the buildings collectively when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

Each building is given as [lefti, righti, heighti]. The skyline is a list of "key points" in the format [[x1,y1],[x2,y2],...] representing the boundary.

Example:

Input: buildings = [[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]]

Approach: Sweep Line + Max-Heap — O(n² worst, O(n log n) typical)​

Key insight: Process events at each building's left edge (start, +height) and right edge (end, -height). Maintain a max-heap of active heights. When the max height changes, record a key point.

import heapq
from collections import defaultdict

def getSkyline(buildings: list[list[int]]) -> list[list[int]]:
    events = []
    for l, r, h in buildings:
        events.append((l, -h, r))  # start: negative height = higher priority
        events.append((r, 0, 0))   # end
    
    events.sort()
    
    result = []
    # Max-heap (negate heights): (neg_height, end_x)
    heap = [(0, float('inf'))]
    
    for x, neg_h, end in events:
        if neg_h != 0:
            heapq.heappush(heap, (neg_h, end))
        
        # Remove expired buildings from top
        while heap[0][1] <= x:
            heapq.heappop(heap)
        
        cur_max = -heap[0][0]
        if result and result[-1][1] == cur_max:
            continue
        result.append([x, cur_max])
    
    return result

Algorithm Flow​

Dry Run​

buildings = [[2,9,10],[3,7,15]]

Events sorted: (2,-10,9), (3,-15,7), (7,0,0), (9,0,0)

xheap (neg_h, end)max_hresult
2[(0,inf),(-10,9)]10[[2,10]]
3[(0,inf),(-10,9),(-15,7)]15[[2,10],[3,15]]
7remove (end=7 lte 7) → [(-10,9),(0,inf)]10[[2,10],[3,15],[7,10]]
9remove (end=9 lte 9) → [(0,inf)]0[[2,10],[3,15],[7,10],[9,0]]

Complexity​

  • Time: O(n² worst case) due to heap removals; O(n log n) with lazy deletion
  • Space: O(n)

Key Terms​

TermDefinition in this problem's context
Sweep lineA conceptual vertical line moving left to right across x-coordinates, processing building start/end events in sorted order.
Event encodingRepresenting a building as two events — (left, -height) for start and (right, 0) for end — so sorting naturally processes starts before ends at the same x.
Max-heapA priority queue of currently "active" building heights; the top always reflects the tallest building overlapping the current x position.
Lazy deletionInstead of removing an expired building from the heap immediately when it ends, it is popped only when it reaches the top, avoiding costly mid-heap removal.
Key pointAn (x, height) coordinate recorded only when the current maximum height changes, forming the final skyline contour.

FAQ​

  1. Why use a max-heap instead of just tracking the tallest building with a variable? Because multiple buildings can be active at once with overlapping ranges, and removing the tallest one requires knowing the next tallest — a heap keeps this ordering efficient across insertions and removals.

  2. Why is the end event given height 0 while the start event stores -height? Storing -height makes Python's min-heap sort behave like a max-heap. Using 0 for end events ensures that when a building starts and another ends at the same x, the start (higher priority, more negative) is processed first, preventing an incorrect dip in the skyline.

  3. Can this be solved without a heap? Yes, using a sorted multiset (e.g., SortedList in Python or a TreeMap in Java) to track active heights with O(log n) insert/remove, giving true O(n log n) instead of the heap's worst-case O(n²) due to lazy deletion.

  4. What's the purpose of the sentinel (0, float('inf')) in the heap? It guarantees the heap is never empty and represents "ground level" (height 0), so when all buildings have ended, the max height correctly resolves back to 0.

  5. What's a common follow-up interviewers ask? "Can you produce the skyline using a divide-and-conquer merge approach instead?" — split buildings into halves, compute skylines recursively, then merge two skylines similarly to merge sort, which is O(n log n) guaranteed without heap deletion issues.

Quick Revision​

  • Pattern: sweep line over sorted events + max-heap of active heights.
  • Represent each building as a start event (l, -h) and end event (r, 0).
  • Sort all events by x; ties resolve naturally because starts have negative height (sort before 0).
  • Maintain a max-heap of (neg_height, end_x), seeded with a sentinel (0, inf).
  • At each event x, push new building's height if it's a start.
  • Pop from heap while its top building's end_x has already passed (lazy deletion).
  • Current max height = negative of heap's top value.
  • Record [x, cur_max] only when it differs from the last recorded height — this avoids duplicate/flat points.
  • Time: O(n²) worst case from heap operations; O(n log n) achievable with a sorted-multiset or divide-and-conquer approach.
  • Space: O(n) for events and heap.
  • 1229-MeetingScheduler — interval overlap processed via sorting/two pointers.
  • 729-MyCalendarI and 732-MyCalendarIII — sweep-line / interval counting with ordered structures.
  • 215-KthLargestElementInAnArray — shares the heap-based "track the max/kth element dynamically" pattern.
  • LeetCode 253 Meeting Rooms II — classic sweep-line + min-heap problem with a similar event-processing structure (not present in this directory).