Heap / Priority Queue crash course ↗ · 158

218. The Skyline Problem

Given a set of rectangular buildings, output the outline of the city skyline as a list of key points. Sweep a vertical line left to right over the building edges, keeping a max-heap of active heights; emit a point whenever the tallest live building changes.

● HardSweep LineMax-HeapTypeScript

PROBLEM What we're solving

Each building is [left, right, height]. We want the silhouette of the whole city as a sequence of key points [x, height], where each point marks the left endpoint of a horizontal segment of the outline; the last point always drops to height 0. For buildings = [[2,9,10],[3,7,15],[5,12,12]] the answer is [[2,10],[3,15],[7,12],[12,0]]: the outline rises to 10 at x=2, jumps to 15 at x=3, falls to 12 at x=7 (the tall middle building ends), and drops to 0 at x=12 when the last building ends.

KEY IDEA A key point is where the max height changes

The running max → the skyline's height at any x is simply the maximum height among all buildings currently overlapping x. As we sweep left to right, this max only changes at building edges. So we process those edges in order, maintain the set of active heights in a max-heap, and emit [x, newMax]exactly when the heap's top differs from the previous max.

That turns "what is the tallest building over every x" into a handful of updates at the 2n edges instead of scanning the ground inch by inch.

RECIPE Sort edges, sweep, emit on change

1 · Make events. For each building push a start event at left and an end event at right. Encode a start as -height and an end as +height so a single sort key handles ties.
2 · Sort. By x ascending; break ties by the signed height. This makes starts come before ends at the same x, and among starts the taller one first.
3 · Sweep. At a start, push(height) onto the max-heap; at an end, mark that height for lazy deletion.
4 · Emit on change. Read heap.top() (0 if empty). If it differs from prevMax, append [x, top] and update prevMax.

Classic confusion → tie-handling at a shared x. If a building starts exactly where another ends (or two start together), naive ordering produces spurious or duplicate points. Sorting starts before ends at equal x, tallest start first and shortest end first (which the -h / +h encoding gives for free), makes the "emit only when max changes" rule produce the correct, duplicate-free outline.

COST Complexity & alternatives

Paint every column

O(n²)

For each of n buildings, update a span of coordinates / scan all others.

Sweep + max-heap

O(n log n)

Sort 2n events, each heap op is O(log n).

Why lazy deletion?

A binary heap has no O(log n) "remove arbitrary element". Instead we mark an ended height as pending and only discard it once it bubbles to the top — amortized O(log n) per event. A balanced multiset / TreeMap of counts is an equivalent clean alternative; divide-and-conquer (merge two skylines) also runs in O(n log n).

Pattern transfer →the "sort edge events, sweep a line, keep an active set" shape powers Meeting Rooms II (count overlaps), Merge Intervals, Minimum Interval to Include Each Query, and any geometry problem where the answer only changes at interval endpoints.

RUN IT Sweep the edges, keep a max-heap, emit when the top moves

buildings =

step 0 / 13

STARTBuilt and sorted 6 edge events from 3 buildings. Each start is stored as -height, each end as +height; sorted by x then signed height. The heap is empty and prevMax = 0.

1type Building = [left: number, right: number, height: number];
2type KeyPoint = [x: number, height: number];
3 
4// A tiny max-heap of heights with lazy deletion (no decrease-key needed).
5class MaxHeap {
6  private a: number[] = [];
7  private toDelete = new Map<number, number>(); // height -> pending removals
8 
9  push(h: number): void {
10    this.a.push(h);
11    let i = this.a.length - 1;
12    while (i > 0) {
13      const parent = (i - 1) >> 1;
14      if (this.a[parent] >= this.a[i]) break;
15      [this.a[parent], this.a[i]] = [this.a[i], this.a[parent]];
16      i = parent;
17    }
18  }
19 
20  // Mark a height for removal; it is purged once it reaches the top.
21  remove(h: number): void {
22    this.toDelete.set(h, (this.toDelete.get(h) ?? 0) + 1);
23  }
24 
25  // Lazily discard stale tops, then report the live max (0 = ground).
26  top(): number {
27    while (this.a.length > 0) {
28      const h = this.a[0];
29      const pending = this.toDelete.get(h) ?? 0;
30      if (pending === 0) return h;
31      if (pending === 1) this.toDelete.delete(h);
32      else this.toDelete.set(h, pending - 1);
33      this.popRoot();
34    }
35    return 0;
36  }
37 
38  private popRoot(): void {
39    const last = this.a.pop()!;
40    if (this.a.length === 0) return;
41    this.a[0] = last;
42    let i = 0;
43    const n = this.a.length;
44    for (;;) {
45      const l = 2 * i + 1;
46      const r = 2 * i + 2;
47      let big = i;
48      if (l < n && this.a[l] > this.a[big]) big = l;
49      if (r < n && this.a[r] > this.a[big]) big = r;
50      if (big === i) break;
51      [this.a[big], this.a[i]] = [this.a[i], this.a[big]];
52      i = big;
53    }
54  }
55}
56 
57function getSkyline(buildings: Building[]): KeyPoint[] {
58  // Build sweep events: a start lowers x first, ties broken to add tall first.
59  const events: Array<[x: number, h: number]> = [];
60  for (const [l, r, h] of buildings) {
61▶    events.push([l, -h]); // start: negative height marks an "add"
62▶    events.push([r, h]);  // end: positive height marks a "remove"
63  }
64  // Sort by x; at equal x, process by signed height so adds beat removes and
65  // a taller start is handled before a shorter one.
66▶  events.sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));
67 
68  const result: KeyPoint[] = [];
69  const heap = new MaxHeap();
70  let prevMax = 0; // current skyline height to the left of this x
71 
72  for (const [x, signedH] of events) {
73    if (signedH < 0) heap.push(-signedH); // a building begins
74    else heap.remove(signedH);            // a building ends
75 
76    const curMax = heap.top();
77    if (curMax !== prevMax) {
78      // The running max changed here -> this x is a key point.
79      result.push([x, curMax]);
80      prevMax = curMax;
81    }
82  }
83 
84  return result;
85}

events =start h10x=2start h15x=3start h12x=5end h15x=7end h10x=9end h12x=12

State

∅

heap (active)

prevMax

—

curMax

—

event

[]

result

current eventprocessed / active heapkey point emittedground (height 0)

slowfast

TYPESCRIPT The solution, annotated

getSkyline.ts
type Building = [left: number, right: number, height: number];
type KeyPoint = [x: number, height: number];

// A tiny max-heap of heights with lazy deletion (no decrease-key needed).
class MaxHeap {
  private a: number[] = [];
  private toDelete = new Map<number, number>(); // height -> pending removals

  push(h: number): void {
    this.a.push(h);
    let i = this.a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.a[parent] >= this.a[i]) break;
      [this.a[parent], this.a[i]] = [this.a[i], this.a[parent]];
      i = parent;
    }
  }

  // Mark a height for removal; it is purged once it reaches the top.
  remove(h: number): void {
    this.toDelete.set(h, (this.toDelete.get(h) ?? 0) + 1);
  }

  // Lazily discard stale tops, then report the live max (0 = ground).
  top(): number {
    while (this.a.length > 0) {
      const h = this.a[0];
      const pending = this.toDelete.get(h) ?? 0;
      if (pending === 0) return h;
      if (pending === 1) this.toDelete.delete(h);
      else this.toDelete.set(h, pending - 1);
      this.popRoot();
    }
    return 0;
  }

  private popRoot(): void {
    const last = this.a.pop()!;
    if (this.a.length === 0) return;
    this.a[0] = last;
    let i = 0;
    const n = this.a.length;
    for (;;) {
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      let big = i;
      if (l < n && this.a[l] > this.a[big]) big = l;
      if (r < n && this.a[r] > this.a[big]) big = r;
      if (big === i) break;
      [this.a[big], this.a[i]] = [this.a[i], this.a[big]];
      i = big;
    }
  }
}

function getSkyline(buildings: Building[]): KeyPoint[] {
  // Build sweep events: a start lowers x first, ties broken to add tall first.
  const events: Array<[x: number, h: number]> = [];
  for (const [l, r, h] of buildings) {
    events.push([l, -h]); // start: negative height marks an "add"
    events.push([r, h]);  // end: positive height marks a "remove"
  }
  // Sort by x; at equal x, process by signed height so adds beat removes and
  // a taller start is handled before a shorter one.
  events.sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));

  const result: KeyPoint[] = [];
  const heap = new MaxHeap();
  let prevMax = 0; // current skyline height to the left of this x

  for (const [x, signedH] of events) {
    if (signedH < 0) heap.push(-signedH); // a building begins
    else heap.remove(signedH);            // a building ends

    const curMax = heap.top();
    if (curMax !== prevMax) {
      // The running max changed here -> this x is a key point.
      result.push([x, curMax]);
      prevMax = curMax;
    }
  }

  return result;
}

Reading it block by block

The max-heap with lazy deletion. A plain binary heap supports push and read-max, but not removing an arbitrary interior value cheaply. So remove(h) just records a pending deletion in a count map; top() discards any pending heights that have surfaced to the root before returning the real maximum (or 0 for the ground when empty).

Building events. Every building becomes two events: a start at left stored as -height, and an end at right stored as +height. The sign distinguishes "add" from "remove" and doubles as the tie-breaker in the sort.

The sort. Order by x; at equal x order by signed height. Because starts are negative, they sort before ends at the same x; among two starts the taller (more negative) comes first; among two ends the shorter comes first. This single comparator removes every tie ambiguity.

The sweep. Walk the events in order. A negative signed height means a building begins, so push its height; a positive one means it ends, so remove that height (lazily).

Emit on change. After updating the heap at this x, read heap.top(). If the live maximum differs from prevMax, the silhouette changes here, so append [x, curMax] and advance prevMax. When the last building ends the top becomes 0, producing the final ground-level key point.

Complexity → Sorting 2n events is O(n log n). Each event does O(1) heap pushes/removes plus an amortized O(log n) cleanup in top(), so the sweep is O(n log n) overall. Space is O(n) for the events and the heap.

INTERVIEWFollow-ups they'll ask

"Why a max-heap and not a min-heap or a plain variable?" We need the current tallest among an arbitrary, changing set of active buildings — that is exactly a max-priority-queue query.
"How do you delete an ended building from a binary heap?" Lazy deletion: record the height as pending and purge it only when it reaches the top. Or use a balanced multiset / TreeMap of counts for true O(log n) removal.
"Handle buildings that touch (one ends where the next starts)?" The sort order — starts before ends at equal x — plus emitting only when the max changes yields no spurious or duplicate points.
"Give a different O(n log n) approach." Divide and conquer: recursively compute the skyline of each half and merge them like merge-sort, tracking the running height of each side.
"What if coordinates are huge or real-valued?" The sweep only cares about the order of edges, not their magnitude, so it works unchanged; coordinate compression is unnecessary here.

OPTIMAL Sweep Line

getSkyline.ts
type Building = [left: number, right: number, height: number];
type KeyPoint = [x: number, height: number];

// A tiny max-heap of heights with lazy deletion (no decrease-key needed).
class MaxHeap {
  private a: number[] = [];
  private toDelete = new Map<number, number>(); // height -> pending removals

  push(h: number): void {
    this.a.push(h);
    let i = this.a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.a[parent] >= this.a[i]) break;
      [this.a[parent], this.a[i]] = [this.a[i], this.a[parent]];
      i = parent;
    }
  }

  // Mark a height for removal; it is purged once it reaches the top.
  remove(h: number): void {
    this.toDelete.set(h, (this.toDelete.get(h) ?? 0) + 1);
  }

  // Lazily discard stale tops, then report the live max (0 = ground).
  top(): number {
    while (this.a.length > 0) {
      const h = this.a[0];
      const pending = this.toDelete.get(h) ?? 0;
      if (pending === 0) return h;
      if (pending === 1) this.toDelete.delete(h);
      else this.toDelete.set(h, pending - 1);
      this.popRoot();
    }
    return 0;
  }

  private popRoot(): void {
    const last = this.a.pop()!;
    if (this.a.length === 0) return;
    this.a[0] = last;
    let i = 0;
    const n = this.a.length;
    for (;;) {
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      let big = i;
      if (l < n && this.a[l] > this.a[big]) big = l;
      if (r < n && this.a[r] > this.a[big]) big = r;
      if (big === i) break;
      [this.a[big], this.a[i]] = [this.a[i], this.a[big]];
      i = big;
    }
  }
}

function getSkyline(buildings: Building[]): KeyPoint[] {
  // Build sweep events: a start lowers x first, ties broken to add tall first.
  const events: Array<[x: number, h: number]> = [];
  for (const [l, r, h] of buildings) {
    events.push([l, -h]); // start: negative height marks an "add"
    events.push([r, h]);  // end: positive height marks a "remove"
  }
  // Sort by x; at equal x, process by signed height so adds beat removes and
  // a taller start is handled before a shorter one.
  events.sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));

  const result: KeyPoint[] = [];
  const heap = new MaxHeap();
  let prevMax = 0; // current skyline height to the left of this x

  for (const [x, signedH] of events) {
    if (signedH < 0) heap.push(-signedH); // a building begins
    else heap.remove(signedH);            // a building ends

    const curMax = heap.top();
    if (curMax !== prevMax) {
      // The running max changed here -> this x is a key point.
      result.push([x, curMax]);
      prevMax = curMax;
    }
  }

  return result;
}

ALT 1 Divide & conquer (merge skylines)

O(n log n) time · O(n) space

Split the buildings in half, recursively skyline each half, then merge the two outlines like merge-sort— walking both by x and tracking each side's current height, emitting a point only when the combined max changes.

approach-2.ts
type Building = [left: number, right: number, height: number];
type KeyPoint = [x: number, height: number];

// Merge two already-computed skylines into one. We walk both lists by x,
// keeping each side's current height; the combined height is their max, and
// we emit a point only when that combined max actually changes.
function mergeSkylines(left: KeyPoint[], right: KeyPoint[]): KeyPoint[] {
  const merged: KeyPoint[] = [];
  let i = 0;
  let j = 0;
  let leftH = 0;  // current height contributed by the left skyline
  let rightH = 0; // current height contributed by the right skyline
  let prevMax = 0;

  while (i < left.length && j < right.length) {
    let x: number;
    // Advance whichever side has the smaller x (or both, on a tie).
    if (left[i][0] < right[j][0]) {
      x = left[i][0];
      leftH = left[i][1];
      i++;
    } else if (right[j][0] < left[i][0]) {
      x = right[j][0];
      rightH = right[j][1];
      j++;
    } else {
      x = left[i][0];
      leftH = left[i][1];
      rightH = right[j][1];
      i++;
      j++;
    }
    const curMax = Math.max(leftH, rightH);
    if (curMax !== prevMax) {
      merged.push([x, curMax]);
      prevMax = curMax;
    }
  }

  // Drain whichever list still has points; the other side is at height 0 now,
  // so its contribution can't change the running max again.
  while (i < left.length) {
    const [x, h] = left[i++];
    if (h !== prevMax) {
      merged.push([x, h]);
      prevMax = h;
    }
  }
  while (j < right.length) {
    const [x, h] = right[j++];
    if (h !== prevMax) {
      merged.push([x, h]);
      prevMax = h;
    }
  }

  return merged;
}

function getSkyline(buildings: Building[]): KeyPoint[] {
  // Base cases: empty -> no outline; single building -> rise then drop.
  if (buildings.length === 0) return [];
  if (buildings.length === 1) {
    const [l, r, h] = buildings[0];
    return [[l, h], [r, 0]];
  }

  // Split in half and recurse, then merge — exactly like merge-sort.
  const mid = buildings.length >> 1;
  const left = getSkyline(buildings.slice(0, mid));
  const right = getSkyline(buildings.slice(mid));
  return mergeSkylines(left, right);
}

Note → Same O(n log n) bound as the heap sweep, with no priority queue: there are log nlevels of recursion and each level merges a total of O(n) key points. Merging two skylines is the same two-pointer walk as merge-sort's combine step.

ALT 2 Brute force (max over boundaries)

O(n²) time · O(n) space

Collect every distinct building edge as a candidate x; at each one compute the max height among buildings covering it, and emit a point whenever that height differs from the previous boundary.

approach-3.ts
type Building = [left: number, right: number, height: number];
type KeyPoint = [x: number, height: number];

function getSkyline(buildings: Building[]): KeyPoint[] {
  if (buildings.length === 0) return [];

  // Every place the outline can change is a left or right edge of some building.
  const xs: number[] = [];
  for (const [l, r] of buildings) {
    xs.push(l, r);
  }
  xs.sort((a, b) => a - b);

  const result: KeyPoint[] = [];
  let prevMax = 0;
  let prevX = Number.NaN;

  for (const x of xs) {
    if (x === prevX) continue; // skip duplicate boundaries
    prevX = x;

    // Tallest building whose half-open span [l, r) covers x. Using a half-open
    // interval means a building stops contributing exactly at its right edge,
    // which is what lets the outline fall there.
    let curMax = 0;
    for (const [l, r, h] of buildings) {
      if (l <= x && x < r && h > curMax) curMax = h;
    }

    if (curMax !== prevMax) {
      result.push([x, curMax]);
      prevMax = curMax;
    }
  }

  return result;
}

Note → Easiest to reason about and a good correctness oracle, but the inner scan over all buildings at each of the O(n) boundaries makes it O(n²). The half-open test l <= x && x < r is what produces the final drop to 0 at the rightmost edge.

MNEMONIC The one-liner

"Sort the edges, sweep the line, push starts and drop ends — print when the top moves."

TRIGGERS When you see _ → reach for _

outline / silhouette of overlapping rectangles	sweep line over edges
answer changes only at interval endpoints	event sort + active set
need the tallest among a changing set	max-heap (priority queue)
remove arbitrary element from a binary heap	lazy deletion via count map

SKELETON The reusable shape

skeleton.ts
const events = [];
for (const [l, r, h] of buildings) { events.push([l, -h]); events.push([r, h]); }
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // x, then signed height

let prevMax = 0; const result = [];
for (const [x, sh] of events) {
  sh < 0 ? heap.push(-sh) : heap.remove(sh); // start adds, end removes
  const cur = heap.top();                    // 0 = ground
  if (cur !== prevMax) { result.push([x, cur]); prevMax = cur; }
}

FLASHCARDS Tap to flip

What is a "key point" in the skyline?

A point [x, height] marking the left end of a horizontal segment of the outline — emitted whenever the running max height changes (the last drops to 0).

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the optimal time complexity of the skyline algorithm?

QUESTION 02

For buildings = [[2,9,10],[3,7,15],[5,12,12]], the correct skyline is:

QUESTION 03

Why store a start as -height and an end as +height before sorting?

QUESTION 04

When is a key point emitted during the sweep?

QUESTION 05

Why use lazy deletion instead of removing the ended height immediately?

QUESTION 06

What does heap.top() return when no buildings are active at the current x?

QUESTION 07

Which related problem uses the same sweep-line-over-endpoints idea?

QUESTION 08

#218 · The Skyline ProblemGiven rectangular buildings, output the skyline as key points. Sweep left to right over the building edges, keep a max-heap of active heights, and emit a point whenever the running max height changes. O(n log n).Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA A key point is where the max height changes

RECIPE Sort edges, sweep, emit on change

COST Complexity & alternatives

Why lazy deletion?

RUN IT Sweep the edges, keep a max-heap, emit when the top moves

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Sweep Line

ALT 1 Divide & conquer (merge skylines)

ALT 2 Brute force (max over boundaries)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _