218. The Skyline Problem

At a Glance

Topic: intervals
Pattern: Sweep line + Heap / multiset (active heights)
Difficulty: Hard
Companies: Google, Microsoft, Amazon, Snowflake, Flipkart
Frequency: Medium
LeetCode: 218

Given building silhouettes as [left, right, height] triples, return the skyline as a list of [x, height] key points where visible height changes (output rules: merge adjacent same heights, unique x events).

Recognition Cues

City skyline / visible outline from infinity
Critical x coordinates only at building edges
Active set of rectangle tops — max height changes drive output

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Interval union height — continuous geometry — messy.
Events at each edge (start height / end height) + multiset of active heights — O(n log n) — optimal.

Optimal Solution

Go

import (
	"sort"
)

func getSkyline(buildings [][]int) [][]int {
	type edge struct {
		x          int
		height     int
		isStart bool
	}
	edges := make([]edge, 0, len(buildings)*2)
	for _, building := range buildings {
		left := building[0]
		right := building[1]
		height := building[2]
		edges = append(edges, edge{x: left, height: height, isStart: true})
		edges = append(edges, edge{x: right, height: height, isStart: false})
	}
	sort.Slice(edges, func(leftIndex, rightIndex int) bool {
		leftEdge := edges[leftIndex]
		rightEdge := edges[rightIndex]
		if leftEdge.x != rightEdge.x {
			return leftEdge.x < rightEdge.x
		}
		if leftEdge.isStart != rightEdge.isStart {
			return leftEdge.isStart
		}
		if leftEdge.isStart {
			return leftEdge.height > rightEdge.height
		}
		return leftEdge.height < rightEdge.height
	})
	counts := map[int]int{}
	currentMax := func() int {
		best := 0
		for height, frequency := range counts {
			if frequency > 0 && height > best {
				best = height
			}
		}
		return best
	}
	previousMax := 0
	result := [][]int{}
	for index := 0; index < len(edges); {
		currentX := edges[index].x
		for index < len(edges) && edges[index].x == currentX {
			edgeItem := edges[index]
			if edgeItem.isStart {
				counts[edgeItem.height]++
			} else {
				counts[edgeItem.height]--
			}
			index++
		}
		nextMax := currentMax()
		if nextMax != previousMax {
			result = append(result, []int{currentX, nextMax})
			previousMax = nextMax
		}
	}
	return result
}

JavaScript

function getSkyline(buildings) {
  const edges = [];
  for (const [left, right, height] of buildings) {
    edges.push({ x: left, height, isStart: true });
    edges.push({ x: right, height, isStart: false });
  }
  edges.sort((leftEdge, rightEdge) => {
    if (leftEdge.x !== rightEdge.x) {
      return leftEdge.x - rightEdge.x;
    }
    if (leftEdge.isStart !== rightEdge.isStart) {
      return leftEdge.isStart ? -1 : 1;
    }
    if (leftEdge.isStart) {
      return rightEdge.height - leftEdge.height;
    }
    return leftEdge.height - rightEdge.height;
  });
  const counts = new Map();
  function currentMax() {
    let best = 0;
    for (const [height, frequency] of counts) {
      if (frequency > 0 && height > best) {
        best = height;
      }
    }
    return best;
  }
  let previousMax = 0;
  const result = [];
  let edgeIndex = 0;
  while (edgeIndex < edges.length) {
    const currentX = edges[edgeIndex].x;
    while (edgeIndex < edges.length && edges[edgeIndex].x === currentX) {
      const edgeItem = edges[edgeIndex];
      if (edgeItem.isStart) {
        counts.set(edgeItem.height, (counts.get(edgeItem.height) || 0) + 1);
      } else {
        counts.set(edgeItem.height, (counts.get(edgeItem.height) || 0) - 1);
      }
      edgeIndex += 1;
    }
    const nextMax = currentMax();
    if (nextMax !== previousMax) {
      result.push([currentX, nextMax]);
      previousMax = nextMax;
    }
  }
  return result;
}

Walkthrough

Process edges left-to-right; starting edge adds height to multiset; ending removes. After each x-group, compare currentMax to previous — append [x, max] when it changes.

Invariant: counts always reflects buildings covering points immediately to the right of processed x.

Edge Cases

Touching buildings same height — multiset counts prevent premature drop
Single building — two points [left, height], [right, 0]
Nested buildings — inner starts may not change silhouette

Pitfalls

Wrong event order at same x — taller starts before shorter ends (sort rules above)
Using max-heap without duplicate height handling — multiset counts required

Variants

3D skyline — segment trees / plane sweep
Output full outline polygon — beyond key points
Dynamic insert building — augmented BST

Mind-Map Tags

#skyline #sweep-line #multiset-heights #edge-events #critical-points