#218

Hard

auto_awesomeArray plus Divide and Conquer

LeetCode Problem Workspace

The Skyline Problem

The Skyline Problem requires calculating a city's silhouette using array manipulation and divide-and-conquer techniques efficiently.

array divide and conquer binary indexed tree segment tree line sweep

Problem Statement

Given a list of buildings represented as [left, right, height], generate the skyline formed by these buildings collectively. Each building is a perfect rectangle grounded on a flat surface at height 0, and buildings may overlap.

Return a list of key points [x, height] that represents the outer contour of the city skyline. Each key point indicates where the height changes, capturing the silhouette produced by the combined buildings when viewed from a distance.

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

Figure A shows the buildings of the input. Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2

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

Output: [[0,3],[5,0]]

Example details omitted.

Constraints

1 <= buildings.length <= 104
0 <= lefti < righti <= 231 - 1
1 <= heighti <= 231 - 1
buildings is sorted by lefti in non-decreasing order.

Solution Approach

Divide and Conquer Skyline Merge

Split the buildings array into two halves recursively until each segment contains one building. Convert each segment into a simple skyline and then merge pairs of skylines by comparing height changes point by point. This ensures an efficient O(n log n) merge without scanning the entire array repeatedly.

Priority Queue for Active Heights

Use a max-heap to track currently active building heights while sweeping from left to right across all building edges. Push building heights when entering a left edge and remove them at a right edge. Record key points whenever the maximum height changes to build the skyline incrementally.

Optimized Segment Tree or Binary Indexed Tree

For extremely large building arrays, a segment tree or binary indexed tree can maintain active heights and efficiently query maximum height over a range. This approach reduces redundant comparisons during merges, especially when handling dense clusters of overlapping buildings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) with divide-and-conquer merges; using heaps or segment trees may introduce O(n log n) overhead for insertions and deletions. Space complexity is O(n) for storing intermediate skylines or active heights.

What Interviewers Usually Probe

Expect candidates to identify divide-and-conquer as the core pattern.
Watch for incorrect merges when skylines overlap, which often signals misunderstanding of height transitions.
Candidates who directly sweep with a heap should explain why it preserves correct key points.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle consecutive buildings with the same height, causing redundant points.
Merging skylines without considering the maximum height at overlapping intervals.
Using naive O(n^2) comparisons instead of divide-and-conquer or heap optimization, leading to timeouts.

Follow-up variants

Compute skylines when buildings are represented as arbitrary polygons instead of rectangles.
Find only the maximum height at any point rather than the full skyline contour.
Return a simplified skyline with merged horizontal segments of equal height.

FAQ

What is the primary pattern used in The Skyline Problem?

The core pattern is array plus divide-and-conquer, merging smaller skyline segments recursively.

Can a heap solve this problem?

Yes, using a max-heap to track active building heights while sweeping the x-axis produces the skyline efficiently.

What are common mistakes when merging skylines?

Ignoring overlapping intervals or failing to update the maximum height when consecutive buildings overlap often produces incorrect key points.

How does a segment tree help in The Skyline Problem?

A segment tree allows efficient range maximum queries, reducing redundant comparisons when merging large numbers of overlapping buildings.

What is the space complexity of this approach?

Space complexity is O(n) to store intermediate skyline points and active heights during merges or heap operations.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

from queue import PriorityQueue


class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        skys, lines, pq = [], [], PriorityQueue()
        for build in buildings:
            lines.extend([build[0], build[1]])
        lines.sort()
        city, n = 0, len(buildings)
        for line in lines:
            while city < n and buildings[city][0] <= line:
                pq.put([-buildings[city][2], buildings[city][0], buildings[city][1]])
                city += 1
            while not pq.empty() and pq.queue[0][2] <= line:
                pq.get()
            high = 0
            if not pq.empty():
                high = -pq.queue[0][0]
            if len(skys) > 0 and skys[-1][1] == high:
                continue
            skys.append([line, high])
        return skys

Continue Practicing

#315 count of smaller numbers after self #327 count of range sum #493 reverse pairs