The Skyline Problem

Problem Statement

Given a list of buildings on a flat cityscape, each represented as a triplet [left, right, height], produce the skyline — a list of key points [x, height] that traces the outer contour of all buildings combined.

A key point is an x-coordinate where the skyline height changes. The output traces the silhouette from left to right, dropping to height 0 where no building covers the ground.

Consider three buildings: [2, 9, 10], [3, 7, 15], [5, 12, 12].

     15 |   ┌───────┐
        |   │       │
        |   │       │            
     12 |   │       │  ┌────────┐
        |   │       │  │        │
     10 | ┌─┤       │  │        │
        | │ │       │  │        │
        | │ │       ├──┤        │
        | │ │       │  │        │
      0 ├─┴─┴───────┴──┴────────┴──
        0 2 3 5     7  9       12

The resulting skyline:

     15 |   ┌───────┐
        |   │       │
        |   │       │
     12 |   │       └──┐
        |   │          │
     10 | ┌─┘          │
        | │            │
        | │            │
        | │            │
      0 ├─┘            └───────────
        0 2 3 5     7  9       12

Output key points: [[2, 10], [3, 15], [7, 12], [12, 0]]

Each point marks where the skyline height changes. At x=2, the skyline rises to 10. At x=3, it rises further to 15. At x=7, the tallest building ends and the skyline drops to 12. At x=12, the last building ends and the skyline drops to 0.

Key Insight: Sweep Line

Processing buildings as a whole is awkward — they overlap, nest inside each other, and share edges. The sweep line approach decomposes the problem into events: moments when something changes.

Two things matter at any x-coordinate:

1. Which buildings are currently active (their horizontal range covers this x).
2. The maximum height among those active buildings.

Whenever the maximum height changes, a new key point is emitted. The sweep line processes events left-to-right, maintaining a data structure that tracks active building heights and answers “what is the current max?” efficiently.

Algorithm: Sweep Line with Max-Heap

Step 1: Create Events

For each building [left, right, height], generate two events:

• Start event at x = left: a building of this height becomes active.
• End event at x = right: this building becomes inactive.

To simplify sorting and processing, encode start events with negative height and end events with positive height:

• Start: (left, -height)
• End: (right, height)

Sort events by x-coordinate. When two events share the same x-coordinate, tie-breaking rules are critical:

• Same x, start vs. end: Start events come first. A building that starts at x=5 is active at x=5 and affects the skyline there.
• Two starts at the same x: Taller building first. This prevents emitting an intermediate lower key point that immediately gets overridden.
• Two ends at the same x: Shorter building first. This ensures we remove the shorter building before the taller one, avoiding a premature height drop.

The negative-height encoding handles all three rules automatically: sorting (x, height) lexicographically places starts (negative) before ends (positive) at the same x, and among starts, the most negative (tallest) comes first.

Step 2: Process Events with a TreeMap

A TreeMap<Integer, Integer> maps height → count of active buildings at that height. It serves as a max-heap with deletion support:

• lastKey() returns the current maximum height in O(log n).
• Inserting and removing heights takes O(log n).
• Duplicate heights are handled by incrementing/decrementing the count.

Initialize the TreeMap with {0: 1} — ground level is always active. This avoids special-casing the “no buildings active” scenario.

For each event:

1. Start event (negative height): Add |height| to the TreeMap. Increment its count, or insert with count 1.
2. End event (positive height): Decrement the count of this height. If the count reaches 0, remove the entry.
3. Check max height: After processing the event, query lastKey(). If it differs from the previous max, emit a key point [x, currentMax].

Implementation

record Event(int x, int height) implements Comparable<Event> {
    @Override
    public int compareTo(Event other) {
        if (this.x != other.x) return Integer.compare(this.x, other.x);
        return Integer.compare(this.height, other.height);
    }
}

List<List<Integer>> getSkyline(int[][] buildings) {
    // Step 1: Create and sort events
    List<Event> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new Event(b[0], -b[2]));  // start: negative height
        events.add(new Event(b[1], b[2]));   // end: positive height
    }
    Collections.sort(events);

    // Step 2: Process events with TreeMap as max-heap
    TreeMap<Integer, Integer> activeHeights = new TreeMap<>();
    activeHeights.put(0, 1);  // ground level
    int prevMax = 0;
    List<List<Integer>> result = new ArrayList<>();

    for (Event e : events) {
        if (e.height() < 0) {
            // Start event: add height
            int h = -e.height();
            activeHeights.merge(h, 1, Integer::sum);
        } else {
            // End event: remove height
            int count = activeHeights.get(e.height());
            if (count == 1) {
                activeHeights.remove(e.height());
            } else {
                activeHeights.put(e.height(), count - 1);
            }
        }

        int currentMax = activeHeights.lastKey();
        if (currentMax != prevMax) {
            result.add(List.of(e.x(), currentMax));
            prevMax = currentMax;
        }
    }
    return result;
}

The Event record encapsulates the sorting logic. The Comparable implementation ensures events sort by x-coordinate first, then by height — which, due to the negative encoding for starts, produces the correct tie-breaking order automatically.

The TreeMap.merge() method handles insertion cleanly: if the height exists, increment its count; otherwise, insert with count 1. For removal, check the count and either decrement or remove the entry entirely.

Detailed Walkthrough

Process the three buildings [2, 9, 10], [3, 7, 15], [5, 12, 12]:

Events after sorting:

x	height (encoded)	Type
2	-10	Start
3	-15	Start
5	-12	Start
7	15	End
9	10	End
12	12	End

Processing:

1. (2, -10) — Start, height 10. TreeMap: {0:1, 10:1}. Max = 10. Changed from 0 → 10. Emit [2, 10].

2. (3, -15) — Start, height 15. TreeMap: {0:1, 10:1, 15:1}. Max = 15. Changed from 10 → 15. Emit [3, 15].

3. (5, -12) — Start, height 12. TreeMap: {0:1, 10:1, 12:1, 15:1}. Max = 15. No change. No emission.

4. (7, 15) — End, height 15. TreeMap: {0:1, 10:1, 12:1}. Max = 12. Changed from 15 → 12. Emit [7, 12].

5. (9, 10) — End, height 10. TreeMap: {0:1, 12:1}. Max = 12. No change. No emission.

6. (12, 12) — End, height 12. TreeMap: {0:1}. Max = 0. Changed from 12 → 0. Emit [12, 0].

Result: [[2, 10], [3, 15], [7, 12], [12, 0]] — matching the expected skyline.

Alternative: Divide and Conquer

The divide and conquer approach splits the building list in half, recursively computes the skyline for each half, and then merges the two skylines. The merge operation resembles the merge step in merge sort but tracks the current height from each side.

List<List<Integer>> getSkylineDC(int[][] buildings) {
    return divideAndConquer(buildings, 0, buildings.length - 1);
}

List<List<Integer>> divideAndConquer(int[][] buildings, int lo, int hi) {
    if (lo == hi) {
        return List.of(
            List.of(buildings[lo][0], buildings[lo][2]),
            List.of(buildings[lo][1], 0)
        );
    }
    int mid = lo + (hi - lo) / 2;
    var left = divideAndConquer(buildings, lo, mid);
    var right = divideAndConquer(buildings, mid + 1, hi);
    return mergeSkylines(left, right);
}

List<List<Integer>> mergeSkylines(List<List<Integer>> left,
                                  List<List<Integer>> right) {
    List<List<Integer>> merged = new ArrayList<>();
    int i = 0, j = 0;
    int leftHeight = 0, rightHeight = 0, prevMax = 0;

    while (i < left.size() && j < right.size()) {
        int x;
        if (left.get(i).get(0) < right.get(j).get(0)) {
            x = left.get(i).get(0);
            leftHeight = left.get(i).get(1);
            i++;
        } else if (left.get(i).get(0) > right.get(j).get(0)) {
            x = right.get(j).get(0);
            rightHeight = right.get(j).get(1);
            j++;
        } else {
            x = left.get(i).get(0);
            leftHeight = left.get(i).get(1);
            rightHeight = right.get(j).get(1);
            i++;
            j++;
        }
        int currentMax = Math.max(leftHeight, rightHeight);
        if (currentMax != prevMax) {
            merged.add(List.of(x, currentMax));
            prevMax = currentMax;
        }
    }
    while (i < left.size()) merged.add(left.get(i++));
    while (j < right.size()) merged.add(right.get(j++));
    return merged;
}

The merge function walks through both skylines simultaneously, picking the smaller x-coordinate at each step. At every x, the effective height is the maximum of the current heights from both sides. A key point is emitted only when this maximum changes.

The divide and conquer approach has the same O(n log n) time complexity as the sweep line. The merge step is O(n), and the recursion depth is O(log n). In practice, the sweep line approach is more commonly used in interviews because the merge logic for divide and conquer is error-prone and harder to get right under pressure.

Complexity Analysis

Approach	Time	Space
Sweep Line + TreeMap	O(n log n)	O(n)
Divide and Conquer	O(n log n)	O(n)

For the sweep line: creating events is O(n), sorting is O(n log n), and processing each event involves an O(log n) TreeMap operation, totaling O(n log n). Space is O(n) for the event list and the TreeMap.

For divide and conquer: the recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) by the Master Theorem. Space is O(n) for the merged results at each level.

Tricky Edge Cases

Buildings sharing an edge. Building [1, 5, 10] and building [5, 10, 8]. At x=5, the first building ends and the second starts. The skyline should transition smoothly: [1, 10] → [5, 8] → [10, 0]. The event sorting ensures the start at x=5 (encoded as -8) is processed before the end at x=5 (encoded as 10), preventing a momentary drop to 0.

Building completely inside another. Building [1, 10, 15] contains [3, 7, 10]. The inner building never affects the skyline because its height (10) never exceeds the outer building’s height (15). The TreeMap handles this naturally — the max is always 15 while both are active.

Multiple buildings starting at the same x. Buildings [2, 5, 10] and [2, 7, 15]. Both start at x=2. The negative encoding ensures the taller building (-15) sorts before the shorter one (-10). Processing the taller one first sets the max to 15, and the shorter one doesn’t change the max. Only one key point [2, 15] is emitted.

Multiple buildings ending at the same x. Buildings [1, 5, 15] and [3, 5, 10]. Both end at x=5. The positive encoding ensures the shorter one (10) sorts before the taller one (15). Removing height 10 first doesn’t change the max (still 15). Then removing height 15 drops the max to 0. One key point [5, 0] is emitted.

Single building. [2, 5, 10] produces [[2, 10], [5, 0]] — the building rises and falls. The TreeMap with ground-level initialization handles this without special casing.

Why TreeMap Instead of PriorityQueue?

Java’s PriorityQueue is a min-heap that does not support efficient removal of arbitrary elements. Removing a specific height from a PriorityQueue is O(n) — it requires a linear scan to find and remove the element. Since end events need to remove specific heights, using a PriorityQueue degrades the sweep line to O(n²).

A TreeMap<Integer, Integer> (height → count) provides:

• O(log n) insertion: merge(h, 1, Integer::sum)
• O(log n) deletion: remove(h) or decrement count
• O(log n) max query: lastKey()

The count value handles duplicate heights. If three buildings of height 10 are active, activeHeights contains {10: 3}. Ending one building decrements the count to 2 rather than removing the height entirely. The max height remains 10 as long as at least one building of that height is active.

An alternative is using a PriorityQueue with lazy deletion — marking removed elements and skipping them when they surface as the max. This works but complicates the code and can degrade to O(n log n) worst case with many stale entries. The TreeMap approach is cleaner and more predictable.

Interviewer Tips

This problem tests the ability to handle complex overlapping intervals under time pressure. Start by drawing the buildings and skyline contour on a whiteboard. The visual makes the event-based decomposition intuitive and demonstrates strong problem-solving methodology.

The event sorting tie-breaking rules are where most candidates fail. Explain why starts come before ends at the same x-coordinate, and why taller starts come first. The negative-height encoding trick eliminates the need for a custom comparator with multiple branches — a clean signal that you’ve seen this pattern before.

Common follow-up questions:

• Streaming buildings (online algorithm). Buildings arrive one at a time. The sweep line approach requires all buildings upfront. An online variant maintains a persistent balanced BST of active heights and processes events as they arrive. The TreeMap-based approach adapts directly — insert/remove heights as buildings arrive/expire.
• 3D skyline problem. Buildings have depth as well as height and width. The problem generalizes to computing a 2D silhouette from a 3D scene, which is fundamentally harder and typically handled with computational geometry techniques like the Bentley-Ottmann algorithm.
• Return the area under the skyline. After computing the key points, integrate by summing the area of each rectangular segment between consecutive key points. This is a straightforward extension: for each pair of adjacent key points [x1, h1] and [x2, h2], add h1 * (x2 - x1) to the total area.
• What if buildings can have negative heights (underground)? The problem structure changes. The TreeMap approach still works, but you track both above-ground and below-ground maxima separately, and the key point definition must account for the underground contour.