We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Skyline Problem

Number: 218

Difficulty: Hard

Paid? No

Companies: Amazon, Google, Meta, Apple, Siemens, Uber, Goldman Sachs, Microsoft, Yelp, X

Problem Description

Given an array of buildings where each building is represented by [left, right, height], the task is to compute the skyline formed by these buildings. The skyline is a list of key points that describes the outer contour of the combined silhouette of the buildings when viewed from a distance. Each key point is defined by an x-coordinate and a height, and consecutive key points with the same height should be merged. The final key point always ends with a height of 0 to show the termination of the skyline.

Key Insights

  • Use a line sweep approach to process building start and end events in sorted order.
  • Differentiate between start events (which add to the skyline) and end events (which remove from the skyline).
  • Employ a max heap (or a priority queue) to efficiently track the current highest building at each sweep line position.
  • When the current maximum height changes, record the corresponding x-coordinate and new height as a key point.
  • Take care to remove expired building heights from the heap as the sweep line moves past the building's end.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting events and heap operations for each building event. Space Complexity: O(n) for the event list and the heap used for processing active buildings.

Solution

The solution uses the line sweep algorithm with a max heap (or priority queue) to maintain the heights of active buildings. Each building contributes two events: one when the building starts (adding its height) and one when it ends (removing its height). These events are sorted primarily by their x-coordinate. For start events, we use negative height values to ensure they are processed before end events at the same x-coordinate. During the sweep, the heap is updated by adding new building heights and removing buildings that have ended. Whenever there is a change in the top of the heap (i.e., the current maximum height), a key point is added to the result. This key point signifies a vertical change in the skyline.

Code Solutions

import heapq

def getSkyline(buildings):
    # List to store all events: (x, height, right)
    events = []
    # Create events for all buildings: left edge (start) and right edge (end)
    for left, right, height in buildings:
        # For the start point, height is negative for proper sorting (start events come before end events)
        events.append((left, -height, right))
        # For the end point, height is 0 to indicate removal of building from active heap
        events.append((right, 0, 0))
    
    # Sort events by x coordinate.
    events.sort()
    
    # Max heap to store active buildings (using negative heights)
    result = []
    # Initialize the heap with a dummy building of height 0 that extends infinitely
    heap = [(0, float('inf'))]
    
    for x, neg_height, right in events:
        # Remove buildings from the heap that have ended by current x.
        while heap and heap[0][1] <= x:
            heapq.heappop(heap)
        
        # If event is a start event (neg_height != 0), push it into the heap.
        if neg_height != 0:
            heapq.heappush(heap, (neg_height, right))
        
        # Current highest building height is at the top of the heap
        current_height = -heap[0][0]
        # If the result is empty or current height differs from last recorded height, add a new key point.
        if not result or current_height != result[-1][1]:
            result.append([x, current_height])
    
    return result

# Example usage:
buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
print(getSkyline(buildings))  # Expected output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
← Back to All Questions