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;
}
};
Difficulty
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
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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++ |
Videos
Similar Problems
- problem 699: Falling Squares
Solved On The Same Day
- problem 175: Combine Two Tables
- problem 181: Employees Earning More Than Their Managers
- problem 182: Duplicate Emails
- problem 183: Customers Who Never Order
- problem 193: Valid Phone Numbers
- problem 196: Delete Duplicate Emails
- problem 197: Rising Temperature
- problem 203: Remove Linked List Elements
- problem 511: Game Play Analysis I
- problem 577: Employee Bonus
- problem 584: Find Customer Referee
- problem 586: Customer Placing the Largest Number of Orders
- problem 595: Big Countries
- problem 596: Classes With at Least 5 Students
- problem 607: Sales Person
- problem 610: Triangle Judgement
- problem 619: Biggest Single Number
- problem 620: Not Boring Movies
- problem 627: Swap Sex of Employees
- problem 1050: Actors and Directors Who Cooperated At Least Three Times
- problem 1068: Product Sales Analysis I
- problem 1075: Project Employees I
- problem 1084: Sales Analysis III
- problem 1141: User Activity for the Past 30 Days I
- problem 1148: Article Views I
- problem 1179: Reformat Department Table
- problem 176: Second Highest Salary
- problem 177: Nth Highest Salary
- problem 178: Rank Scores
- problem 180: Consecutive Numbers
- problem 184: Department Highest Salary
- problem 192: Word Frequency
- problem 194: Transpose File
- problem 550: Game Play Analysis IV
- problem 570: Managers with at Least 5 Direct Reports
- problem 585: Investments in 2016
- problem 602: Friend Requests II: Who Has the Most Friends
- problem 608: Tree Node
- problem 626: Exchange Seats
- problem 725: Split Linked List in Parts
- problem 1045: Customers Who Bought All Products
- problem 1070: Product Sales Analysis III
- problem 1164: Product Price at a Given Date
- problem 1174: Immediate Food Delivery II
- problem 1193: Monthly Transactions I
- problem 1204: Last Person to Fit in the Bus
- problem 1321: Restaurant Growth
- problem 1393: Capital Gain/Loss
- problem 174: Dungeon Game
- problem 185: Department Top Three Salaries
- problem 262: Trips and Users
- problem 601: Human Traffic of Stadium
Extra
- 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