Hard

The Skyline Problem

LAB

Given buildings [left,right,height], return the skyline key points.

EXAMPLES

Example 1

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

FUNCTION SHAPE

buildings: intMatrix→intMatrix

SOLUTION NOTE

This is not really a 'pure' sweep line problem as we saw above. But the idea of creating these events, sorting them, and iterating over them can be considered 'sweep line' as well.

Key insight: We use a max heap/sorted list to efficiently track the tallest building at each point. The skyline only changes when the maximum height changes, so we only add points at those positions.

We need to prioritize larger heights first in starts, because we could have a higher new start interval and a closing lower height at that exact same x position.

Reveal reference solution +

pythonREFERENCE

from sortedcontainers import SortedList

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        # Create special events: (position, height, type)
        # Type: 0 for start, 1 for end
        events = []
        for left, right, height in buildings:
            # Start event: negative height to prioritize starts over ends at same position
            events.append((left, -height, 0))
            # End event: positive height
            events.append((right, height, 1))

        # Sort events by position, then by type (start before end)
        events.sort()

        # Max heap to track current heights
        heights = SortedList([0])  # Start with ground level
        result = []
        prev_max_height = 0

        for pos, h, event_type in events:
            if event_type == 0:
                # Start event, add height
                heights.add(-h)
            else:
                # End event, remove the height
                heights.remove(h)

            curr_max_height = heights[-1]

            # If the max height changed, add a skyline point
            if curr_max_height != prev_max_height:
                result.append([pos, curr_max_height])
                prev_max_height = curr_max_height

        return result

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗