LeetCode 218: The Skyline Problem

Problem Restatement

We are given a list of buildings.

Each building is represented as:

[left, right, height]

Meaning:

We need to return the skyline formed by these buildings.

The skyline is represented as a list of key points:

[x, height]

Each key point means:

at x-coordinate x, the skyline height changes to height

The last point must end with height 0.

The official statement defines the skyline as the outer contour formed by overlapping rectangular buildings and asks for all key points of that contour. (leetcode.com)

Input and Output

Example function shape:

def getSkyline(buildings: list[list[int]]) -> list[list[int]]:
    ...

Examples

Example 1:

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],
]

Example 2:

buildings = [[0,2,3],[2,5,3]]

Output:

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

The height remains 3 continuously, so no extra point appears at x = 2.

Understanding the Skyline

Imagine viewing buildings from very far away.

Only the highest visible outline matters.

Example:

[2,9,10]

creates:

height 10 from x = 2 to x = 9

Now add:

[3,7,15]

This taller building hides the previous one between 3 and 7.

So the skyline becomes:

x = 2 -> height 10
x = 3 -> height 15
x = 7 -> height 10
x = 9 -> height 0

The skyline only changes when the maximum active building height changes.

Key Insight

We process the plane from left to right.

At each x-coordinate:

• some buildings start
• some buildings end

We need to know:

What is the tallest active building right now?

That immediately suggests:

Sweep Line Events

Each building creates two events:

For:

[2,9,10]

we create:

(2, start, 10)
(9, end, 10)

As we sweep through x-coordinates:

• start events add heights
• end events remove heights

The skyline changes whenever the current maximum height changes.

Heap Challenge

Python only has a min-heap.

To simulate a max-heap, store negative heights.

Example:

heap = [-15, -10, -12]

The smallest negative value corresponds to the tallest building.

Another Challenge: Removing Buildings

Suppose a building ends.

Removing arbitrary values from a heap efficiently is difficult.

Instead, store:

(-height, right)

At each x-coordinate:

1. Remove buildings whose right <= current_x.
2. The heap top then automatically gives the tallest active building.

This is called lazy deletion.

Event Representation

For each building:

[left, right, height]

create a start event:

(left, -height, right)

Why negative height?

Because sorting events should process taller starting buildings first at the same x-coordinate.

End events are handled lazily through heap expiration.

Algorithm

1. Convert buildings into start events.
2. Sort events by x-coordinate.
3. Maintain a max-heap of active buildings.
4. Sweep through events:
   • remove expired buildings
   • add newly starting buildings
   • compute current maximum height
5. Whenever the height changes, add a skyline key point.

Walkthrough

Use:

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

Events:

(2, -10, 9)
(3, -15, 7)

Initial heap:

[(0, inf)]

This represents ground level.

At x = 2

Add building height 10.

Heap top:

10

Skyline changes:

[2,10]

At x = 3

Add building height 15.

Heap top:

15

Skyline changes:

[3,15]

At x = 7

Building 15 expires.

Heap top becomes:

10

Skyline changes:

[7,10]

At x = 9

Building 10 expires.

Heap top becomes:

0

Skyline changes:

[9,0]

Final skyline:

[[2,10],[3,15],[7,10],[9,0]]

Why Event Ordering Matters

Suppose two buildings start at the same x-coordinate:

[2,9,10]
[2,7,15]

We must process height 15 first.

Otherwise the skyline might incorrectly produce:

[2,10]
[2,15]

instead of directly:

[2,15]

Using negative heights naturally sorts taller starts first.

Correctness

The sweep line processes all x-coordinates where the skyline can possibly change, namely building start positions and effective end positions.

The heap always contains exactly the active buildings whose intervals cover the current x-coordinate. Expired buildings are removed whenever their right endpoint is no longer greater than the current position.

The top of the heap therefore gives the maximum active height at the current x-coordinate.

The skyline changes exactly when this maximum height changes. The algorithm records a key point precisely in that situation.

If the maximum height stays the same, the visible skyline does not change, so no key point is added.

Thus every recorded point is necessary, and every actual skyline height change is recorded.

Therefore the algorithm returns exactly the correct skyline.

Complexity

Let:

n = number of buildings

Each building is inserted and removed from the heap at most once.

Implementation

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.sort()

        result = []

        heap = [(0, float("inf"))]

        prev_height = 0
        i = 0

        while i < len(events):
            current_x = events[i][0]

            while heap and heap[0][1] <= current_x:
                heapq.heappop(heap)

            while i < len(events) and events[i][0] == current_x:
                _, neg_height, right = events[i]
                heapq.heappush(heap, (neg_height, right))
                i += 1

            while heap and heap[0][1] <= current_x:
                heapq.heappop(heap)

            current_height = -heap[0][0]

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

        return result

Code Explanation

Create building start events:

events.append((left, -height, right))

Negative height makes taller buildings sort first.

Sort all events:

events.sort()

Initialize the heap with ground level:

heap = [(0, float("inf"))]

This prevents the heap from becoming empty.

Before processing the current x-coordinate, remove expired buildings:

while heap and heap[0][1] <= current_x:
    heapq.heappop(heap)

Process all events at the same x-coordinate:

while i < len(events) and events[i][0] == current_x:

Add buildings to the heap:

heapq.heappush(heap, (neg_height, right))

Current skyline height:

current_height = -heap[0][0]

If the skyline changed:

if current_height != prev_height:

record a new key point:

result.append([current_x, current_height])

Alternative Event-Based Solution

Another common solution explicitly creates both start and end events.

Example:

(left, -height)
(right, height)

Then:

• negative height means entering
• positive height means leaving

A multiset or counter structure is needed to remove heights correctly.

This version is elegant in languages with balanced trees, but Python requires more bookkeeping.

The lazy-deletion heap approach is usually simpler in Python.

Testing

def run_tests():
    s = Solution()

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

    assert s.getSkyline(buildings) == [
        [2,10],
        [3,15],
        [7,12],
        [12,0],
        [15,10],
        [20,8],
        [24,0],
    ]

    assert s.getSkyline([[0,2,3],[2,5,3]]) == [
        [0,3],
        [5,0],
    ]

    assert s.getSkyline([[1,2,1]]) == [
        [1,1],
        [2,0],
    ]

    assert s.getSkyline([[1,5,3],[1,5,5]]) == [
        [1,5],
        [5,0],
    ]

    print("all tests passed")

run_tests()