The Skyline Problem

📋

The Skyline Problem

Edge cases:

</>

IDE

def getSkyline(buildings: list[list[int]]) -> list[list[int]]:public List<List<Integer>> getSkyline(int[][] buildings)vector<vector<int>> getSkyline(vector<vector<int>>& buildings)function getSkyline(buildings)

def getSkyline(buildings):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    // Write your solution here
    return {};
}

function getSkyline(buildings) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Missing key points where height changesNot updating skyline when max height changes after processing building edges✅ Add a key point whenever the current max height changes after processing each building edge

Wrong: Duplicate consecutive points with same heightAdding key points without checking if height changed from previous point✅ Only add a key point if the height differs from the previous key point's height

Wrong: Incorrect skyline for buildings with identical start and end pointsNot selecting the tallest building among buildings with same edges✅ When multiple buildings share the same start and end, pick the maximum height among them

Wrong: Timeout or crash on large inputsUsing brute force approach iterating over large coordinate ranges✅ Implement sweep line with max heap or divide and conquer algorithm with O(n log n) complexity

Wrong: Incorrect output or crash on empty inputNot handling empty input case explicitly✅ Add a guard clause to return empty list if input is empty

✓

Test Cases

Handle empty and single building inputs carefully to avoid crashes.

Test your solution against tricky overlapping cases and identical edges.

Optimize your solution to run efficiently on large inputs using advanced algorithms.

t1_01basic

Input{"buildings":[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]}

Expected[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

⏱ Performance - must finish in 2000ms

The skyline rises to 10 at x=2, then to 15 at x=3, drops to 12 at x=7, falls to 0 at x=12, rises again to 10 at x=15, drops to 8 at x=20, and finally falls to 0 at x=24.

💡 Consider sorting building edges and using a max heap to track heights.

💡 Use a sweep line algorithm with a priority queue to maintain current tallest building.

💡 Add key points when the max height changes after processing each edge.

Why it failed: Incorrect skyline output - likely missing updates when height changes or incorrect handling of overlapping buildings. Fix by ensuring to add a key point whenever the current max height changes after processing building edges.

✓ Correct skyline computed with proper handling of overlapping buildings and height changes.

t1_02basic

Input{"buildings":[[1,5,11],[2,7,6],[3,9,13],[12,16,7],[14,25,3],[19,22,18],[23,29,13],[24,28,4]]}

Expected[[1,11],[3,13],[9,0],[12,7],[16,3],[19,18],[22,3],[23,13],[29,0]]

⏱ Performance - must finish in 2000ms

Skyline rises to 11 at x=1, peaks at 13 at x=3, drops to 0 at x=9, rises to 7 at x=12, drops to 3 at x=16, peaks at 18 at x=19, drops to 3 at x=22, rises to 13 at x=23, and falls to 0 at x=29.

💡 Track building start and end points separately and process in sorted order.

💡 Use a max heap to keep track of current tallest building height efficiently.

💡 Update the skyline key points only when the max height changes after processing an event.

Why it failed: Output misses some key points or has incorrect heights - likely due to not handling building end events properly or failing to update max height after removals. Fix by processing both start and end edges and updating max height accordingly.

✓ Correctly handles multiple overlapping buildings and updates skyline at all critical points.

t2_01edge

Input{"buildings":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input means no buildings, so the skyline is empty.

💡 Check if the input list is empty before processing.

💡 Return an empty list immediately if no buildings are given.

💡 Add a guard clause at the start to handle empty input.

Why it failed: Function crashes or returns non-empty output on empty input. Fix by adding a check for empty input and returning an empty list immediately.

✓ Handles empty input gracefully by returning an empty skyline.

t2_02edge

Input{"buildings":[[0,1,5]]}

Expected[[0,5],[1,0]]

⏱ Performance - must finish in 2000ms

Single building creates a skyline with two points: rise at start and fall to zero at end.

💡 For a single building, the skyline is just two points: start height and end zero.

💡 Ensure to add both the start and end key points for single building input.

💡 Do not omit the final drop to zero after the building ends.

Why it failed: Output missing the final drop to zero or missing start point. Fix by adding both start and end key points for single building.

✓ Correctly outputs skyline for single building with start and end points.

t2_03edge

Input{"buildings":[[1,5,10],[1,5,15],[1,5,12]]}

Expected[[1,15],[5,0]]

⏱ Performance - must finish in 2000ms

Multiple buildings with same start and end but different heights; tallest building dominates the skyline.

💡 When buildings share the same start and end, only the tallest affects the skyline.

💡 Ensure to consider all buildings starting at the same point and pick max height.

💡 Use a max heap or sorting to handle multiple buildings with identical edges.

Why it failed: Skyline includes multiple points for same start/end or wrong height chosen. Fix by selecting max height among buildings with identical edges.

✓ Correctly outputs skyline dominated by tallest building among identical edges.

t2_04edge

Input{"buildings":[[1,3,0],[2,4,0]]}

Expected[]

⏱ Performance - must finish in 2000ms

Buildings with zero height should be ignored, resulting in empty skyline.

💡 Check for buildings with zero height and ignore them.

💡 Do not add key points for zero height buildings.

💡 Filter out zero height buildings before processing.

Why it failed: Output includes zero height buildings in skyline. Fix by filtering out buildings with zero height before processing.

✓ Correctly ignores zero height buildings resulting in empty skyline.

t3_01corner

Input{"buildings":[[1,3,4],[2,4,5],[3,5,3]]}

Expected[[1,4],[2,5],[4,3],[5,0]]

⏱ Performance - must finish in 2000ms

Overlapping buildings where greedy approach picking tallest building first fails to capture intermediate height changes.

💡 Greedy approach picking tallest building first may miss intermediate skyline changes.

💡 Use sweep line with max heap to track all active buildings and update skyline on height changes.

💡 Add key points whenever the max height changes after processing building edges.

Why it failed: Greedy approach outputs skyline missing intermediate height changes. Fix by using sweep line and max heap to track all active buildings and update skyline on every height change.

✓ Correctly handles overlapping buildings with intermediate height changes.

t3_02corner

Input{"buildings":[[1,2,1],[1,2,2],[1,2,3],[1,2,4]]}

Expected[[1,4],[2,0]]

⏱ Performance - must finish in 2000ms

Multiple buildings with same start and end but different heights; tests correct max height selection and no duplicate points.

💡 Ensure to pick the maximum height among buildings with identical edges.

💡 Avoid adding duplicate key points with same height consecutively.

💡 Use a max heap to maintain current tallest building efficiently.

Why it failed: Output has duplicate points or wrong max height for identical edges. Fix by selecting max height and avoiding duplicate consecutive points.

✓ Correctly outputs single peak for multiple identical edge buildings.

t3_03corner

Input{"buildings":[[0,2147483647,2147483647]]}

Expected[[0,2147483647],[2147483647,0]]

⏱ Performance - must finish in 2000ms

Tests handling of large coordinate and height values at boundary constraints.

💡 Use data types that can handle large integers without overflow.

💡 Avoid brute force approaches that iterate over large coordinate ranges.

💡 Implement efficient sweep line or divide and conquer algorithms.

Why it failed: Incorrect output or timeout due to overflow or brute force iteration over large range. Fix by using efficient algorithm and appropriate data types.

✓ Correctly handles large input values without overflow or timeout.

t4_01performance

Input{"buildings":[[0,5,1000000000],[10,15,999999999],[20,25,999999998],[30,35,999999997],[40,45,999999996],[50,55,999999995],[60,65,999999994],[70,75,999999993],[80,85,999999992],[90,95,999999991],[100,105,999999990],[110,115,999999989],[120,125,999999988],[130,135,999999987],[140,145,999999986],[150,155,999999985],[160,165,999999984],[170,175,999999983],[180,185,999999982],[190,195,999999981],[200,205,999999980],[210,215,999999979],[220,225,999999978],[230,235,999999977],[240,245,999999976],[250,255,999999975],[260,265,999999974],[270,275,999999973],[280,285,999999972],[290,295,999999971],[300,305,999999970],[310,315,999999969],[320,325,999999968],[330,335,999999967],[340,345,999999966],[350,355,999999965],[360,365,999999964],[370,375,999999963],[380,385,999999962],[390,395,999999961],[400,405,999999960],[410,415,999999959],[420,425,999999958],[430,435,999999957],[440,445,999999956],[450,455,999999955],[460,465,999999954],[470,475,999999953],[480,485,999999952],[490,495,999999951],[500,505,999999950],[510,515,999999949],[520,525,999999948],[530,535,999999947],[540,545,999999946],[550,555,999999945],[560,565,999999944],[570,575,999999943],[580,585,999999942],[590,595,999999941],[600,605,999999940],[610,615,999999939],[620,625,999999938],[630,635,999999937],[640,645,999999936],[650,655,999999935],[660,665,999999934],[670,675,999999933],[680,685,999999932],[690,695,999999931],[700,705,999999930],[710,715,999999929],[720,725,999999928],[730,735,999999927],[740,745,999999926],[750,755,999999925],[760,765,999999924],[770,775,999999923],[780,785,999999922],[790,795,999999921],[800,805,999999920],[810,815,999999919],[820,825,999999918],[830,835,999999917],[840,845,999999916],[850,855,999999915],[860,865,999999914],[870,875,999999913],[880,885,999999912],[890,895,999999911]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 buildings with large heights and non-overlapping intervals; algorithm must run in O(n log n) time within 2 seconds.

💡 Brute force approach iterating over coordinate range will time out.

💡 Use sweep line with max heap or divide and conquer for O(n log n) performance.

💡 Avoid iterating over all x-coordinates explicitly.

Why it failed: TLE due to brute force or inefficient approach with O(n * maxRight) complexity. Fix by implementing sweep line or divide and conquer algorithm with O(n log n) complexity.

✓ Efficient O(n log n) algorithm confirmed by passing performance test.

Practice

1. You need to design a stack data structure that supports the usual push and pop operations, but also an increment operation that adds a given value to the bottom k elements of the stack efficiently. Which approach guarantees the most optimal time complexity for a sequence of n operations?

easy

A. Use a balanced binary search tree to store elements and increments, allowing O(log n) updates and queries.

B. Directly increment the bottom k elements on each increment call, resulting in O(n*k) time for n operations.

C. Use a lazy increment array to record increments and propagate them during pop operations, achieving O(n) total time.

D. Maintain a prefix sum array of increments and update it on each increment call, applying increments during pop.

Solution

1. Step 1: Understand the problem constraints

   The increment operation must be efficient even when called multiple times, so directly incrementing bottom k elements each time (O(n*k)) is too slow.

2. Step 2: Recognize the lazy increment pattern

   Using an auxiliary array to store increments lazily and applying them during pop operations reduces total time to O(n), as increments are propagated only once per element.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Lazy increments avoid repeated updates, achieving O(n) total time [OK]

Hint: Lazy increments reduce repeated updates to O(n) total time [OK]

Common Mistakes:

• Directly incrementing elements each time causes TLE
• Using complex data structures unnecessarily

2. Consider the following Python code implementing an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys [2 (MRU), 1 (LRU)]. get(1) moves key 1 to MRU, order: [1,2]. put(3,3) evicts LRU key 2, cache: [3,1]. get(2) returns -1 (evicted). put(4,4) evicts LRU key 1, cache: [4,3].

2. Step 2: Evaluate get(1) after put(4,4)

   Key 1 was evicted, so get(1) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 1 evicted after put(4,4), so get(1) -> -1 [OK]

Hint: Remember to update usage order on get and evict LRU on put [OK]

Common Mistakes:

• Forgetting to move accessed node to front
• Evicting wrong node
• Returning wrong value after eviction

3. Given the following code snippet for SnapshotArray, what is the output of snapshotArr.get(0, 0) after executing all lines shown?

snapshotArr = SnapshotArray(3)
snapshotArr.set(0, 5)
snap_id = snapshotArr.snap()
snapshotArr.set(0, 6)
print(snapshotArr.get(0, 0))

easy

A. 5

B. 6

C. 0

D. Error due to invalid snap_id

Solution

1. Step 1: Trace set and snap operations

   Initially, data[0] = [(-1,0)]. After set(0,5), data[0] = [(-1,0),(0,5)] because snap_id=0. Then snap() increments snap_id to 1 and returns 0. Then set(0,6) appends (1,6) to data[0].

2. Step 2: Trace get(0,0)

   For snap_id=0, bisect_right finds insertion point for (0,inf) in data[0] = [(-1,0),(0,5),(1,6)]. It returns index 2, so i=1. data[0][1] = (0,5), so get returns 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Value at snap 0 is 5, not the later set 6 [OK]

Hint: Get returns value at or before snap_id using binary search [OK]

Common Mistakes:

• Returning latest value ignoring snap_id
• Off-by-one in bisect index

4. Consider the following buggy LFUCache get method. Which line contains the subtle bug that can cause incorrect eviction behavior?

def get(self, key: int) -> int:
    if key not in self.key_val_freq:
        return -1
    val, freq = self.key_val_freq[key]
    del self.freq_keys[freq][key]
    if not self.freq_keys[freq]:
        del self.freq_keys[freq]
        # BUG: missing update of min_freq here
    self.freq_keys[freq + 1][key] = None
    self.key_val_freq[key] = (val, freq + 1)
    return val

What is the bug?

medium

A. Missing update of min_freq after deleting freq_keys[freq]

B. Line deleting freq_keys[freq] when empty

C. Line deleting key from freq_keys[freq]

D. Line adding key to freq_keys[freq + 1]

Solution

1. Step 1: Identify the role of min_freq

   min_freq tracks the smallest frequency present in the cache, needed for correct eviction.

2. Step 2: Check frequency list deletion

   When freq_keys[freq] becomes empty and is deleted, if freq equals min_freq, min_freq must be incremented to freq + 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing min_freq update causes stale min_freq and wrong eviction [OK]

Hint: min_freq must update when freq list empties [OK]

Common Mistakes:

• Forgetting to update min_freq after freq list deletion
• Confusing key deletion with frequency list deletion
• Assuming min_freq updates automatically

5. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)