LeetCode #218 — HARD

The Skyline Problem

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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] = [left_i, right_i, height_i]:

left_i is the x coordinate of the left edge of the i^th building.
right_i is the x coordinate of the right edge of the i^th building.
height_i is the height of the i^th 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 [[x₁,y₁],[x₂,y₂],...]. 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's 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 in the final output as such: [...,[2 3],[4 5],[12 7],...]

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⁴
0 <= left_i < right_i <= 2³¹ - 1
1 <= height_i <= 2³¹ - 1
buildings is sorted by left_i in non-decreasing order.

Step 01

Brute Force Baseline

Problem summary: 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

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Segment Tree

Example 1

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

Example 2

[[0,2,3],[2,5,3]]

Core Insight

What unlocks the optimal approach

No official hints in dataset. Start from constraints and look for a monotonic or reusable state.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #218: The Skyline Problem
class Solution {
  public List<List<Integer>> getSkyline(int[][] buildings) {
    final int n = buildings.length;
    if (n == 0)
      return new ArrayList<>();
    if (n == 1) {
      final int left = buildings[0][0];
      final int right = buildings[0][1];
      final int height = buildings[0][2];
      List<List<Integer>> ans = new ArrayList<>();
      ans.add(new ArrayList<>(List.of(left, height)));
      ans.add(new ArrayList<>(List.of(right, 0)));
      return ans;
    }

    List<List<Integer>> leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
    List<List<Integer>> rightSkyline = getSkyline(Arrays.copyOfRange(buildings, n / 2, n));
    return merge(leftSkyline, rightSkyline);
  }

  private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
    List<List<Integer>> ans = new ArrayList<>();
    int i = 0; // left's index
    int j = 0; // right's index
    int leftY = 0;
    int rightY = 0;

    while (i < left.size() && j < right.size())
      // Choose the point with the smaller x.
      if (left.get(i).get(0) < right.get(j).get(0)) {
        leftY = left.get(i).get(1); // Update the ongoing `leftY`.
        addPoint(ans, left.get(i).get(0), Math.max(left.get(i++).get(1), rightY));
      } else {
        rightY = right.get(j).get(1); // Update the ongoing `rightY`.
        addPoint(ans, right.get(j).get(0), Math.max(right.get(j++).get(1), leftY));
      }

    while (i < left.size())
      addPoint(ans, left.get(i).get(0), left.get(i++).get(1));

    while (j < right.size())
      addPoint(ans, right.get(j).get(0), right.get(j++).get(1));

    return ans;
  }

  private void addPoint(List<List<Integer>> ans, int x, int y) {
    if (!ans.isEmpty() && ans.get(ans.size() - 1).get(0) == x) {
      ans.get(ans.size() - 1).set(1, y);
      return;
    }
    if (!ans.isEmpty() && ans.get(ans.size() - 1).get(1) == y)
      return;
    ans.add(new ArrayList<>(List.of(x, y)));
  }
}

// Accepted solution for LeetCode #218: The Skyline Problem
type Matrix struct{ left, right, height int }
type Queue []Matrix

func (q Queue) Len() int           { return len(q) }
func (q Queue) Top() Matrix        { return q[0] }
func (q Queue) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }
func (q Queue) Less(i, j int) bool { return q[i].height > q[j].height }
func (q *Queue) Push(x any)        { *q = append(*q, x.(Matrix)) }
func (q *Queue) Pop() any {
	old, x := *q, (*q)[len(*q)-1]
	*q = old[:len(old)-1]
	return x
}

func getSkyline(buildings [][]int) [][]int {
	skys, lines, pq := make([][]int, 0), make([]int, 0), &Queue{}
	heap.Init(pq)
	for _, v := range buildings {
		lines = append(lines, v[0], v[1])
	}
	sort.Ints(lines)
	city, n := 0, len(buildings)
	for _, line := range lines {
		// 将所有符合条件的矩形加入队列
		for ; city < n && buildings[city][0] <= line && buildings[city][1] > line; city++ {
			v := Matrix{left: buildings[city][0], right: buildings[city][1], height: buildings[city][2]}
			heap.Push(pq, v)
		}
		// 从队列移除不符合条件的矩形
		for pq.Len() > 0 && pq.Top().right <= line {
			heap.Pop(pq)
		}
		high := 0
		// 队列为空说明是最右侧建筑物的终点，其轮廓点为 (line, 0)
		if pq.Len() != 0 {
			high = pq.Top().height
		}
		// 如果该点高度和前一个轮廓点一样的话，直接忽略
		if len(skys) > 0 && skys[len(skys)-1][1] == high {
			continue
		}
		skys = append(skys, []int{line, high})
	}
	return skys
}

# Accepted solution for LeetCode #218: The Skyline Problem
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

// Accepted solution for LeetCode #218: The Skyline Problem
impl Solution {
    pub fn get_skyline(buildings: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut skys: Vec<Vec<i32>> = vec![];
        let mut lines = vec![];
        for building in buildings.iter() {
            lines.push(building[0]);
            lines.push(building[1]);
        }
        lines.sort_unstable();
        let mut pq = std::collections::BinaryHeap::new();
        let (mut city, n) = (0, buildings.len());

        for line in lines {
            while city < n && buildings[city][0] <= line && buildings[city][1] > line {
                pq.push((buildings[city][2], buildings[city][1]));
                city += 1;
            }
            while !pq.is_empty() && pq.peek().unwrap().1 <= line {
                pq.pop();
            }
            let mut high = 0;
            if !pq.is_empty() {
                high = pq.peek().unwrap().0;
            }
            if !skys.is_empty() && skys.last().unwrap()[1] == high {
                continue;
            }
            skys.push(vec![line, high]);
        }
        skys
    }
}

// Accepted solution for LeetCode #218: The Skyline Problem
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #218: The Skyline Problem
// class Solution {
//   public List<List<Integer>> getSkyline(int[][] buildings) {
//     final int n = buildings.length;
//     if (n == 0)
//       return new ArrayList<>();
//     if (n == 1) {
//       final int left = buildings[0][0];
//       final int right = buildings[0][1];
//       final int height = buildings[0][2];
//       List<List<Integer>> ans = new ArrayList<>();
//       ans.add(new ArrayList<>(List.of(left, height)));
//       ans.add(new ArrayList<>(List.of(right, 0)));
//       return ans;
//     }
// 
//     List<List<Integer>> leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
//     List<List<Integer>> rightSkyline = getSkyline(Arrays.copyOfRange(buildings, n / 2, n));
//     return merge(leftSkyline, rightSkyline);
//   }
// 
//   private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
//     List<List<Integer>> ans = new ArrayList<>();
//     int i = 0; // left's index
//     int j = 0; // right's index
//     int leftY = 0;
//     int rightY = 0;
// 
//     while (i < left.size() && j < right.size())
//       // Choose the point with the smaller x.
//       if (left.get(i).get(0) < right.get(j).get(0)) {
//         leftY = left.get(i).get(1); // Update the ongoing `leftY`.
//         addPoint(ans, left.get(i).get(0), Math.max(left.get(i++).get(1), rightY));
//       } else {
//         rightY = right.get(j).get(1); // Update the ongoing `rightY`.
//         addPoint(ans, right.get(j).get(0), Math.max(right.get(j++).get(1), leftY));
//       }
// 
//     while (i < left.size())
//       addPoint(ans, left.get(i).get(0), left.get(i++).get(1));
// 
//     while (j < right.size())
//       addPoint(ans, right.get(j).get(0), right.get(j++).get(1));
// 
//     return ans;
//   }
// 
//   private void addPoint(List<List<Integer>> ans, int x, int y) {
//     if (!ans.isEmpty() && ans.get(ans.size() - 1).get(0) == x) {
//       ans.get(ans.size() - 1).set(1, y);
//       return;
//     }
//     if (!ans.isEmpty() && ans.get(ans.size() - 1).get(1) == y)
//       return;
//     ans.add(new ArrayList<>(List.of(x, y)));
//   }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n + q log n)

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n × q) time

O(1) space

For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.

SEGMENT TREE

O(n + q log n) time

O(n) space

Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.

Shortcut: Build O(n), query/update O(log n) each. When you need both range queries AND point updates.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.