Table of Contents

# The Skyline Problem – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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`

is the x coordinate of the left edge of the_{i}`i`

building.^{th}`right`

is the x coordinate of the right edge of the_{i}`i`

building.^{th}`height`

is the height of the_{i}`i`

building.^{th}

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 `[[x`

. 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 _{1},y_{1}],[x_{2},y_{2}],...]`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 <= 10`

^{4}`0 <= left`

_{i}< right_{i}<= 2^{31}- 1`1 <= height`

_{i}<= 2^{31}- 1`buildings`

is sorted by`left`

in non-decreasing order._{i}

# C++ The Skyline Problem LeetCode Solution

```
``````
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> res;
int cur=0, cur_X, cur_H =-1, len = buildings.size();
priority_queue< pair<int, int>> liveBlg; // first: height, second, end time
while(cur<len || !liveBlg.empty())
{ // if either some new building is not processed or live building queue is not empty
cur_X = liveBlg.empty()? buildings[cur][0]:liveBlg.top().second; // next timing point to process
if(cur>=len || buildings[cur][0] > cur_X)
{ //first check if the current tallest building will end before the next timing point
// pop up the processed buildings, i.e. those have height no larger than cur_H and end before the top one
while(!liveBlg.empty() && ( liveBlg.top().second <= cur_X) ) liveBlg.pop();
}
else
{ // if the next new building starts before the top one ends, process the new building in the vector
cur_X = buildings[cur][0];
while(cur<len && buildings[cur][0]== cur_X) // go through all the new buildings that starts at the same point
{ // just push them in the queue
liveBlg.push(make_pair(buildings[cur][2], buildings[cur][1]));
cur++;
}
}
cur_H = liveBlg.empty()?0:liveBlg.top().first; // outut the top one
if(res.empty() || (res.back().second != cur_H) ) res.push_back(make_pair(cur_X, cur_H));
}
return res;
}
};
```

# Java The Skyline Problem LeetCode Solution

```
``````
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
List<int[]> height = new ArrayList<>();
for(int[] b:buildings) {
height.add(new int[]{b[0], -b[2]});
height.add(new int[]{b[1], b[2]});
}
Collections.sort(height, (a, b) -> {
if(a[0] != b[0])
return a[0] - b[0];
return a[1] - b[1];
});
Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
int prev = 0;
for(int[] h:height) {
if(h[1] < 0) {
pq.offer(-h[1]);
} else {
pq.remove(h[1]);
}
int cur = pq.peek();
if(prev != cur) {
result.add(new int[]{h[0], cur});
prev = cur;
}
}
return result;
}
```

# Python 3 The Skyline Problem LeetCode Solution

```
``````
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
# for the same x, (x, -H) should be in front of (x, 0)
# For Example 2, we should process (2, -3) then (2, 0), as there's no height change
x_height_right_tuples = sorted([(L, -H, R) for L, R, H in buildings] + [(R, 0, "doesn't matter") for _, R, _ in buildings])
# (0, float('inf')) is always in max_heap, so max_heap[0] is always valid
result, max_heap = [[0, 0]], [(0, float('inf'))]
for x, negative_height, R in x_height_right_tuples:
while x >= max_heap[0][1]:
# reduce max height up to date, i.e. only consider max height in the right side of line x
heapq.heappop(max_heap)
if negative_height:
# Consider each height, as it may be the potential max height
heapq.heappush(max_heap, (negative_height, R))
curr_max_height = -max_heap[0][0]
if result[-1][1] != curr_max_height:
result.append([x, curr_max_height])
return result[1:]
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below