The O(n) Club: The Skyline Problem — Heap, Sweep, and the Art of Urban Java

The O(n) Club: The Skyline Problem — Heap, Sweep, and the Art of Urban Java

⚡ TL;DR

Given a row of buildings, your job is to chart those dramatic points where the city’s outline jumps up or down—basically, draw a proper skyline. The brute force method? Crawl every x, check every building, and pray for daylight. In reality, the sweep line + max-heap combo is your only hope for a skyline that’s all peaks, no headaches.

// Please no: brute-force version
for (int x = minX; x <= maxX; x++) {
    int maxH = 0;
    for (int[] building : buildings) {
        if (building[0] <= x && x < building[1]) {
            maxH = Math.max(maxH, building[2]);
        }
    }
    // Only record (x, maxH) if it changes
}

🧠 How Devs Usually Mess This Up

So, you threw every building onto the canvas and tried to render the skyline column by column? Welcome to O(n²) performance and an art installation called “How to Burn a JVM.” If you mess up how you sort starts versus ends or forget to clean up finished buildings, your skyline will have more steps than a Zumba class. And if you don’t check if the height actually changed before adding a point, congratulations: you’ve invented the world’s most jittery city outline.

🔍 What’s Actually Going On

Picture a robotic broom sweeping across the city from left to right. Every building offers up two events: a dramatic entrance (start) and a not-so-dramatic exit (end). As the sweep passes a building’s opening, its height jumps on a giant heap; at closing time, it checks out. The heap is your bouncer—it always knows which building is tallest. Every time the peak height changes, it’s a headline moment: update the skyline!

🛠️ PseudoCode

• Turn buildings into events: For each building [L, R, H], make two tickets:
  (L, -H)
(R, H)
• Sort events: Events go by x-coordinate. If two clash:
  • Let taller starts go first.
  • Let smaller ends end earlier (because taller ends should keep the sky high as long as possible).
• Sweep left to right: For each event:
  • If start, heap.add(height)
  • If end, heap.remove(height)
• After each move, check heap’s top dog.
  • If the max height changed, record key point (x, height). Cue the skyline chorus!

💻 The Code

// Java sweep line for the win
public List<list>> getSkyline(int[][] buildings) {
    List<int> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2]}); // Start event
        events.add(new int[]{b[1],  b[2]}); // End event
    }
    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
    List<list>> result = new ArrayList<>();
    PriorityQueue
<integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    heap.add(0); // Ground level
    int prev = 0;
    for (int[] e : events) {
        if (e[1] < 0) {
            heap.add(-e[1]); // Building rises
        } else {
            heap.remove(e[1]); // Building ends
        }
        int curr = heap.peek();
        if (curr != prev) {
            result.add(Arrays.asList(e[0], curr));
            prev = curr;
        }
    }
    return result;
}</integer></list></int></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• Event order chaos: If you get sorting of starts vs ends backward, your buildings will look like a wild stock market chart.
• Heap.remove() is slow: Sure, heap.remove() is O(n), so for monster cities, look into TreeMap. But in interviews, PriorityQueue is just fine — call it “urban prototyping.”
• Don’t be a key point spammer: No duplicate heights — only add (x, h) if there’s an actual view change.
• Time/Space sanity: Sort and heap ops give you O(N log N). Heap and event list cost O(N) space. That’s skyline-sustainable.

🧠 Interviewer Brain-Tattoo

“A real skyline doesn’t stutter. Sort events, use your heap. When in doubt: sweep, peek, and only raise the roof when something actually changes.”