305. The Skyline Problem
🔗 LeetCode Problem: 218. The Skyline Problem
📊 Difficulty: Hard
🏷️ Topics: Array, Divide and Conquer, Heap (Priority Queue), Sorting, Segment Tree, Line Sweep
Problem Statement
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]]
Example 2:
Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]
Constraints:
- 1 <= buildings.length <= 10^4
- 0 <= lefti < righti <= 2^31 - 1
- 1 <= heighti <= 2^31 - 1
- buildings is sorted by lefti in non-decreasing order.
🌳 Visual Understanding - Building Intuition from Scratch
Let's Discover the Problem Together:
Imagine you're standing far away from a city, looking at building silhouettes:
What you see is NOT individual buildings, but their OUTLINE
Individual buildings:
15| ┌───┐
| │ B │
12| │ B ├───────┐
| │ B │ C │
10| ┌──┤ A │ C ├───┐
| │A │ B │ C │ D │
8| │A │ B │ C │ D ├───┐
| │A │ B │ C │ D │ E │
0|──┴──┴───┴───────┴───┴───┴──
0 2 3 5 7 9 12 15 19 20 24
But you only see the OUTER CONTOUR (skyline):
15| ┌───┐
| │ │
12| │ ├───────┐
| │ │
10| ┌──┤ ├───┐
| │ │
8| │ ├───┐
| │ │
0|──┴──────────────────────┴──
2 3 5 7 9 12 15 20 24
Key insight: Buildings can HIDE each other!
The Problem We're Solving:
Buildings: [[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]
Let me walk you through DISCOVERING the solution:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
QUESTION 1: When does the skyline HEIGHT change?
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Let's think... Height changes when:
- A new building STARTS (might make it taller)
- A building ENDS (might make it shorter)
Between these events? Height stays SAME!
So we only need to check at building START and END points!
This is the FIRST KEY INSIGHT! 🔑
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
QUESTION 2: What is the skyline height at any point?
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
If multiple buildings overlap at point x:
Skyline height = MAXIMUM height at that point!
Example at x=5:
Building A [2,9,10]: height=10 ✓
Building B [3,7,15]: height=15 ✓ (but ends at 7)
Building C [5,12,12]: height=12 ✓
Skyline height at x=5 = max(10,15,12) = 15
So we need to track MAXIMUM of all active buildings!
This is the SECOND KEY INSIGHT! 🔑
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
QUESTION 3: How do we track the maximum efficiently?
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
As we move left to right:
- Buildings START → add their height
- Buildings END → remove their height
- Need current MAX at any time
What data structure?
❌ Simple variable: Can't track multiple heights
❌ Array: Finding max is O(n)
✓ TreeMap/MultiSet: Can get max in O(1), add/remove in O(log n)!
This is the THIRD KEY INSIGHT! 🔑
Let's Walk Through an Example Step by Step:
Buildings: [[2,9,10], [3,7,15]]
Think of this as EVENTS on a timeline:
Timeline:
0 1 2 3 4 5 6 7 8 9 10
↑ ↑ ↑ ↑
START START END END
10 15 15 10
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
At x=2: Building height 10 STARTS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Active heights: {10}
Maximum height: 10
Previous max: 0
Height CHANGED from 0 to 10!
Record key point: (2, 10) ✓
Visualization:
10| ┌──
0|──┴
2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
At x=3: Building height 15 STARTS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Active heights: {10, 15}
Maximum height: 15
Previous max: 10
Height CHANGED from 10 to 15!
Record key point: (3, 15) ✓
Visualization:
15| ┌
10| ┌──┤
0|──┴
2 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
At x=7: Building height 15 ENDS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Active heights: {10} (removed 15)
Maximum height: 10
Previous max: 15
Height CHANGED from 15 to 10!
Record key point: (7, 10) ✓
Visualization:
15| ┌───┐
10| ┌──┤ ├──
0|──┴
2 3 7
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
At x=9: Building height 10 ENDS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Active heights: {} (removed 10)
Maximum height: 0 (ground)
Previous max: 10
Height CHANGED from 10 to 0!
Record key point: (9, 0) ✓
Visualization:
15| ┌───┐
10| ┌──┤ ├──┐
0|──┴ ┴──
2 3 7 9
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL SKYLINE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Key points: [[2,10], [3,15], [7,10], [9,0]]
These are the points where height CHANGES! ✓
Understanding Key Points:
Key point = (x, height) where skyline height changes
NOT every x-coordinate, only where CHANGES occur!
Why record changes?
- Between changes, height is constant
- No need to record constant segments
- Just record transition points!
Why This is Hard - The Tricky Cases:
TRICKY CASE 1: Same x-coordinate
Buildings: [[0,2,3], [2,4,3]]
START START
At x=2: Building 1 ENDS, Building 2 STARTS
Both have height 3!
Height doesn't change (3 → 3)
DON'T record a key point!
This is why we check: currentMax != prevMax
TRICKY CASE 2: Multiple buildings at same x
Buildings: [[0,3,3], [1,3,3], [2,3,3]]
START START START
At x=0, x=1, x=2: Multiple buildings start
All have height 3!
Height changes: 0 → 3 (only record at x=0)
At x=1, x=2: 3 → 3 (no change, don't record!)
TRICKY CASE 3: Building completely inside another
Buildings: [[1,5,5], [2,3,3]]
5| ┌─────┐
3| │ ┌─┐ │
0|──┴─┴─┴─┴──
1 2 3 5
At x=2: Start building height 3
But max is still 5 (outer building)
Height doesn't change (5 → 5)
DON'T record!
At x=3: End building height 3
Max is still 5 (outer building)
Height doesn't change (5 → 5)
DON'T record!
This is why tracking MAXIMUM is crucial!
Key Observations:
1. Buildings can OVERLAP
Multiple buildings at same x-coordinate
Skyline height = max of all active buildings
2. Must track ACTIVE buildings
When building starts: add to active set
When building ends: remove from active set
Current height = max height in active set
3. Only record when height CHANGES
Not every x-coordinate, only where height changes
4. This is a LINE SWEEP problem
Process events (building starts/ends) from left to right
Track maximum height as we go
🧠 Discovering the Solution - Intuitive Approach
Let's Think Through This Problem Step by Step:
Starting Point: What do we need?
Output: List of (x, height) where height changes
So we need to:
1. Process events chronologically (left to right)
2. Track current skyline height at each event
3. Record when height changes
Question 1: What are the "events"?
Events = Building START and END points
For building [left, right, height]:
- Event 1: Building STARTS at x = left
- Event 2: Building ENDS at x = right
Example: [2, 9, 10]
- START event at x=2 with height 10
- END event at x=9 with height 10
Question 2: How to represent events?
Simple idea: (x-coordinate, type, height)
- START: (left, "START", height)
- END: (right, "END", height)
But there's a CLEVER TRICK!
Use NEGATIVE height for START events:
- START: (left, -height)
- END: (right, +height)
Why negative? For sorting! (explained below)
Question 3: What order to process events?
Sort by x-coordinate (left to right)
But what if TWO events at SAME x?
Critical case: Building ends and another starts at SAME x
Example: [0,2,3] and [2,5,3]
At x=2: Building 1 ENDS, Building 2 STARTS
If we process END first:
Height: 3 → 0 → 3 (records TWO key points!)
Wrong: [[0,3], [2,0], [2,3]] ✗
If we process START first:
Height: 3 → 3 (no change!)
Correct: [[0,3], [5,0]] ✓
So: START before END at same x-coordinate!
How does negative height help?
START: (2, -3)
END: (2, +3)
When sorting: -3 < 3, so START comes first automatically! ✨
This is a CLEVER SORTING TRICK!
Question 4: How to track active building heights?
Need a data structure that can:
1. Add a height (when building starts)
2. Remove a height (when building ends)
3. Get current MAXIMUM height (for skyline)
Options:
❌ Simple variable: Can't track multiple heights
❌ Array: Finding max is O(n) every time
❌ PriorityQueue: Can't remove arbitrary elements efficiently!
✓ TreeMap with counts: Perfect!
TreeMap<Integer, Integer>:
- Key: height (sorted in DESCENDING order)
- Value: count of buildings with that height
- firstKey(): gives maximum height in O(1)!
- add/remove: O(log n)
Why counts?
Multiple buildings can have SAME height!
Can't just remove - might still have others with that height!
Question 5: When to record a key point?
After processing each event:
1. Update active heights (add or remove)
2. Get current maximum height
3. If max CHANGED from previous: record key point!
Pseudocode:
prevMax = 0
for each event:
if START: add height
if END: remove height
currentMax = heights.firstKey()
if currentMax != prevMax:
result.add([x, currentMax])
prevMax = currentMax
The Complete Algorithm (Discovered!):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Create Events
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For each building [left, right, height]:
Create START: (left, -height)
Create END: (right, height)
Negative for START ensures START before END when sorting!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Sort Events
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Sort by:
1. x-coordinate (ascending)
2. Height value (negative START comes before positive END)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 3: Process Events with TreeMap
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initialize:
heights = TreeMap (descending order)
heights.put(0, 1) // Ground level
prevMax = 0
For each event (x, h):
if h < 0: // START
h = -h
heights.put(h, heights.getOrDefault(h, 0) + 1)
else: // END
count = heights.get(h) - 1
if count == 0:
heights.remove(h)
else:
heights.put(h, count)
currentMax = heights.firstKey()
if currentMax != prevMax:
result.add([x, currentMax])
prevMax = currentMax
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
DONE!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
🔴 Approach 1: Brute Force (For Understanding)
💡 Intuition
Check every x-coordinate:
Find maximum height at that point
Record when it changes
Simple but inefficient!
📊 Complexity Analysis
Time Complexity: O(n × range)
n = number of buildings
range = max(right) - min(left)
For each x in range: O(range)
Check all buildings: O(n)
Total: O(n × range)
Can be O(n × 10^9) - TOO SLOW!
Why we won't implement: - Too slow for large ranges - Better approach exists
🟢 Approach 2: Line Sweep + Priority Queue (Optimal)
💡 Intuition - The Line Sweep Algorithm
Don't check every x-coordinate!
Only process CRITICAL POINTS where something changes!
Critical points = building edges (starts and ends)
Use priority queue (max-heap) to track active heights:
- When building starts: add height to heap
- When building ends: remove height from heap
- Current skyline = max height in heap
- Record key point when max changes
This is O(n log n) - much better! 🎯
🎨 Building the Complete Solution
Step 1: Create Events
For each building [left, right, height]:
Create START event: (left, height, START)
Create END event: (right, height, END)
Sort all events by x-coordinate
If same x: process START before END (important!)
Step 2: Process Events with Max-Heap
Initialize:
maxHeap = {0} (ground level)
prevHeight = 0
result = []
For each event in sorted order:
If START:
Add height to maxHeap
If END:
Remove height from maxHeap
currentMax = maxHeap.top()
If currentMax != prevHeight:
Add [x, currentMax] to result
prevHeight = currentMax
Step 3: Handle Edge Cases
- Multiple buildings at same x
- Buildings with same height
- Adjacent buildings of different heights
- Removing from heap (need multiset/map)
📝 Implementation - Using TreeMap for Heights
import java.util.*;
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<List<Integer>> result = new ArrayList<>();
// Step 1: Create events
List<int[]> events = new ArrayList<>();
for (int[] building : buildings) {
int left = building[0];
int right = building[1];
int height = building[2];
// Start event: negative height to process before end
events.add(new int[]{left, -height});
// End event: positive height
events.add(new int[]{right, height});
}
// Step 2: Sort events
Collections.sort(events, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0]; // Sort by x-coordinate
}
return a[1] - b[1]; // If same x, negative (start) comes first
});
// Step 3: Process events with TreeMap (acts as multiset)
TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
heightMap.put(0, 1); // Ground level
int prevMaxHeight = 0;
for (int[] event : events) {
int x = event[0];
int height = Math.abs(event[1]);
if (event[1] < 0) {
// Start event: add height
heightMap.put(height, heightMap.getOrDefault(height, 0) + 1);
} else {
// End event: remove height
int count = heightMap.get(height);
if (count == 1) {
heightMap.remove(height);
} else {
heightMap.put(height, count - 1);
}
}
// Current max height
int currentMaxHeight = heightMap.firstKey();
// If height changed, add key point
if (currentMaxHeight != prevMaxHeight) {
result.add(Arrays.asList(x, currentMaxHeight));
prevMaxHeight = currentMaxHeight;
}
}
return result;
}
}
🔍 Complete Dry Run - Example 1 (Simplified)
Input: buildings = [[2,9,10], [3,7,15]]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Create events
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Building [2,9,10]:
(2, -10) - start
(9, 10) - end
Building [3,7,15]:
(3, -15) - start
(7, 15) - end
Events: [(2,-10), (9,10), (3,-15), (7,15)]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Sort events
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
After sorting: [(2,-10), (3,-15), (7,15), (9,10)]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 3: Process events
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initialize:
heightMap = {0: 1}
prevMaxHeight = 0
Event 1: (2, -10) - START at x=2, height=10
Add height 10 to map
heightMap = {10: 1, 0: 1}
currentMax = 10 (max key)
Changed? 10 != 0? YES
Add key point: [2, 10]
prevMaxHeight = 10
Event 2: (3, -15) - START at x=3, height=15
Add height 15 to map
heightMap = {15: 1, 10: 1, 0: 1}
currentMax = 15
Changed? 15 != 10? YES
Add key point: [3, 15]
prevMaxHeight = 15
Event 3: (7, 15) - END at x=7, height=15
Remove height 15 from map
heightMap = {10: 1, 0: 1}
currentMax = 10
Changed? 10 != 15? YES
Add key point: [7, 10]
prevMaxHeight = 10
Event 4: (9, 10) - END at x=9, height=10
Remove height 10 from map
heightMap = {0: 1}
currentMax = 0
Changed? 0 != 10? YES
Add key point: [9, 0]
prevMaxHeight = 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Output: [[2,10], [3,15], [7,10], [9,0]] ✓
📊 Complexity Analysis
Time Complexity: O(n log n)
Create events: O(n)
Sort events: O(n log n)
Process events: O(n log n)
Each event: O(log n) for TreeMap operations
Total: O(n log n)
OPTIMAL! 🎯
Space Complexity: O(n)
Events array: O(n)
TreeMap: O(n) in worst case
Result: O(n)
🎯 Key Insights Summary
The Four Critical Points:
1. Line Sweep Algorithm
Don't check every x-coordinate!
Only process CRITICAL EVENTS:
- Building starts
- Building ends
This reduces from O(range) to O(n) points! 🔑
2. Track Active Building Heights
Use max-heap (or TreeMap) to track heights:
- Current skyline = maximum active height
- Efficiently get max in O(log n)
- Add/remove heights as buildings start/end
This is the KEY data structure! ✓
3. Negative Heights for Event Ordering
Trick: Use negative heights for START events
Why?
When same x-coordinate:
START before END (to avoid spurious key points)
Sorting by (x, height):
(3, -15) comes before (3, 10)
START processes first!
Clever sorting technique! 🎯
4. Only Record Height Changes
Don't record every event!
Only when maximum height CHANGES
This gives us actual skyline key points
And avoids redundant points! ✓
💡 Why This Approach Works - Deep Intuition
The Line Sweep Concept:
Imagine a vertical line sweeping left to right:
At each critical point (building edge):
- Update active buildings
- Check current maximum height
- Record if height changed
This captures all height changes without checking every x!
Like scanning a bar code - only care about transitions! 📊
Why TreeMap (Not Simple Heap):
Problem with PriorityQueue:
- Can't efficiently remove arbitrary elements
- Building ends require removal
Solution: TreeMap with counts
- Key = height (sorted descending)
- Value = count of buildings with that height
- firstKey() = maximum height
- Can increment/decrement counts
Perfect for this problem! ✓
⚠️ Common Mistakes
// Mistake 1: Wrong event ordering
Collections.sort(events, (a, b) -> a[0] - b[0]); // ❌ Misses height tie-break
// ✓ CORRECT: Handle same x-coordinate
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1]; // Negative (start) before positive (end)
// Mistake 2: Using PriorityQueue without remove support
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(); // ❌ Can't remove efficiently
// ✓ CORRECT: Use TreeMap with counts
TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
// Mistake 3: Recording every event
result.add(Arrays.asList(x, currentMaxHeight)); // ❌ Every time!
// ✓ CORRECT: Only when height changes
if (currentMaxHeight != prevMaxHeight) {
result.add(Arrays.asList(x, currentMaxHeight));
}
// Mistake 4: Forgetting ground level
TreeMap<Integer, Integer> heightMap = new TreeMap<>(); // ❌ Empty initially
// ✓ CORRECT: Initialize with 0
heightMap.put(0, 1);
// Mistake 5: Not handling duplicate heights
heightMap.put(height, 1); // ❌ Overwrites existing!
// ✓ CORRECT: Use count
heightMap.put(height, heightMap.getOrDefault(height, 0) + 1);
📝 Quick Revision Notes
🎯 Core Concept
Problem: Find skyline from overlapping buildings
Key Insight: Line sweep + max-heap for active heights!
Algorithm: 1. Create events (start/end) for each building 2. Sort events by x (start before end at same x) 3. Process events: add/remove heights from TreeMap 4. Record key point when max height changes
Why It Works: Only process critical points, track max efficiently!
🔑 Key Points
✓ Line sweep: process events not every x
✓ Events: (x, -height) for start, (x, height) for end
✓ Negative height ensures start before end
✓ TreeMap: max height with counts
✓ Record only when height changes
✓ Time: O(n log n), Space: O(n)
🎪 Memory Aid
"Sweep the line, events we find!"
"Heights we track, max aligned!"
"Changes record, skyline defined!"
"TreeMap keeps, sorted and refined!" ✨
Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.TreeMap;
public class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
return sweepAndHeap(buildings);
}
private List<List<Integer>> sweepAndHeap(int[][] buildings) {
List<List<Integer>> result = new ArrayList<>();
// step 1: lets create events
// start/left is an event and end/right is an event.
// why -ve height for start?
List<int[]> events = new ArrayList<>();
for (int[] building : buildings) {
int left = building[0];
int right = building[1];
int height = building[2];
// start or left event
events.add(new int[] { left, -height });
// end or right event
events.add(new int[] { right, height });
}
// step 2: sort based on left/start or right/end
Collections.sort(events, (e1, e2) -> {
if (e1[0] != e2[0]) {
return e1[0] - e2[0];
} else {
return e1[1] - e2[1];
}
});
// step 3: map that stores height of buildings in descending
// order (like a max heap)
// But, since buildings may have same height, we need to maintain
// its count also. So, when its polled, we can simply reduce count.
// This type of requirement is satisfied by TreeMap
TreeMap<Integer, Integer> heightsMap = new TreeMap<>(Collections.reverseOrder());
// step 4: initialize (buildings with 0 heights)
heightsMap.put(0, 1);
int prevMaxHeight = 0;
// step 5: process the events now
for (int[] event : events) {
int height = Math.abs(event[1]);
if (event[1] < 0) {
// step 6a: start event - new building started
// simply add it to heightsMap
heightsMap.put(height, heightsMap.getOrDefault(height, 0) + 1);
} else {
// step 6b: end event - some building ended
// simply decrease its count or remove it from heightsMap if 0 count.
int count = heightsMap.get(height);
if (count == 1) {
heightsMap.remove(height);
} else {
heightsMap.put(height, count - 1);
}
}
// step 7: check if prevMaxHeight is still curr max height.
int currMaxHeight = heightsMap.firstKey(); // gives curr max height in map
if (prevMaxHeight != currMaxHeight) {
result.add(Arrays.asList(event[0], currMaxHeight));
prevMaxHeight = currMaxHeight;
}
}
return result;
}
public static void main(String[] args) {
Solution s = new Solution();
// [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
System.out.println(
s.getSkyline(new int[][] { { 2, 9, 10 }, { 3, 7, 15 }, { 5, 12, 12 }, { 15, 20, 10 }, { 19, 24, 8 } }));
}
}
🎉 Congratulations!
You've mastered The Skyline Problem - a HARD problem!
What You Learned:
✅ Line sweep algorithm - Process critical points
✅ Event-based thinking - Starts and ends
✅ Priority queue with counts - TreeMap usage
✅ Clever event sorting - Negative heights
✅ Height change detection - Key point logic
The Beautiful Insight:
Complex Geometric Problem → Line Sweep + Heap
The core insight:
"Don't check every x-coordinate"
"Only process where something changes"
Line Sweep:
Sweep left to right
Process building edges (critical points)
Track active buildings efficiently
Data Structure:
TreeMap with counts
Max height in O(log n)
Add/remove heights dynamically
This reduces O(n × range) to O(n log n)!
This line sweep pattern appears in:
- Computational geometry
- Interval problems
- Range queries
- Scheduling problems
Master this = Solve complex spatial problems! ✨
Interview Mastery:
When asked about Skyline Problem:
1. Understand: "Find skyline key points from buildings"
2. Clarify: "Key points are where height changes, right?"
3. Brute force: "Could check every x - O(n × range), too slow!"
4. Key insight: "Use line sweep! Process building edges only.
Track active building heights with TreeMap."
5. Events: "Create start/end events for each building.
Use negative height for starts (sort before ends)."
6. Algorithm: "Sort events. For each:
- Add/remove height from TreeMap
- Check current max
- Record if max changed"
7. Why TreeMap: "Need max height with ability to remove.
TreeMap with counts perfect!"
8. Code it: O(n log n) solution
9. Complexity: "O(n log n) - sorting and TreeMap ops.
O(n) space for events and map."
Shows mastery of hard problem! 💯
You've conquered a HARD problem using advanced techniques: line sweep + sophisticated data structure! This is interview gold! 🚀✨🎯