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 data structure that supports incrementing and decrementing string keys, and retrieving a key with the maximum or minimum count, all in constant time. Which approach best guarantees O(1) time complexity for all these operations?

easy

A. Using a balanced binary search tree keyed by counts to maintain order of keys

B. Using a hash map to store counts and scanning all keys to find max/min when requested

C. Maintaining a doubly linked list of buckets, each bucket holding keys with the same count, plus hash maps for quick access

D. Using a priority queue to track max and min keys with lazy updates

Solution

1. Step 1: Understand operation requirements

   Increment, decrement, getMaxKey, and getMinKey must all be O(1).

2. Step 2: Evaluate approaches

   Hash map + linear scan (B) is O(n) for max/min. Balanced BST (C) and priority queue (D) have O(log n) operations. Doubly linked list with buckets and hash maps (A) supports O(1) updates and retrievals.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bucket list + hash maps enable O(1) increments, decrements, and max/min retrievals [OK]

Hint: Bucket list + hash maps enable O(1) max/min updates [OK]

Common Mistakes:

• Thinking balanced BST or priority queue can achieve O(1) for all operations

2. You need to design a data structure that supports adding intervals, removing intervals, and querying whether a given range is fully covered by the added intervals. Which approach guarantees efficient updates and queries with logarithmic time complexity per operation?

easy

A. Use a balanced binary search tree (e.g., TreeMap) to store and merge intervals, enabling logarithmic time operations.

B. Use a brute force list of intervals and scan all intervals for each operation.

C. Use dynamic programming to precompute coverage for all possible ranges.

D. Use a greedy algorithm that always merges intervals only when queried.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support add, remove, and query operations on intervals efficiently.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n) per operation, which is inefficient. DP is not suitable for dynamic interval updates. Greedy merging only on query delays merging and leads to inefficient queries. Balanced BST with interval merging maintains sorted intervals and merges overlapping ones, supporting O(log n) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with merging -> O(log n) per operation [OK]

Hint: Balanced BST with merging enables efficient interval operations [OK]

Common Mistakes:

• Thinking DP or greedy solves dynamic interval updates efficiently

3. Identify the bug in the following LRU Cache implementation snippet that causes incorrect eviction behavior when capacity is exceeded:

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        self._remove(self.cache[key])
    node = Node(key, value)
    self._add(node)
    self.cache[key] = node
    if len(self.cache) > self.capacity:
        lru = self.head.next  # Bug here
        self._remove(lru)
        del self.cache[lru.key]

medium

A. Evicting the node at head.next instead of tail.prev

B. Removing node from cache before adding new node

C. Not updating the cache dictionary after eviction

D. Not checking if capacity is zero before eviction

Solution

1. Step 1: Understand eviction logic

   Eviction must remove the least recently used node, which is at tail.prev, not head.next.

2. Step 2: Identify bug

   Code incorrectly evicts head.next, which is the most recently used node, causing wrong eviction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Evicting head.next breaks LRU policy, must evict tail.prev [OK]

Hint: LRU node is at tail.prev, not head.next [OK]

Common Mistakes:

• Evicting MRU instead of LRU
• Forgetting to delete from cache dict
• Not handling zero capacity

4. Suppose the multilevel doubly linked list can have cycles introduced via child pointers (i.e., a child pointer may point to an ancestor node). Which modification to the flattening algorithm is necessary to handle this safely?

hard

A. Use recursion with a depth limit to prevent stack overflow on cycles.

B. Remove all child pointers before flattening to guarantee acyclic structure.

C. Use a hash set to track visited nodes and skip already visited ones to avoid infinite loops.

D. No modification needed; the existing in-place iterative approach handles cycles naturally.

Solution

1. Step 1: Understand the problem with cycles

   Cycles cause infinite loops during traversal if nodes are revisited.

2. Step 2: Identify safe traversal method

   Tracking visited nodes with a hash set prevents revisiting and infinite loops.

3. Step 3: Evaluate other options

   Removing child pointers loses structure; recursion depth limit is unreliable; existing code does not detect cycles.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Visited set prevents infinite loops in cyclic graphs [OK]

Hint: Track visited nodes to handle cycles safely [OK]

Common Mistakes:

• Assuming no cycles exist in input
• Relying on recursion depth limits
• Ignoring cycle detection altogether

5. Suppose the data structure must now support a new operation: getRandomWeighted(), which returns a random element with probability proportional to the number of times it appears (its frequency). Which modification to the optimized Insert Delete GetRandom O(1) with duplicates data structure is correct to support this efficiently?

hard

A. Maintain a list with each element repeated as many times as its frequency; getRandomWeighted() picks uniformly from this list.

B. Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove.

C. Use the existing list and hash map without changes; getRandomWeighted() is same as getRandom().

D. Store frequencies in a balanced BST and perform weighted random selection by traversing the tree.

Solution

1. Step 1: Understand weighted random requirements

   getRandomWeighted() must return elements with probability proportional to their frequency.

2. Step 2: Evaluate options

   Maintain a list with each element repeated as many times as its frequency; getRandomWeighted() picks uniformly from this list. duplicates elements in list, causing O(n) space and slow updates. Use the existing list and hash map without changes; getRandomWeighted() is same as getRandom(). ignores weighting. Store frequencies in a balanced BST and perform weighted random selection by traversing the tree. adds complexity and O(log n) operations. Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove. maintains frequencies and prefix sums, enabling O(log n) or better weighted sampling with efficient updates.

3. Step 3: Choose best tradeoff

   Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove. is the most efficient and scalable approach to support weighted random sampling with dynamic updates.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Prefix sums enable efficient weighted sampling [OK]

Hint: Prefix sums on frequencies enable weighted random sampling [OK]

Common Mistakes:

• Using naive repeated list causing high space
• Ignoring frequency updates
• Assuming getRandom() suffices for weighted sampling