Skip to main content
Talentd

The Skyline Problem - Solution & Explanation

HardArrayDivide and ConquerBinary Indexed TreeSegment Tree17 min readAsked at: Amazon, Microsoft, Apple +10
Practice this problem

Problem Statement

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

  • lefti is the x coordinate of the left edge of the ith building.
  • righti is the x coordinate of the right edge of the ith building.
  • heighti is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]

 

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]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

 

Constraints:

  • 1 <= buildings.length <= 104
  • 0 <= lefti < righti <= 231 - 1
  • 1 <= heighti <= 231 - 1
  • buildings is sorted by lefti in non-decreasing order.

Approach Overview

Problem Overview: You are given a list of buildings represented as [left, right, height]. Each building forms a rectangle on the skyline. The task is to compute the outer contour of all buildings combined and return the key points where the skyline height changes.

Approach 1: Sweep Line Algorithm with Priority Queue (O(n log n) time, O(n) space)

The most common solution treats building edges as events and processes them from left to right using a sweep line. Convert every building into two events: a start edge (height enters) and an end edge (height leaves). Sort all events by x-coordinate, then track active building heights with a max heap (priority queue). When the sweep line encounters a start edge, push the height into the heap; when it encounters an end edge, remove that height. The maximum value in the heap represents the current skyline height. Whenever this maximum changes, record a new key point. The heap ensures efficient retrieval of the tallest active building in O(log n). This approach is the standard solution for skyline and interval-overlay problems and heavily relies on techniques from Line Sweep and Heap (Priority Queue).

Approach 2: Divide and Conquer (O(n log n) time, O(n) space)

This method mirrors merge sort. Split the buildings array into two halves, recursively compute the skyline for each half, then merge the two skylines into a combined outline. During merging, iterate through both skyline lists while tracking the current heights from the left and right halves. The visible skyline at any x-coordinate is the maximum of the two heights. Whenever this maximum changes, append a new key point. The key challenge is merging two skyline outlines while eliminating redundant height segments. The recursive structure leads to O(n log n) time, similar to merge sort. This approach highlights algorithmic design patterns from Divide and Conquer and is useful when reasoning about skyline merging rather than event simulation.

Recommended for interviews: The sweep line with a priority queue is the approach most interviewers expect. It demonstrates understanding of event processing, heaps, and geometric interval problems. The divide and conquer solution is equally optimal but less commonly implemented under time pressure. Showing the sweep line idea first proves you recognize the canonical skyline technique.

Approach 1: Approach 1: Sweep Line Algorithm with Priority Queue

The Sweep Line algorithm involves moving a vertical line from left to right over the x-coordinates and maintaining a list of currently active buildings using a max-heap. The priority queue helps keep track of the tallest building at each point. As the line reaches the start of a new building, add it to the heap, and as it reaches the end of a building, remove it. The key points are detected based on changes in the maximum height at points where buildings start or end.

This code uses a priority queue (min-heap) where we push the negative of the height to simulate a max-heap, to manage the building heights efficiently. We handle start and end events separately, ensuring the heap accurately reflects the current tallest building. While processing each event, code also manages to merge the same consecutive heights, ensuring result compliance with the rules.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(N log N), where N is the number of events (two for each building).
Space Complexity: O(N), as we store up to N building heights in the heap.

Try this approach in the editor →

Approach 2: Approach 2: Divide and Conquer

This approach involves breaking down the problem using the divide and conquer strategy. The buildings array is split into two halves recursively. The base case is a single building, where the skyline can directly be calculated. The results are then merged, taking care of overlapping heights and ensuring continuity and distinct key points.

This Python code uses the divide and conquer strategy where each call splits the building list into two halves and recursively solves for both sides, merging their results into a coherent skyline outline by comparing the heights at each step and ensuring the output is minimal.

Code

PythonJavaC++C#JavaScript

Python

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(N log N), due to division of buildings and merging.
Space Complexity: O(N), needing space for recursive stack and individual skyline lists.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonC++GoRust

Python

C++

Go

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sweep Line Algorithm with Priority Queue

Time Complexity: O(N log N), where N is the number of events (two for each building).
Space Complexity: O(N), as we store up to N building heights in the heap.

Approach 2: Divide and Conquer

Time Complexity: O(N log N), due to division of buildings and merging.
Space Complexity: O(N), needing space for recursive stack and individual skyline lists.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sweep Line with Priority QueueO(n log n)O(n)Best general solution. Efficient for large building sets and the most common interview approach.
Divide and ConquerO(n log n)O(n)Useful when modeling the skyline merge process or applying merge-sort style recursion.

Video Solution

Skyline Problem • Tushar Roy - Coding Made Simple • 204,993 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is The Skyline Problem easy or hard?
The Skyline Problem is classified as Hard because it combines multiple concepts: event sorting, heap management, and careful handling of overlapping intervals. Implementing the sweep line logic without producing redundant points requires careful reasoning.
How to solve The Skyline Problem in O(n)?
An exact O(n) algorithm generally isn't feasible because building edges must be processed in sorted order. Sorting alone requires O(n log n) time in comparison-based models. The practical optimal approach is O(n log n) using a sweep line with a max heap or a divide and conquer skyline merge.
What is the best approach for The Skyline Problem?
The sweep line algorithm with a priority queue is the most widely used solution. Convert building edges into start and end events, sort them by x-coordinate, and track active heights using a max heap. Whenever the maximum height changes, record a new skyline key point. This approach runs in O(n log n) time and O(n) space.
Is The Skyline Problem asked at Google/Amazon/Meta?
The Skyline Problem appears frequently in interviews at large tech companies including Google, Amazon, and Meta. It tests understanding of sweep line algorithms, heaps, and interval merging. Variants of skyline or silhouette problems are commonly used to evaluate algorithmic reasoning.
What data structure is used in The Skyline Problem?
The primary data structure is a max heap (priority queue) that stores active building heights during the sweep line traversal. Other implementations may use balanced ordered sets, segment trees, or binary indexed trees to manage height ranges efficiently.
What is the time complexity of The Skyline Problem?
Most optimal solutions run in O(n log n) time. Sorting building edges requires O(n log n), and each heap insertion or removal during the sweep line process costs O(log n). The overall space complexity is typically O(n) to store events, the heap, and the resulting skyline points.
The Skyline Problem Python or Java solution approach?
Most Python and Java implementations follow the sweep line pattern. Convert each building into two events, sort the events, and use a priority queue to maintain active heights. Each time the maximum height changes, append a new skyline key point to the result.

Ready to solve this problem?

Practice The Skyline Problem with our built-in code editor and test cases.

Practice on FleetCode
Previous

Falling Squares

Next

Shifting Letters II