What is the time complexity of The Skyline Problem?

The optimal solution has a time complexity of O(n log n).

What data structures are used to solve The Skyline Problem?

This problem uses Array, Divide and Conquer, Binary Indexed Tree, Segment Tree, Line Sweep, Sorting, Heap (Priority Queue), Ordered Set. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving The Skyline Problem?

Insight 1: Treat the start and end of each building as separate events. The start event increases the current maximum height, and the end event decreases it. These events drive the skyline's changes. Insight 2: Use a data structure (max-heap) to efficiently track the current maximum height at any given x-coordinate. This allows us to quickly determine if a skyline point needs to be added or updated.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

The Skyline Problem - LeetCode 218 Solution

Q: Which companies ask LeetCode 218. The Skyline Problem in interviews?

This problem is frequently asked at Citadel, Goldman Sachs, Google, Salesforce, Siemens and 2 more companies.

The Skyline Problem - Complete Solution Guide

The Skyline Problem is LeetCode problem 218, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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] = [left i , right i , height i ] : left i is the x coordinate of the left edge of the i th building. right i is the x coordinate of the right edge of the i th buildin

Detailed Explanation

The Skyline Problem asks us to determine the outer contour of a city's skyline given the locations and heights of its buildings. The input is a list of buildings, where each building is represented by a tuple (left, right, height), indicating the x-coordinates of its left and right edges and its height. The output should be a list of key points, representing the skyline. These key points are the left endpoints of the horizontal segments that make up the skyline's contour. The skyline should be sorted by x-coordinate, and there should be no consecutive horizontal lines of equal height. The last point always has a y-coordinate of 0 to mark the end of the skyline.

Solution Approach

The provided solution uses a line sweep algorithm along with a max-heap to efficiently determine the skyline. It processes the buildings from left to right based on their start and end x-coordinates. Each building contributes two events: a start event (left edge, negative height) and an end event (right edge, positive height). The negative height is used to distinguish start events from end events when sorting. The max-heap stores the heights of all active buildings at a given x-coordinate. By maintaining this max-heap, we can determine the current maximum height and identify points where the skyline changes.

Step-by-Step Algorithm

Step 1: Create a list of points, where each point represents either the start or end of a building. Store these points as tuples (x-coordinate, height), using negative heights to represent start events and positive heights to represent end events.
Step 2: Sort the points by their x-coordinate. If two points have the same x-coordinate, prioritize start events (negative height) over end events (positive height) or events with larger heights.
Step 3: Initialize a max-heap to keep track of the current active building heights. Initially, the max-heap contains a single element, 0, representing the ground level.
Step 4: Initialize a map (or dictionary) to keep track of heights to be deleted because heights are not easily removed from a max-heap
Step 5: Iterate through the sorted points. For each point:
Step 5a: If it's a start event (negative height), add the height to the max-heap.
Step 5b: If it's an end event (positive height), mark the height for deletion.
Step 6: After processing each x-coordinate, remove heights from the heap that were marked for deletion
Step 7: Get the current maximum height from the max-heap.
Step 8: Compare the current maximum height with the height of the last key point in the skyline. If they are different, add a new key point (x-coordinate, current maximum height) to the skyline. Handle cases where the new key point has the same x-coordinate as the previous one (update the height) or has the same height as the previous one (remove the redundant key point).
Step 9: Return the skyline.

Key Insights

Insight 1: Treat the start and end of each building as separate events. The start event increases the current maximum height, and the end event decreases it. These events drive the skyline's changes.
Insight 2: Use a data structure (max-heap) to efficiently track the current maximum height at any given x-coordinate. This allows us to quickly determine if a skyline point needs to be added or updated.
Insight 3: Handle overlapping and adjacent buildings correctly. The solution should gracefully handle cases where buildings share the same x-coordinate or have varying heights that influence the skyline's shape.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

Topics

This problem involves: Array, Divide and Conquer, Binary Indexed Tree, Segment Tree, Line Sweep, Sorting, Heap (Priority Queue), Ordered Set.

Companies

Asked at: Citadel, Goldman Sachs, Google, Salesforce, Siemens, X, Yelp.

The Skyline Problem | LeetCode 218

Hard

Array Divide and Conquer Binary Indexed Tree Segment Tree Line Sweep Sorting Heap (Priority Queue)Ordered Set

Time: O(n log n)Space: O(n)

Solution Code

Available in:

import java.util.*;

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<int[]> points = new ArrayList<>();
        for (int[] building : buildings) {
            int l = building[0];
            int r = building[1];
            int h = building[2];
            points.add(new int[]{l, -h});
            points.add(new int[]{r, h});
        }

        points.sort((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });

        List<List<Integer>> skyline = new ArrayList<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(0);
        Map<Integer, Integer> deleted = new HashMap<>();

        int i = 0;
        int n = points.size();
        while (i < n) {
            int curr_x = points.get(i)[0];

            int j = i;
            while (j < n && points.get(j)[0] == curr_x) {
                int x = points.get(j)[0];
                int h_val = points.get(j)[1];
                if (h_val < 0) {
                    int height = -h_val;
                    maxHeap.add(height);
                } else {
                    int height = h_val;
                    deleted.put(height, deleted.getOrDefault(height, 0) + 1);
                }
                j++;
            }
            i = j;

            while (maxHeap.size() > 1 && deleted.containsKey(maxHeap.peek()) && deleted.get(maxHeap.peek()) > 0) {
                int h_to_del = maxHeap.peek();
                deleted.put(h_to_del, deleted.get(h_to_del) - 1);
                maxHeap.poll();
            }

            int curr_max_h = maxHeap.peek();

            int last_skyline_h = skyline.isEmpty() ? 0 : skyline.get(skyline.size() - 1).get(1);

            if (curr_max_h != last_skyline_h) {
                if (!skyline.isEmpty() && skyline.get(skyline.size() - 1).get(0) == curr_x) {
                    skyline.get(skyline.size() - 1).set(1, curr_max_h);
                } else {
                    skyline.add(Arrays.asList(curr_x, curr_max_h));
                }

                if (skyline.size() >= 2 && skyline.get(skyline.size() - 1).get(1) == skyline.get(skyline.size() - 2).get(1)) {
                    skyline.remove(skyline.size() - 1);
                }

                if (!skyline.isEmpty() && skyline.get(skyline.size() - 1).get(1) == 0 && skyline.size() > 1) {
                    if (skyline.get(skyline.size() - 2).get(0) == skyline.get(skyline.size() - 1).get(0)) {
                        skyline.remove(skyline.size() - 2);
                    }
                }
            }
        }

        return skyline;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 218: The Skyline Problem - Detailed explanation and solution approaches.

Topics

Array Divide and Conquer Binary Indexed Tree Segment Tree Line Sweep Sorting Heap (Priority Queue)Ordered Set

Companies

CitadelGoldman SachsGoogleSalesforceSiemensXYelp

Stats

Difficulty:Hard

Languages:4

Companies:7

Problem #:218

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Create a list of points, where each point represents either the start or end of a building. Store these points as tuples (x-coordinate, height), using negative heights to represent start events and positive heights to represent end events.
2
Step 2: Sort the points by their x-coordinate. If two points have the same x-coordinate, prioritize start events (negative height) over end events (positive height) or events with larger heights.
3
Step 3: Initialize a max-heap to keep track of the current active building heights. Initially, the max-heap contains a single element, 0, representing the ground level.
4
Step 4: Initialize a map (or dictionary) to keep track of heights to be deleted because heights are not easily removed from a max-heap
5
Step 5: Iterate through the sorted points. For each point:
6
Step 5a: If it's a start event (negative height), add the height to the max-heap.
7
Step 5b: If it's an end event (positive height), mark the height for deletion.
8
Step 6: After processing each x-coordinate, remove heights from the heap that were marked for deletion
9
Step 7: Get the current maximum height from the max-heap.
10
Step 8: Compare the current maximum height with the height of the last key point in the skyline. If they are different, add a new key point (x-coordinate, current maximum height) to the skyline. Handle cases where the new key point has the same x-coordinate as the previous one (update the height) or has the same height as the previous one (remove the redundant key point).
11
Step 9: Return the skyline.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n log n)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

Sorting the points takes O(n log n). Iterating through the points to populate the skyline and the heap takes O(n), however there are at most O(n) elements in the heap, and each heap operation (add, delete, peek) takes O(log n), for a total of O(n log n) overall. The auxiliary structures (points, skyline, max-heap, deleted) each take O(n) space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Divide and Conquer

Divide the buildings into two halves, recursively compute the skyline for each half, and then merge the two skylines. This can be more complicated to implement correctly, especially the merging step.

Time: O(n log n)Space: O(n)

Trade-offs: Can have a higher constant factor than the heap-based approach, making it less efficient in practice. Implementation complexity is higher as well.

✨

Key Insights

1Insight 1: Treat the start and end of each building as separate events. The start event increases the current maximum height, and the end event decreases it. These events drive the skyline's changes.
2Insight 2: Use a data structure (max-heap) to efficiently track the current maximum height at any given x-coordinate. This allows us to quickly determine if a skyline point needs to be added or updated.
3Insight 3: Handle overlapping and adjacent buildings correctly. The solution should gracefully handle cases where buildings share the same x-coordinate or have varying heights that influence the skyline's shape.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Buildings with the same left x-coordinate. The solution sorts events such that buildings starting at the same x-coordinate are processed before those ending, allowing for proper height determination.
Edge case 2: Buildings with overlapping x-coordinate ranges but different heights. The max-heap ensures that the tallest building determines the skyline's height at any given point.
Edge case 3: Consecutive buildings with the same height. The algorithm has checks to ensure that the skyline does not have consecutive horizontal lines of equal height, merging them into one.
Edge case 4: Empty input. The algorithm should handle an empty list of buildings gracefully, returning an empty skyline (or a skyline with a single point [0,0]).

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly sorting the points. Failing to prioritize start events over end events when x-coordinates are the same can lead to incorrect skyline formation.

✗Common mistake 2: Not handling deleted heights properly. If the deletion is not performed as needed when calculating maximum height, this can lead to a skyline that does not properly reflect the shape of the buildings.

✗Common mistake 3: Not considering the base case. Failing to account for when there are no buildings results in the code attempting to access a negative index

✗Common mistake 4: Not removing consecutive horizontal segments of the same height. Failing to properly handle this condition could create invalid outputs.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Visualization of cityscapes in architectural software or geographic information systems (GIS).

🏦Real-world scenario 2: Resource allocation and scheduling problems where events have start and end times, and the goal is to determine the maximum resource usage at any given time. This is similar to determining the maximum height of the skyline.

🎮Real-world scenario 3: Database systems, where you need to track active transactions at any given time.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 9, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "The Skyline Problem"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether divide and conquer techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?