Problem 218

Abstract / Summary

Given a list of buildings each defined by left right and height output the skyline showing the outline formed by the tops of the buildings.

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 0218.cpp

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> result;

        multimap<int, int> changes; // y => last x
        set<int> walls;
        for (const auto& b : buildings)
        {
            changes.insert(make_pair(b[0], +b[2])); // start
            changes.insert(make_pair(b[1], -b[2])); // end
            walls.insert(b[0]);
            walls.insert(b[1]);
        }

        map<int, int> y;
        y[0] = 1; // ground
        int last = 0;

        // merge
        for (auto x : walls)
        {
            auto same = changes.equal_range(x);
            for (auto i = same.first; i != same.second; i++)
            {
                auto height = i->second;
                if (height > 0)
                    y[height]++;
                else
                {
                    auto posHeight = -height;
                    y[posHeight]--;
                    if (y[posHeight] == 0)
                        y.erase(posHeight);
                }
            }

            int high = y.rbegin()->first;
            if (last == high)
                continue;

            result.push_back({ x, high });
            last = high;
        }

        return result;
    }
};
48 lines | 1311 bytes | submitted September 6, 2023 | GitHub   12% comment ratio | tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 46% (700k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Binary Indexed Tree
  • Divide And Conquer
  • Heap (Priority Queue)
  • Ordered Set
  • Segment Tree
  • Sorting
  • Sweep Line
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The implementation computes the skyline of a collection of rectangular buildings using a sweep-line technique. It first transforms each building into two height change events (entering and leaving) and records every distinct x-coordinate that marks a wall. While moving from left to right across the sorted wall positions, it updates a multiset-like structure that tracks how many times each height is currently active. The highest active height after each wall determines whether a new key point belongs in the skyline. The result is a list of (x, height) pairs that describe the outer contour.

Transforming Buildings into Events

For every building the code creates a positive height entry at the left edge and a negative height entry at the right edge. These pairs are stored in a multimap<int,int> named changes, where the key is the x-coordinate and the value encodes the height change. At the same time all wall positions are collected in a set<int> called walls so that they can be processed in sorted order.

for (const auto& b : buildings)
{
    changes.insert(make_pair(b[0], +b[2])); // start
    changes.insert(make_pair(b[1], -b[2])); // end
    walls.insert(b[0]);
    walls.insert(b[1]);
}

The use of a multimap allows multiple events to share the same x-coordinate, preserving all height modifications that occur at that location.

Maintaining Active Heights

A map<int,int> named y holds the current count of each active height. The map is ordered by height, which makes the greatest height readily accessible via rbegin(). The ground level is seeded with a height of zero and a count of one, guaranteeing that the map is never empty.

map<int, int> y;
y[0] = 1; // ground
int last = 0;

When the sweep line reaches a wall coordinate, the code retrieves the range of events that share that x-value and updates the active height map accordingly. Positive entries increment the count for that height; negative entries decrement the count and erase the height entry when its count drops to zero.

auto same = changes.equal_range(x);
for (auto i = same.first; i != same.second; i++)
{
    auto height = i->second;
    if (height > 0)
        y[height]++;
    else
    {
        auto posHeight = -height;
        y[posHeight]--;
        if (y[posHeight] == 0)
            y.erase(posHeight);
    }
}

Determining Skyline Key Points

After processing all events at a given wall, the current maximum height is obtained from the reverse iterator of the map. If this height differs from the height of the previously recorded key point, a new point is appended to the result vector.

int high = y.rbegin()->first;
if (last == high)
    continue;

result.push_back({ x, high });
last = high;

The variable last stores the height of the most recent skyline point, preventing duplicate entries when the height remains unchanged across consecutive walls.

Edge Cases Handled

The algorithm correctly handles multiple buildings that start or end at the same x-coordinate because all events for that coordinate are processed together before the height is queried. Overlapping buildings with different heights are managed by the count-based map, which ensures that a height persists as long as at least one building of that height is active. When the last building at a particular height ends, the corresponding entry is removed, allowing the next lower height to become the new maximum. The ground level entry guarantees that the skyline always returns to height zero after the final building, even if no explicit event lowers the height to zero.

Performance Optimizations

Using a set for wall positions provides an automatically sorted collection without duplicate entries, eliminating the need for an explicit sort step. The multimap groups events by x-coordinate, enabling batch updates at each wall and reducing the number of map lookups. The active height map stores counts rather than individual instances of heights, which keeps its size bounded by the number of distinct heights rather than the total number of active buildings. Accessing the current maximum height via rbegin() is an O(1) operation on the ordered map, avoiding a linear scan of all active heights at each step. Together, these choices keep the sweep line iteration efficient while preserving correctness.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a big pile of wooden building blocks standing on the floor. Some are tall and some are short, and they are all lined up in a row. This code is like a little helper who walks along the edge of the city to draw a picture of the top shape of all the blocks stacked together.

First, the helper looks at every block to see exactly where it starts on the left and where it ends on the right. The helper makes a list of all these special spots because those are the only places where the shape of the skyline might change.

Then, the helper starts a long walk from the very beginning to the very end of the city. At every spot where a block starts, the helper remembers that a new building is joining the group. If a block ends, the helper remembers that one of the buildings is being taken away.

Because many buildings might be standing in the same place at the same time, the helper keeps track of all their heights in a special box. Every time the helper reaches a spot, they check which building is currently the tallest one in that box. If the tallest height changes compared to the spot just before it, the helper writes down that new height and the current location. This creates a neat outline of the tallest parts of all the buildings without needing to worry about the ones hiding underneath. By the time the helper finishes walking, they have a complete list of all the points that make the outline of the city skyline.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 6.62 | σ = 1.57

Complexity Analysis

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Rust Go
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github aylei Rust
BigEggStudy C#
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
FelixFan1122 C#
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
linouk23 C++
lkwq007 Python
lzl124631x C++
MacJim C++
ruoru Rust
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, Rust
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
aylei Rust
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
FelixFan1122 C#
gaosq0604 Python
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
linouk23 C++
lkwq007 Python
lzl124631x C++
MacJim C++
ruoru Rust
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
zfang399 C++
45 links | 32 authors | 9 languages

Videos

16 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

26 easy 22 medium 4 hard
53 solutions   September 6, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality