218. The Skyline Problem

Array Divide and Conquer Binary Search Sorting Heap (Priority Queue)Ordered Set

Time: O(n log n)

Space: O(n)

Intuition

Use a max-heap (sorted set) of active building heights. For each event (start or end of a building), update the heap and emit a keypoint when the maximum height changes. Process starts before ends at the same x-coordinate (to avoid height-0 gaps).

Algorithm

1Create events: for each building [l,r,h], add (l, -h) for start and (r, h) for end.
2Sort events by x; for equal x, starts (negative h) come before ends.
3Use a sorted multiset of heights, initialised with [0].
4For each event: if start (h<0), insert |h|. If end (h>0), remove h.
5If the current max height changes, emit (x, maxHeight) as a keypoint.

Example Walkthrough

Input: [[2,9,10],[3,7,15],[5,12,12]]

1.x=2: add 10. max=10 -> emit [2,10].
2.x=3: add 15. max=15 -> emit [3,15].
3.x=5: add 12. max=15 (unchanged).
4.x=7: remove 15. max=12 -> emit [7,12].
5.x=9: remove 10. max=12 (unchanged).
6.x=12: remove 12. max=0 -> emit [12,0].

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

Common Pitfalls

•Sort starts before ends at the same x to avoid premature height-drop keypoints.

218.cs

// Approach: Divide and conquer — split the buildings list in half, recursively compute
// each half's skyline, then merge two skylines into one.
// Merging two skylines uses a two-pointer sweep over their key points.
// At each x-coordinate, take the maximum height from both skylines.
// Only add a key point to the result when the effective maximum height changes.
// This is analogous to merge-sort and shares the same recurrence T(n) = 2T(n/2) + O(n).
// Time: O(n log n) Space: O(n) for temporary skyline lists.

public class Solution
{
    public IList<IList<int>> GetSkyline(int[][] buildings)
    {
        int n = buildings.Length;
        if (n == 0)
            return new List<IList<int>>();
        if (n == 1)
        {
            int left = buildings[0][0];
            int right = buildings[0][1];
            int height = buildings[0][2];
            IList<IList<int>> ans = new List<IList<int>>();
            ans.Add(new List<int> { left, height });
            ans.Add(new List<int> { right, 0 });
            return ans;
        }

        IList<IList<int>> leftSkyline = GetSkyline(buildings[0..(n / 2)]);
        IList<IList<int>> rightSkyline = GetSkyline(buildings[(n / 2)..n]);
        return Merge(leftSkyline, rightSkyline);
    }

    private IList<IList<int>> Merge(IList<IList<int>> left, IList<IList<int>> right)
    {
        IList<IList<int>> ans = new List<IList<int>>();
        int i = 0; // left's index
        int j = 0; // right's index
        int leftY = 0;
        int rightY = 0;

        while (i < left.Count && j < right.Count)
        {
            // Choose the point with the smaller x.
            if (left[i][0] < right[j][0])
            {
                leftY = left[i][1]; // Update the ongoing `leftY`.
                AddPoint(ans, left[i][0], Math.Max(left[i++][1], rightY));
            }
            else
            {
                rightY = right[j][1]; // Update the ongoing `rightY`.
                AddPoint(ans, right[j][0], Math.Max(right[j++][1], leftY));
            }
        }

        while (i < left.Count)
            AddPoint(ans, left[i][0], left[i++][1]);

        while (j < right.Count)
            AddPoint(ans, right[j][0], right[j++][1]);

        return ans;
    }

    private void AddPoint(IList<IList<int>> ans, int x, int y)
    {
        if (ans.Count > 0 && ans[ans.Count - 1][0] == x)
        {
            ans[ans.Count - 1][1] = y;
            return;
        }
        if (ans.Count > 0 && ans[ans.Count - 1][1] == y)
            return;
        ans.Add(new List<int> { x, y });
    }
}

Was this solution helpful?