218. The Skyline Problem - Detailed Explanation

Problem Statement

You are given an array of buildings, where each building is represented by a triplet [left, right, height]:

• left: the x-coordinate of the left edge.
• right: the x-coordinate of the right edge.
• height: the height of the building.

Your goal is to output the skyline formed by these buildings as a list of key points. A key point is defined as [x, height], where:

• x is the x-coordinate where the height changes.
• height is the new height starting from that x-coordinate.

Important: The skyline should be a list of key points sorted by the x-coordinate, and it must represent the outer contour without redundant points.

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

Explanation:

• At x = 2, the first building starts with height 10 → add [2, 10].
• At x = 3, a taller building (height 15) starts → update to [3, 15].
• At x = 7, the building with height 15 ends; the next highest active building has height 12 → add [7, 12].
• At x = 12, the building with height 12 ends → the skyline drops to 0 → add [12, 0].
• At x = 15, a new building with height 10 starts → add [15, 10].
• At x = 20, the building with height 10 ends, but another building is still active with height 8 → add [20, 8].
• At x = 24, the final building ends → the skyline returns to 0 → add [24, 0].

Constraints

• The number of buildings can be large (up to several thousand).
• Building coordinates and heights are positive integers.
• Buildings may overlap with one another.

Hints

1. Sweep Line Concept:
   Think of moving a vertical line (sweep line) from left to right across the x-axis. At each critical x-coordinate (where a building starts or ends), update the current active buildings and check if the maximum height has changed.

2. Using a Priority Queue (Max-Heap):
   As you sweep through, maintain a data structure (like a max-heap) to quickly retrieve the current highest building among all buildings that overlap the current x position.

3. Event Processing:
   Convert each building into two events:

   • A start event at x = left with the building's height.
   • An end event at x = right with the building's height. Then, sort these events by x-coordinate (with careful handling of ties).

Approach Overview

There are two common approaches to solve this problem:

1. Sweep Line with Priority Queue (Max-Heap)

Idea:
Process all start and end events sorted by x-coordinate. Use a max-heap to store the heights of the active buildings. At each event:

• For a start event, add the building’s height to the heap.
• For an end event, remove the building’s height (or mark it for lazy removal).
• After processing an event, if the current maximum height (top of the heap) differs from the previous maximum height, record the x-coordinate and the new height as a key point.

Time Complexity: O(n log n) (for sorting and heap operations)
Space Complexity: O(n)

2. Divide and Conquer

Idea:
Divide the list of buildings into two halves, recursively compute the skyline for each half, and then merge the two skylines. The merging process is similar to merging two sorted lists while keeping track of the maximum height at each x-coordinate.

Time Complexity: O(n log n)
Space Complexity: O(n)

Detailed Explanation (Sweep Line with Priority Queue)

Step-by-Step Walkthrough

1. Event Creation:
   For each building [L, R, H], create:

   • A start event (L, -H) (using negative height so that start events come before end events when x is the same, and higher buildings come first).
   • An end event (R, H).

2. Sorting Events:
   Sort all events primarily by the x-coordinate. If two events have the same x:

   • Process start events before end events.
   • For start events, process the one with a higher height first.
   • For end events, process the one with a lower height first.

3. Processing Events with a Max-Heap:

   • Initialize a max-heap with a zero to represent the ground level.
   • Initialize a variable prevMax as 0.
   • Iterate over the sorted events:
     • If it is a start event, push its height (convert the negative value back to positive) into the heap.
     • If it is an end event, remove the corresponding height from the heap (using lazy removal if necessary).
     • Check the current maximum height from the heap.
     • If the maximum height has changed compared to prevMax, add a key point [x, current_max] and update prevMax.

4. Final Output:
   The list of key points recorded during the sweep forms the skyline.

Visual Example Using the Given Input

For the input:

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

• Events:

  (2, -10), (9, 10)
  (3, -15), (7, 15)
  (5, -12), (12, 12)
  (15, -10), (20, 10)
  (19, -8), (24, 8)
  

• Sorted Events:

  (2, -10), (3, -15), (5, -12), (7, 15), (9, 10), (12, 12), (15, -10), (19, -8), (20, 10), (24, 8)
  

• Processing:

  • At x = 2, add 10 → current max becomes 10 → key point [2, 10].
  • At x = 3, add 15 → current max becomes 15 → key point [3, 15].
  • At x = 5, add 12 → current max remains 15 → no key point.
  • At x = 7, remove 15 → current max becomes 12 → key point [7, 12].
  • At x = 9, remove 10 → current max remains 12 → no key point.
  • At x = 12, remove 12 → current max drops to 0 → key point [12, 0].
  • Continue similarly for x = 15, 19, 20, and 24.

• Resulting Skyline:

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

Code Implementation

Python Code