Compute city skyline silhouette
Company: TikTok
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Compute the outer silhouette of a 2D skyline. You are given n axis-aligned rectangular buildings; each building i is (Li, Ri, Hi) with 0 <= Li < Ri and Hi > 0. Return the list of critical points (x, h) where the silhouette height changes, sorted by x ascending; consecutive points must have different heights, and the final point should drop to height 0 when the skyline ends. Aim for O(n log n) time and near-linear space. Implement and explain an efficient approach (e.g., sweep line with a max-structure or divide-and-conquer). Specify and handle tie cases when multiple edges share the same x (e.g., entering edges before leaving; among entering edges process higher heights first; among leaving edges process lower heights first). Discuss correctness, complexity, and edge cases such as identical buildings, fully nested intervals, touching borders (Ri == Lj), and very large coordinates.
Quick Answer: Compute city skyline silhouette evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given `n` axis-aligned rectangular buildings on a flat ground. Each building `i` is described by `(Li, Ri, Hi)` where `0 <= Li < Ri` is its left/right x-coordinate and `Hi > 0` is its height.
Compute the outer silhouette (skyline) formed by the union of all buildings. Return the list of **critical points** `[x, h]` — the points where the silhouette height changes — sorted by `x` ascending. The first coordinate of each key point is the x position; the second is the height there. Consecutive key points must have **different** heights (no redundant points), and the silhouette must terminate at a key point of height `0` where the rightmost building ends.
If there are no buildings, return an empty list.
This is the classic 'Skyline Problem'. Aim for `O(n log n)` time.
**Tie handling (important):** when multiple building edges share the same x, the algorithm must process them so the reported height is the true maximum across that x. Entering edges should be considered before leaving edges, among entering edges higher heights take effect first, and among leaving edges lower heights leave first — a sweep-line with a max-heap (and lazy deletion of ended buildings) achieves this naturally.
**Example:** `buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]` → `[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]`.
Constraints
- 0 <= n (n is the number of buildings; n may be 0)
- Each building is [L, R, H] with 0 <= L < R and H > 0
- Coordinates and heights may be large; the algorithm only compares values, so very large coordinates are fine
- Return key points sorted by x ascending with strictly alternating heights, ending at height 0
Examples
Input: [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Expected Output: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
Explanation: Canonical LC218 example. The silhouette rises as taller buildings begin, drops to 0 in the gap between x=12 and x=15, then resumes for the second cluster.
Input: [[0,2,3],[2,5,3]]
Expected Output: [[0, 3], [5, 0]]
Explanation: Two equal-height buildings touching at x=2 (Ri == Lj). The shared border produces no spurious key point — height stays 3 until the right end.
Hints
- Convert each building into two sweep-line events at its left and right edge, then sweep x from left to right while tracking the current maximum height among 'live' buildings.
- Use a max-heap keyed by height. The hard part is removal: a binary heap can't pop an arbitrary element, so use lazy deletion — store each building's right edge alongside its height and discard heap-top entries whose right edge has already been passed.
- Handle ties at a shared x carefully: process all events at the same x together, and emit a key point only when the resulting max height differs from the last emitted height. Encoding start edges as (x, -H, R) and end edges as (x, 0, 0) makes the sort order do the tie-breaking for you (starts before ends; taller starts first).