# The Skyline Problem LeetCode Solution | Easy Approach Share:

The Skyline Problem 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.

Time: O(nlogn)
Space: O(n)

### C++

`````` class Solution {
public:
vector<vector<int>> getSkyline(const vector<vector<int>>& buildings) {
const int n = buildings.size();
if (n == 0)
return {};
if (n == 1) {
const int left = buildings;
const int right = buildings;
const int height = buildings;
return {{left, height}, {right, 0}};
}

const auto left = getSkyline({begin(buildings), begin(buildings) + n / 2});
const auto right = getSkyline({begin(buildings) + n / 2, end(buildings)});
return merge(left, right);
}

private:
vector<vector<int>> merge(const vector<vector<int>>& left,
const vector<vector<int>>& right) {
vector<vector<int>> ans;
int i = 0;  // left's index
int j = 0;  // right's index
int leftY = 0;
int rightY = 0;

while (i < left.size() && j < right.size())
// choose the point with smaller x
if (left[i] < right[j]) {
leftY = left[i];  // update the ongoing leftY
} else {
rightY = right[j];  // update the ongoing rightY
}

while (i < left.size())

while (j < right.size())

return ans;
}

void addPoint(vector<vector<int>>& ans, int x, int y) {
if (!ans.empty() && ans.back() == x) {
ans.back() = y;
return;
}
if (!ans.empty() && ans.back() == y)
return;
ans.push_back({x, y});
}
};``````

### Java

`````` class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
final int n = buildings.length;
if (n == 0)
return new ArrayList<>();
if (n == 1) {
final int left = buildings;
final int right = buildings;
final int height = buildings;
List<List<Integer>> ans = new ArrayList<>();
return ans;
}

var leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
var rightSkyline = getSkyline(Arrays.copyOfRange(buildings, n / 2, n));
return merge(leftSkyline, rightSkyline);
}

private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
List<List<Integer>> ans = new ArrayList<>();
int i = 0; // left's index
int j = 0; // right's index
int leftY = 0;
int rightY = 0;

while (i < left.size() && j < right.size())
// choose the point with smaller x
if (left.get(i).get(0) < right.get(j).get(0)) {
leftY = left.get(i).get(1); // update the ongoing leftY
} else {
rightY = right.get(j).get(1); // update the ongoing rightY
}

while (i < left.size())

while (j < right.size())

return ans;
}

private void addPoint(List<List<Integer>> ans, int x, int y) {
if (!ans.isEmpty() && ans.get(ans.size() - 1).get(0) == x) {
ans.get(ans.size() - 1).set(1, y);
return;
}
if (!ans.isEmpty() && ans.get(ans.size() - 1).get(1) == y)
return;
}
}
``````

### Python

``````  class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
n = len(buildings)
if n == 0:
return []
if n == 1:
left, right, height = buildings
return [[left, height], [right, 0]]

left = self.getSkyline(buildings[:n // 2])
right = self.getSkyline(buildings[n // 2:])
return self._merge(left, right)

def _merge(self, left: List[List[int]], right: List[List[int]]) -> List[List[int]]:
ans = []
i = 0  # left's index
j = 0  # right's index
leftY = 0
rightY = 0

while i < len(left) and j < len(right):
# choose the powith smaller x
if left[i] < right[j]:
leftY = left[i]  # update the ongoing leftY
i += 1
else:
rightY = right[j]  # update the ongoing rightY
j += 1

while i < len(left):
i += 1

while j < len(right):
j += 1

return ans

def _addPoint(self, ans: List[List[int]], x: int, y: int) -> None:
if ans and ans[-1] == x:
ans[-1] = y
return
if ans and ans[-1] == y:
return
ans.append([x, y])
``````

#### Watch Tutorial

Checkout more Solutions here