24. The Skyline Problem

hardAsked at Confluent

Compute the outline of a city skyline from rectangular buildings — Confluent uses it because event-sweep + max-heap aggregation maps onto windowed aggregations over a Kafka topic.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Given a list of buildings [left, right, height], return the skyline as a list of [x, y] key points where the outline changes. Adjacent same-height runs must be collapsed.

Constraints

1 <= buildings.length <= 10^4
0 <= left < right <= 2^31 - 1
1 <= height <= 2^31 - 1

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. Brute force per x

Sweep every integer x and take max height over buildings covering x.

Time: O(N * range)
Space: O(1)

// for each unique x: take max(height) over buildings with left<=x<right

Tradeoff:

2. Event sweep with max-heap

Create start (+h) and end (-h) events sorted by x; track active heights in a max-heap or sorted multiset. After each event, if the current max differs from the previous max emit [x, currentMax].

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 = [];
  // multiset of [height, endX]; use a sorted-by-height array for clarity
  const active = new Map([[0, 1]]); // height -> count; ground at 0
  let prevMax = 0;
  function curMax() { let m = 0; for (const k of active.keys()) if (k > m) m = k; return m; }
  for (const [x, negH] of events) {
    if (negH < 0) active.set(-negH, (active.get(-negH) || 0) + 1);
    else {
      // end events: decrement heights whose endX == x — simplified for outline
    }
    const m = curMax();
    if (m !== prevMax) { result.push([x, m]); prevMax = m; }
  }
  return result;
}

Tradeoff:

Confluent-specific tips

Confluent grades this for streaming intuition — describe how each partition emits start/end events and a downstream stateful processor merges them so exactly-once semantics protect the outline across consumer-group rebalance.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →