Skip to main content

218. The Skyline Problem

hardAsked at DoorDash

Given a list of buildings (left, right, height), return the skyline as key points. DoorDash uses this for senior infrastructure rounds — the sweep-line + max-heap pattern shows up in surge-pricing and capacity-window problems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Skyline as the canonical sweep-line hard problem.
  • Blind (2025-12)— DoorDash SDE2 reports list this for surge-pricing-team rounds.

Problem

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]. The skyline should be represented as a list of 'key points' sorted by their x-coordinate in the form [[x_1, y_1], [x_2, y_2], ...]. 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.

Constraints

  • 1 <= buildings.length <= 10^4
  • 0 <= left_i < right_i <= 2^31 - 1
  • 1 <= height_i <= 2^31 - 1
  • buildings is sorted by left_i in non-decreasing order.

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

Example 2

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

Approaches

1. Sweep line with max-heap (lazy deletion)

Create events for building starts/ends. Sort. Sweep with a max-heap of active heights; on each event point, peek the heap, emit (x, currentMax) if changed.

Time
O(n log n)
Space
O(n)
function getSkyline(buildings) {
  const events = [];
  for (const [l, r, h] of buildings) {
    events.push([l, -h, r]);
    events.push([r, 0, 0]);
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const result = [];
  const heap = []; // [-height, endX]
  function push(v) {
    heap.push(v);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] > heap[i][0]) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  }
  let prev = 0;
  for (const [x, negH, r] of events) {
    if (negH !== 0) push([negH, r]);
    while (heap.length && heap[0][1] <= x) {
      const last = heap.pop();
      if (heap.length) {
        heap[0] = last;
        let i = 0;
        while (true) {
          const l = 2*i+1, ri = 2*i+2;
          let small = i;
          if (l < heap.length && heap[l][0] < heap[small][0]) small = l;
          if (ri < heap.length && heap[ri][0] < heap[small][0]) small = ri;
          if (small === i) break;
          [heap[i], heap[small]] = [heap[small], heap[i]];
          i = small;
        }
      }
    }
    const cur = heap.length ? -heap[0][0] : 0;
    if (cur !== prev) {
      result.push([x, cur]);
      prev = cur;
    }
  }
  return result;
}

Tradeoff: DoorDash's expected answer. The negated-height trick turns the min-heap into a max-heap. Lazy deletion: skip popped heights whose endX is in the past.

2. Divide and conquer (merge-sort style)

Recursively compute skyline for left half + right half. Merge two skylines like a sweep line.

Time
O(n log n)
Space
O(n)
function getSkylineDC(buildings) {
  function helper(start, end) {
    if (start === end) {
      const [l, r, h] = buildings[start];
      return [[l, h], [r, 0]];
    }
    const mid = (start + end) >> 1;
    return merge(helper(start, mid), helper(mid + 1, end));
  }
  function merge(a, b) {
    const result = [];
    let i = 0, j = 0, h1 = 0, h2 = 0;
    while (i < a.length && j < b.length) {
      let x, h;
      if (a[i][0] < b[j][0]) { x = a[i][0]; h1 = a[i][1]; i++; }
      else if (a[i][0] > b[j][0]) { x = b[j][0]; h2 = b[j][1]; j++; }
      else { x = a[i][0]; h1 = a[i][1]; h2 = b[j][1]; i++; j++; }
      const maxH = Math.max(h1, h2);
      if (!result.length || result[result.length - 1][1] !== maxH) result.push([x, maxH]);
    }
    while (i < a.length) result.push(a[i++]);
    while (j < b.length) result.push(b[j++]);
    return result;
  }
  return buildings.length ? helper(0, buildings.length - 1) : [];
}

Tradeoff: Same complexity. Some interviewers prefer this for the divide-and-conquer narrative. Heap version is more general.

DoorDash-specific tips

DoorDash interviewers grade on the LAZY-DELETION trick. State 'I'll push every building into a heap on its start, and on each x I'll pop the top until its endX > x' BEFORE coding. The heap-with-lazy-deletion pattern recurs in dispatch systems.

Common mistakes

  • Forgetting to filter duplicate consecutive heights — must emit only when the running max CHANGES.
  • Tie-breaking event sorting incorrectly: starts before ends at the same x; among multiple starts, taller first.
  • Naive removal from the heap on building end — O(n) per remove. Use lazy deletion via end-time check.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Falling Squares (LC 699) — segment-tree variant.
  • Meeting Rooms II (LC 253) — simpler sweep-line for max concurrent.
  • My Calendar III (LC 732) — same sweep-line shape.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why negate heights in the heap?

JS doesn't have a built-in max-heap. Negating turns max-heap into min-heap. The pop is still the largest absolute height.

Why is lazy deletion necessary?

Removing an arbitrary element from a heap is O(n). Lazy deletion (skip popped items whose endX is past) keeps it amortized O(log n).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill The Skyline Problem and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →