LeetCode 218: The Skyline Problem Solution in Python Explained

Problem Statement

In LeetCode 218: The Skyline Problem, you’re given:

• buildings: A list of [left, right, height] triples, where left is the x-coordinate of the left edge, right is the right edge, and height is the building’s height.
• Your task is to return a list of [x, h] pairs representing the skyline—points where the height changes, forming the outline of all buildings combined.

The skyline traces the maximum height at each x-coordinate. This differs from duplicate detection in LeetCode 217: Contains Duplicate, focusing instead on geometric sweep line techniques.

Constraints

• 1 ≤ buildings.length ≤ 10⁴.
• 0 ≤ left < right ≤ 2³¹ - 1.
• 1 ≤ height ≤ 2³¹ - 1.
• buildings is sorted by left in non-decreasing order.

Examples

Let’s see some cases:

Copy codeInput: 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]]
Explanation:
<ul>
<li>[2,10]: Building [2,9,10] starts.</li>
<li>[3,15]: [3,7,15] increases height.</li>
<li>[7,12]: [3,7,15] ends, drops to 12.</li>
<li>[12,0]: [5,12,12] ends, no height left.</li>
<li>[15,10]: [15,20,10] starts.</li>
<li>[20,8]: [15,20,10] ends, [19,24,8] remains.</li>
<li>[24,0]: [19,24,8] ends.</li>
</ul>

Copy codeInput: buildings = [[1,2,1],[1,2,2],[1,2,3]]
Output: [[1,3],[2,0]]
Explanation: Three overlapping buildings, max height 3, all end at 2.

These examples show we’re tracking height changes across x-coordinates.

Understanding the Problem

How do we solve LeetCode 218: The Skyline Problem in Python? For [[2,9,10],[3,7,15],[5,12,12]], the skyline starts at height 10, jumps to 15, drops to 12, then to 0 as buildings end. A naive approach might check every x-coordinate (O(n²)), but a sweep line processes events efficiently. This isn’t a combination problem like LeetCode 216: Combination Sum III; it’s about managing building edges. We’ll use: 1. Sweep Line with Heap: O(n log n) time, O(n) space—our best solution. 2. Sweep Line with Sorted Events: O(n log n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Sweep Line with Heap Approach

Explanation

The Sweep Line with Heap approach uses a max heap to track active heights:

• Convert buildings into events: [x, height] for start (positive height) and end (negative height).
• Sort events by x-coordinate (tiebreak: starts before ends, higher starts first).
• Use a max heap to maintain active building heights.
• Sweep through events:
• Add start heights to heap.
• Remove end heights from heap.
• Record height changes in the result.

This runs in O(n log n) time (sorting + heap operations) and O(n) space (heap and result), making it efficient and robust—our best solution.

For [[2,9,10],[3,7,15]], it tracks height transitions accurately.

Step-by-Step Example

Example 1: buildings = [[2,9,10],[3,7,15],[5,12,12]]

Goal: Return [[2,10],[3,15],[7,12],[12,0]].

• Step 1: Create events.
• [2,10], [9,-10], [3,15], [7,-15], [5,12], [12,-12].
• Step 2: Sort events.
• [2,10], [3,15], [5,12], [7,-15], [9,-10], [12,-12].
• Step 3: Sweep with heap.
• heap = [], result = [], prev_height = 0.
• [2,10]: Add 10, heap=[10], max=10, result=[[2,10]].
• [3,15]: Add 15, heap=[15,10], max=15, result=[[2,10],[3,15]].
• [5,12]: Add 12, heap=[15,12,10], max=15, no change.
• [7,-15]: Remove 15, heap=[12,10], max=12, result=[[2,10],[3,15],[7,12]].
• [9,-10]: Remove 10, heap=[12], max=12, no change.
• [12,-12]: Remove 12, heap=[], max=0, result=[[2,10],[3,15],[7,12],[12,0]].
• Output: [[2,10],[3,15],[7,12],[12,0]].

Example 2: buildings = [[1,2,1],[1,2,2]]

Goal: Return [[1,2],[2,0]].

• Step 1: Events: [1,1], [1,2], [2,-1], [2,-2].
• Step 2: Sort: [1,2], [1,1], [2,-2], [2,-1].
• Step 3:
• [1,2]: heap=[2], result=[[1,2]].
• [1,1]: heap=[2,1], max=2, no change.
• [2,-2]: Remove 2, heap=[1], max=1, result=[[1,2],[2,1]].
• [2,-1]: Remove 1, heap=[], max=0, result=[[1,2],[2,0]].
• Output: [[1,2],[2,0]].

How the Code Works (Sweep Line with Heap) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codeimport heapq

def getSkyline(buildings: list[list[int]]) -> list[list[int]]:
    # Line 1: Create and sort events
    events = []
    # List of [x, height] events (e.g., [])
    for left, right, height in buildings:
        # Iterate buildings (e.g., [2,9,10])
        events.append((left, height))   # Start event
        events.append((right, -height)) # End event (negative)
    events.sort(key=lambda x: (x[0], -x[1]))
    # Sort by x, then height descending (e.g., [(2,10), (3,15)])

    # Line 2: Initialize heap and result
    heap = [0]  # Max heap (negative values), 0 as base
    # Active heights (e.g., [0])
    heapq.heapify(heap)
    # Make it a heap
    result = []
    # Skyline points (e.g., [])
    prev_height = 0
    # Previous max height (e.g., 0)

    # Line 3: Process events
    for x, h in events:
        # Sweep through events (e.g., (2,10))
        if h > 0:
            # Start event (e.g., h=10)
            heapq.heappush(heap, -h)
            # Add height (negative for max heap, e.g., -10)
        else:
            # End event (e.g., h=-15)
            heap.remove(-h)
            # Remove height (e.g., 15)
            heapq.heapify(heap)
            # Re-heapify (e.g., [12,10])

        curr_height = -heap[0] if heap else 0
        # Current max height (e.g., 10)
        if curr_height != prev_height:
            # Height change (e.g., 0 to 10)
            result.append([x, curr_height])
            # Add point (e.g., [2,10])
            prev_height = curr_height
            # Update previous (e.g., 10)

    # Line 4: Return skyline
    return result
    # Final skyline (e.g., [[2,10],[3,15],[7,12],[12,0]])

This solution efficiently tracks height changes with a heap.

Alternative: Sweep Line with Sorted Events Approach

Explanation

The Sweep Line with Sorted Events approach uses a sorted list:

• Create start and end events, sort by x-coordinate.
• Maintain a sorted list of active heights (e.g., with SortedList).
• Process events, updating heights and recording changes.

It’s O(n log n) time (sorting + height updates) and O(n) space, avoiding heap removal overhead.

Step-by-Step Example

For [[2,9,10],[3,7,15]]:

• Events: [(2,10,T), (3,15,T), (7,15,F), (9,10,F)].
• Sweep:
• (2,10,T): Heights=[10], result=[[2,10]].
• (3,15,T): Heights=[10,15], result=[[2,10],[3,15]].
• (7,15,F): Heights=[10], result=[[2,10],[3,15],[7,10]].
• (9,10,F): Heights=[], result=[[2,10],[3,15],[7,10],[9,0]].
• Output: [[2,10],[3,15],[7,10],[9,0]].

How the Code Works (Sorted Events)

Copy codefrom sortedcontainers import SortedList

def getSkylineSorted(buildings: list[list[int]]) -> list[list[int]]:
    events = []
    for left, right, height in buildings:
        events.append((left, height, True))
        events.append((right, height, False))
    events.sort()

    heights = SortedList([0])
    result = []
    prev_height = 0

    for x, h, is_start in events:
        if is_start:
            heights.add(h)
        else:
            heights.remove(h)

        curr_height = heights[-1]
        if curr_height != prev_height:
            result.append([x, curr_height])
            prev_height = curr_height

    return result

Complexity

• Sweep Line with Heap:
• Time: O(n log n) – sorting + heap operations.
• Space: O(n) – heap and result.
• Sweep Line with Sorted Events:
• Time: O(n log n) – sorting + sorted list updates.
• Space: O(n) – event list and heights.

Efficiency Notes

Sweep Line with Heap is our best solution for its balance of speed and standard library use (heapq). Sorted Events is elegant but requires an external library or more complex implementation.

Key Insights

• Sweep Line: Process events in order.
• Heap: Tracks max height.
• Skyline: Height transitions.

Additional Example

For [[1,3,2],[2,4,3]]:

• Heap: [[1,2],[2,3],[3,3],[4,0]].

Edge Cases

• Single building: Works fine.
• Overlapping: Handled by max height.
• Empty (not per constraints): [].

Both solutions manage these well.

Final Thoughts

LeetCode 218: The Skyline Problem in Python is a captivating blend of sweep line and data structures. Sweep Line with Heap offers efficiency and clarity, while Sorted Events provides an alternative twist. Want more? Try LeetCode 56: Merge Intervals or LeetCode 253: Meeting Rooms II. Test your skills—Solve LeetCode 218 on LeetCode with [[2,9,10],[3,7,15]] (expecting [[2,10],[3,15],[7,10],[9,0]])—draw that skyline today!