LeetCode 218 - The Skyline Problem

LeetCode Problem 218

Difficulty: 🔴 Hard
Topics: Array, Divide and Conquer, Binary Indexed Tree, Segment Tree, Sweep Line, Sorting, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The Skyline Problem asks us to compute the visible outer contour formed by a collection of rectangular buildings when viewed from far away. Each building is represented by three integers: a left x-coordinate, a right x-coordinate, and a height. The buildings sit on the ground, which is considered height 0.

The output is not the full shape itself, but a compact representation of the skyline using "key points." A key point is a position where the skyline height changes. For example, if the skyline rises from height 10 to height 15 at x = 3, then [3, 15] is a key point. Similarly, when a building ends and the skyline drops, that drop also creates a key point.

The challenge is that buildings can overlap in many ways:

• A taller building can completely hide a shorter one
• Multiple buildings can start or end at the same x-coordinate
• Buildings may partially overlap
• Several adjacent buildings may share the same height

The final skyline must not contain redundant horizontal segments. If the skyline stays at the same height across multiple intervals, it should appear as a single continuous segment.

The input constraints are important:

• Up to 10^4 buildings
• Coordinates and heights can be as large as 2^31 - 1
• Buildings are already sorted by starting coordinate

These constraints immediately rule out naive geometric simulation across every x-coordinate. The coordinate range is enormous, so we cannot build a dense array representing every possible x-position.

Several edge cases are especially important:

• Buildings that start and end at the same positions
• Multiple buildings with identical heights
• Buildings fully contained inside taller buildings
• Adjacent buildings of equal height, which should merge into one segment
• Events occurring at the same x-coordinate, where processing order matters

A correct solution must carefully manage overlapping heights and ensure skyline changes are emitted only when the visible maximum height truly changes.

Approaches

Brute Force Approach

A straightforward approach is to simulate the height at every x-coordinate. We could determine the maximum height among all buildings covering each coordinate, then compress the resulting height profile into skyline key points.

Conceptually, this works because the skyline at any position is simply the tallest active building at that point.

However, this approach becomes impractical because coordinates can be extremely large, up to 2^31 - 1. Even if we compressed coordinates, checking every building against every interval would still be expensive.

Another brute-force variation is:

1. Collect all unique x-coordinates from building boundaries
2. For every interval between consecutive x-values, determine the maximum building height
3. Generate skyline transitions from those heights

This improves the coordinate issue, but still requires scanning many buildings repeatedly.

The brute-force approach is correct because it explicitly computes the visible height everywhere, but it is too slow for the problem constraints.

Optimal Approach, Sweep Line with Max Heap

The key observation is that the skyline only changes at building boundaries.

Between two consecutive event points, the skyline height remains constant. Therefore, instead of examining every x-coordinate, we only need to process building start and end events.

This leads naturally to a sweep line algorithm:

• Sweep from left to right across the x-axis
• Add buildings when we encounter their left edge
• Remove buildings when we encounter their right edge
• Maintain the tallest currently active building

To efficiently retrieve the tallest active building at any moment, we use a max heap.

The heap stores active buildings ordered by height. As the sweep line moves:

• New buildings are inserted
• Expired buildings are removed lazily
• The heap top always represents the visible skyline height

Whenever the maximum height changes, we record a new skyline key point.

This approach is efficient because every building is inserted and removed at most once, and heap operations are logarithmic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scans buildings across intervals
Optimal	O(n log n)	O(n)	Sweep line with max heap for active buildings

Algorithm Walkthrough

Step 1: Convert buildings into events

For every building [left, right, height], create two events:

• A start event at left
• An end event at right

We process these events in sorted x-order because the skyline changes only at building boundaries.

For example:

[2,9,10]

becomes:

start at x=2 with height=10
end at x=9

Step 2: Sort events carefully

The ordering at the same x-coordinate is extremely important.

We represent:

• Start events with negative heights
• End events with positive heights

This creates the correct sorting behavior automatically:

• Taller starts processed before shorter starts
• Starts processed before ends
• Shorter ends processed before taller ends

This prevents temporary incorrect skyline transitions.

Step 3: Maintain active buildings with a max heap

The heap stores currently active buildings.

Each heap entry contains:

(-height, right_edge)

We use negative heights because Python's heapq is a min heap, so negating values simulates a max heap.

The heap top always represents the tallest visible building.

Step 4: Add buildings on start events

When encountering a start event:

• Push the building into the heap
• The building becomes active immediately

Step 5: Remove expired buildings lazily

When the sweep line reaches x-coordinate x, some buildings may already have ended.

Instead of removing them immediately when their end event occurs, we remove them lazily:

• While the heap top has right_edge <= x
• Pop it from the heap

This works because only the tallest active building matters at any moment.

Lazy deletion avoids expensive arbitrary heap removals.

Step 6: Detect skyline changes

After processing events at position x:

• The current skyline height is the heap top
• If this height differs from the previous height
• Append a new key point

This ensures we only record actual skyline transitions.

Step 7: Continue until all events are processed

Once all events are processed:

• The heap eventually becomes empty
• The skyline returns to height 0
• The final termination point is added automatically

Why it works

The algorithm maintains the invariant that the heap always contains all currently active buildings, and the heap top always represents the tallest visible building at the current sweep position.

Since skyline changes can only occur at building boundaries, processing events in sorted order guarantees that every possible height transition is examined exactly once. Whenever the maximum active height changes, the skyline contour must also change, so recording those transitions produces the correct skyline.

Python Solution

from typing import List
import heapq

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        events = []

        for left, right, height in buildings:
            events.append((left, -height, right))
            events.append((right, 0, 0))

        events.sort()

        result = []

        # (negative_height, right_edge)
        max_heap = [(0, float('inf'))]

        previous_height = 0

        for x, neg_height, right in events:
            # Remove expired buildings
            while max_heap and max_heap[0][1] <= x:
                heapq.heappop(max_heap)

            # Add new building
            if neg_height != 0:
                heapq.heappush(max_heap, (neg_height, right))

            current_height = -max_heap[0][0]

            # Skyline changed
            if current_height != previous_height:
                result.append([x, current_height])
                previous_height = current_height

        return result

The implementation begins by converting every building into two sweep-line events. Start events store negative heights so that sorting naturally prioritizes taller buildings first at the same x-coordinate.

After sorting all events, the algorithm sweeps from left to right while maintaining a max heap of active buildings. Each heap entry contains both the building height and its ending coordinate.

Before processing a new position, expired buildings are removed from the heap. This lazy deletion strategy is efficient because we only care about the tallest active building, which always appears at the heap top.

Whenever a start event is encountered, the building is inserted into the heap. The current skyline height is then determined from the heap top.

If the visible height differs from the previous height, a skyline transition has occurred, so a new key point is added to the result.

The heap is initialized with a dummy ground-level building of height 0. This avoids empty-heap edge cases and naturally produces the final drop back to ground level.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

type Event struct {
	x      int
	height int
	right  int
}

type MaxHeap [][2]int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i][0] < h[j][0]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func getSkyline(buildings [][]int) [][]int {
	events := []Event{}

	for _, b := range buildings {
		left, right, height := b[0], b[1], b[2]

		events = append(events, Event{
			x:      left,
			height: -height,
			right:  right,
		})

		events = append(events, Event{
			x:      right,
			height: 0,
			right:  0,
		})
	}

	sort.Slice(events, func(i, j int) bool {
		if events[i].x != events[j].x {
			return events[i].x < events[j].x
		}
		return events[i].height < events[j].height
	})

	result := [][]int{}

	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)

	heap.Push(maxHeap, [2]int{0, int(^uint(0) >> 1)})

	prevHeight := 0

	for _, event := range events {
		x := event.x

		for maxHeap.Len() > 0 && (*maxHeap)[0][1] <= x {
			heap.Pop(maxHeap)
		}

		if event.height != 0 {
			heap.Push(maxHeap, [2]int{event.height, event.right})
		}

		currentHeight := -(*maxHeap)[0][0]

		if currentHeight != prevHeight {
			result = append(result, []int{x, currentHeight})
			prevHeight = currentHeight
		}
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version, but Go requires explicit heap interface implementation using container/heap.

Since Go does not provide a built-in max heap, negative heights are again used to simulate one. Heap entries are stored as fixed-size arrays [2]int, where the values represent:

[negative_height, right_edge]

Go slices naturally handle dynamic resizing for both events and result arrays. Integer overflow is not a concern because Go's int type comfortably handles the problem constraints on modern 64-bit platforms.

Worked Examples

Example 1

Input:

[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]

Sorted events:

x	height	right
2	-10	9
3	-15	7
5	-12	12
7	0	0
9	0	0
12	0	0
15	-10	20
19	-8	24
20	0	0
24	0	0

Processing steps:

x	Action	Heap Top	Skyline
2	Add height 10	10	[2,10]
3	Add height 15	15	[3,15]
5	Add height 12	15	unchanged
7	Remove expired 15	12	[7,12]
9	Remove expired 10	12	unchanged
12	Remove expired 12	0	[12,0]
15	Add height 10	10	[15,10]
19	Add height 8	10	unchanged
20	Remove expired 10	8	[20,8]
24	Remove expired 8	0	[24,0]

Final result:

[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Example 2

Input:

[[0,2,3],[2,5,3]]

Sorted events:

x	height	right
0	-3	2
2	-3	5
2	0	0
5	0	0

Processing:

x	Action	Heap Top	Skyline
0	Add first building	3	[0,3]
2	Add second building	3	unchanged
2	First building expires	3	unchanged
5	Remove second building	0	[5,0]

Final result:

[[0,3],[5,0]]

The adjacent equal-height buildings merge correctly into one continuous segment.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting events and heap operations
Space	O(n)	Event list and active heap storage

The algorithm creates 2n events and sorts them, which requires O(n log n) time. Each building is inserted into and removed from the heap at most once, and every heap operation costs O(log n).

The heap may contain up to n active buildings simultaneously, and the event list also stores 2n elements, so the overall space complexity is linear.

Test Cases

from typing import List

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        import heapq

        events = []

        for left, right, height in buildings:
            events.append((left, -height, right))
            events.append((right, 0, 0))

        events.sort()

        result = []
        max_heap = [(0, float('inf'))]

        prev_height = 0

        for x, neg_height, right in events:
            while max_heap[0][1] <= x:
                heapq.heappop(max_heap)

            if neg_height != 0:
                heapq.heappush(max_heap, (neg_height, right))

            current_height = -max_heap[0][0]

            if current_height != prev_height:
                result.append([x, current_height])
                prev_height = current_height

        return result

solution = Solution()

assert solution.getSkyline(
    [[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]
]  # Official example with overlaps

assert solution.getSkyline(
    [[0,2,3],[2,5,3]]
) == [
    [0,3],[5,0]
]  # Adjacent buildings with same height merge

assert solution.getSkyline(
    [[1,5,10]]
) == [
    [1,10],[5,0]
]  # Single building

assert solution.getSkyline(
    [[1,10,5],[2,3,8]]
) == [
    [1,5],[2,8],[3,5],[10,0]
]  # Nested taller building

assert solution.getSkyline(
    [[1,5,5],[1,5,10]]
) == [
    [1,10],[5,0]
]  # Same boundaries, different heights

assert solution.getSkyline(
    [[1,3,4],[3,6,4]]
) == [
    [1,4],[6,0]
]  # Continuous equal-height skyline

assert solution.getSkyline(
    [[1,2,1],[1,2,2],[1,2,3]]
) == [
    [1,3],[2,0]
]  # Multiple starts at same x-coordinate

assert solution.getSkyline(
    [[1,5,11],[2,6,7],[3,9,13],[12,16,7]]
) == [
    [1,11],[3,13],[9,0],[12,7],[16,0]
]  # Mixed overlap patterns

assert solution.getSkyline(
    [[0,2147483647,2147483647]]
) == [
    [0,2147483647],[2147483647,0]
]  # Maximum coordinate and height values

Test	Why
Official overlapping example	Validates core sweep-line logic
Adjacent equal-height buildings	Ensures redundant segments merge
Single building	Simplest valid input
Nested taller building	Tests temporary skyline rise
Same boundaries, different heights	Ensures tallest building dominates
Continuous equal-height skyline	Prevents duplicate heights
Multiple starts at same x	Verifies event ordering correctness
Mixed overlap patterns	Stress test for heap updates
Maximum integer values	Validates large coordinate handling

Edge Cases

One important edge case occurs when multiple buildings start at the same x-coordinate. If shorter buildings are processed before taller ones, the algorithm may incorrectly generate intermediate skyline points that should never appear. Sorting start events by descending height avoids this problem. Using negative heights naturally enforces the correct ordering.

Another tricky case is adjacent buildings with the same height. Consider:

[[0,2,3],[2,5,3]]

A naive implementation might output:

[[0,3],[2,3],[5,0]]

which contains redundant consecutive heights. The implementation prevents this by only appending a skyline point when the visible height actually changes.

A third important edge case involves buildings completely hidden behind taller buildings. For example:

[[1,10,10],[2,5,5]]

The smaller building should never appear in the skyline. The heap structure handles this naturally because the tallest active building always determines visibility. Even though the smaller building exists in the heap, it never becomes the maximum height, so no skyline transition is produced.

Another subtle issue arises when buildings end at the same x-coordinate where others begin. Correct event ordering is critical here. Start events must be processed before end events at the same position so the skyline does not temporarily drop to an incorrect lower height. The event sorting strategy ensures this behavior automatically.