A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

  • lefti is the x coordinate of the left edge of the ith building.
  • righti is the x coordinate of the right edge of the ith building.
  • heighti is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of “key points” sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline’s termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3],[4 5],[7 5],[11 5],[12 7]...] is not acceptable; the three lines of height 5 should be merged into one: [...[2 3],[4 5],[12 7]...]

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

Constraints

  • 1 <= buildings.length <= 10^4
  • 0 <= lefti < righti <= 2^31 - 1
  • 1 <= heighti <= 2^31 - 1
  • buildings is sorted by lefti in non-decreasing order.

Thinking Process

This is a classic sweep line algorithm problem. The key insight is to process all building edges (start and end points) in sorted order and maintain the current maximum height at each position.

There are several approaches to solve this problem:

  1. Coordinate Compression + Brute Force: Compress coordinates and update heights for each building
  2. Sweep Line with Map: Use events and maintain height counts
  3. Sweep Line with Priority Queue: Use priority queue to track active buildings
  4. Sweep Line with Two Priority Queues: Separate queues for active and past heights
  5. Union Find Optimization: Use Union Find to optimize the coordinate compression approach
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Brute force (this problem) Often O(n^2) or O(2^n) O(n) Baseline; clarifies the optimization target
Sort + scan O(n log n) O(1) Pairs, intervals, greedy ordering
Hash map / set O(n) O(n) Frequency, membership, two-sum style
Single-pass linear O(n) O(1) Two pointers, sliding window, Kadane

Solution

// import java.util.*;
class Solution {
    public int[][] getSkyline(int[][] buildings) {
        TreeSet<Integer> edgeSet = new TreeSet<>();
        for (int building : buildings) {
        int left = building[0], right = building[1];
            edgeSet.add(left);
            edgeSet.add(right);
        }
        int[]edges(edgeSet /* elements of edgeSet */);
        TreeMap<Integer, Integer> edgeIdxMap = new TreeMap<>();
        for(int i = 0; i < edges.length; i++) {
            edgeIdxMap[edges[i]] = i;
        }
        int[]heights(edges.length);
        for (int building : buildings) {
            int left = building[0], right = building[1], height = building[2];
            int leftIdx = edgeIdxMap[left], rightIdx = edgeIdxMap[right];
            for(int idx = leftIdx; idx < rightIdx; idx++) {
                heights.put(idx, Math.max(heights[idx], height));
            }
        }
        List<int[]> rtn = new ArrayList<>();
        for(int i = 0; i < heights.length; i++) {
            int curHeight = heights[i], curPos = edges[i];
            if(i == 0 || curHeight != heights[i - 1]) {
                rtn.add(new int[] {curPos, curHeight});
            }
        }
        return rtn;
    }
}

Solution Explanation

Approach: Brute force (this problem)

Key idea: This is a classic sweep line algorithm problem. The key insight is to process all building edges (start and end points) in sorted order and maintain the current maximum height at each position.

How the code works:

  1. Coordinate Compression + Brute Force: Compress coordinates and update heights for each building
  2. Sweep Line with Map: Use events and maintain height counts
  3. Sweep Line with Priority Queue: Use priority queue to track active buildings
  4. Sweep Line with Two Priority Queues: Separate queues for active and past heights
  5. Union Find Optimization: Use Union Find to optimize the coordinate compression approach

Walkthrough — input buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]], expected 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.

Step-by-Step Example (Solution 2)

Let’s trace through buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]:

Create Events:

(2, -10), (9, 10)   // Building 1: height 10
(3, -15), (7, 15)   // Building 2: height 15  
(5, -12), (12, 12)  // Building 3: height 12
(15, -10), (20, 10) // Building 4: height 10
(19, -8), (24, 8)   // Building 5: height 8

Sort Events:

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

Process Events:

  1. x=2: Add height 10 → max=10 → add [2,10]
  2. x=3: Add height 15 → max=15 → add [3,15]
  3. x=5: Add height 12 → max=15 → no change
  4. x=7: Remove height 15 → max=12 → add [7,12]
  5. x=9: Remove height 10 → max=12 → no change
  6. x=12: Remove height 12 → max=0 → add [12,0]
  7. x=15: Add height 10 → max=10 → add [15,10]
  8. x=19: Add height 8 → max=10 → no change
  9. x=20: Remove height 10 → max=8 → add [20,8]
  10. x=24: Remove height 8 → max=0 → add [24,0]

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

Algorithm Analysis

Solution Comparison:

Solution Time Complexity Space Complexity Approach Pros Cons
Coordinate Compression O(n²) O(n) Brute Force Simple logic Inefficient
Sweep Line + Map O(n log n) O(n) Event Processing Clean, efficient Map overhead
Sweep Line + PQ O(n log n) O(n) Priority Queue Intuitive PQ cleanup needed
Two Priority Queues O(n log n) O(n) Dual PQ Handles duplicates More complex
Union Find O(n²) worst O(n) Optimization Skips processed Complex implementation

Key Insights:

  1. Event Processing: Convert buildings to start/end events
  2. Height Tracking: Maintain current maximum height efficiently
  3. Change Detection: Only add skyline points when height changes
  4. Coordinate Handling: Process events in sorted order
  5. Data Structure Choice: Map vs Priority Queue trade-offs

Common Mistakes

  1. Not handling height changes correctly - Only add points when height changes
  2. Incorrect event sorting - Must handle ties properly
  3. Memory management - Clean up expired buildings from priority queue
  4. Edge cases - Handle empty buildings, single building scenarios

  5. Coordinate precision - Handle large coordinate values

  6. Single building: [[1,2,3]] → [[1,3],[2,0]]
  7. Overlapping buildings: Same height buildings
  8. Adjacent buildings: Buildings touching at edges
  9. Large coordinates: Integer overflow considerations
  10. Empty input: Return empty skyline

Key Takeaways

  • Pattern: Brute force (this problem)

References

Conclusion

The Skyline Problem is a classic sweep line algorithm that tests understanding of:

  1. Event Processing: Converting 2D problems to 1D events
  2. Data Structures: Choosing appropriate structures for height tracking
  3. Algorithm Design: Efficiently processing sorted events
  4. Edge Case Handling: Managing height changes and duplicates

Recommended Solution: Solution 2 (Sweep Line with Map) offers the best balance of efficiency, clarity, and correctness for most scenarios.

The key insight is recognizing that skyline changes only occur at building edges, and we need to efficiently track the maximum height at each position while processing events in order.