DevExCode

LeetCode 218: The Skyline Problem Solution

Master LeetCode problem 218 (The Skyline Problem), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

The problem can be solved using a data structure like a priority queue (max heap) to keep track of the heights of the buildings. We iterate through the buildings and for each building, we add the left corner with a negative height to indicate the start of a building, and the right corner with a positive height to indicate the end of a building. By doing this, we can keep track of the heights and their respective positions.

We iterate through the buildings in sorted order of their left corners. At each iteration, we update the current maximum height and compare it with the previous maximum height to determine if there is a transition in the skyline. If there is a transition, we record the key point in the skyline.

Time complexity: O(n log n) where n is the number of buildings Space complexity: O(n) for the priority queue

:

Solution Code

import java.util.*;

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> result = new ArrayList<>();
        List<int[]> buildingPoints = new ArrayList<>();

        for (int[] building : buildings) {
            buildingPoints.add(new int[]{building[0], -building[2]});
            buildingPoints.add(new int[]{building[1], building[2]});
        }

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

        Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.offer(0);
        int prevMaxHeight = 0;

        for (int[] point : buildingPoints) {
            if (point[1] < 0) {
                maxHeap.offer(-point[1]);
            } else {
                maxHeap.remove(point[1]);
            }

            int currentMaxHeight = maxHeap.peek();
            if (prevMaxHeight != currentMaxHeight) {
                List<Integer> keyPoint = new ArrayList<>();
                keyPoint.add(point[0]);
                keyPoint.add(currentMaxHeight);
                result.add(keyPoint);
                prevMaxHeight = currentMaxHeight;
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 218 (The Skyline Problem)?

This page provides optimized solutions for LeetCode problem 218 (The Skyline Problem) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 218 (The Skyline Problem)?

The time complexity for LeetCode 218 (The Skyline Problem) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 218 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 218 in Java, C++, or Python.

Back to LeetCode Solutions