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 continuously receive numbers from a stream and efficiently find the median at any point. Which approach guarantees optimal time complexity for both insertion and median retrieval?

easy

A. Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half, balancing their sizes.

B. Use a balanced binary search tree to insert elements and find the median by in-order traversal.

C. Sort the entire list after each insertion and pick the middle element(s).

D. Store all elements in an unsorted array and scan it fully to find the median when requested.

Solution

1. Step 1: Understand the problem constraints

   The problem requires efficient insertion and median retrieval from a data stream, so sorting on every insertion is too slow.

2. Step 2: Evaluate approaches

   Sorting each time (A) is O(n log n) per insertion, scanning unsorted array (D) is O(n) per median query, and balanced BST (B) has O(log n) insertion but median retrieval is not O(1). Two heaps (C) provide O(log n) insertion and O(1) median retrieval by balancing sizes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two heaps balance halves for median in O(log n) insertion and O(1) retrieval [OK]

Hint: Two heaps balance halves for O(log n) insert and O(1) median [OK]

Common Mistakes:

• Sorting on every insertion is too slow for large streams
• Using a single heap cannot maintain median efficiently
• Balanced BST median retrieval is not O(1)

2. Examine the following modified code for Largest Rectangle in Histogram. Which line contains a subtle bug that can cause incorrect maximum area calculation?

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel to flush stack at end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()  # Restore original list
    return max_area

medium

A. Line with 'while stack and heights[stack[-1]] >= h:'

B. Line with 'height = heights[stack.pop()]'

C. Line with 'width = i - left - 1'

D. Line with 'heights.append(0)'

Solution

1. Step 1: Identify condition in while loop

   The condition uses '>=' which causes bars of equal height to be popped prematurely, merging areas incorrectly.

2. Step 2: Correct condition

   Changing '>=' to '>' ensures bars of equal height remain on stack, preserving correct width calculations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using '>=' pops equal height bars too early, causing wrong max area [OK]

Hint: Use '>' not '>=' to avoid premature popping [OK]

Common Mistakes:

• Using '>=' instead of '>' in while condition
• Miscomputing width boundaries
• Forgetting sentinel bar

3. Consider the following buggy code snippet for the optimal median of two sorted arrays. Which line contains the subtle bug that can cause incorrect median calculation or runtime error?

medium

A. Line 10: max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1]

B. Line 7: i = (low + high) // 2

C. Line 17: elif max_left_nums1 > min_right_nums2:

D. Line 2: if len(nums1) < len(nums2): nums1, nums2 = nums2, nums1

Solution

1. Step 1: Check array swap condition

   The code swaps arrays only if len(nums1) < len(nums2), which is incorrect. It should swap if nums1 is larger to ensure binary search on smaller array.

2. Step 2: Consequences of wrong swap

   Without correct swap, binary search range can be large, causing inefficiency or index errors.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Swap condition reversed causes subtle bugs [OK]

Hint: Swap arrays so binary search is on smaller one [OK]

Common Mistakes:

• Swapping arrays incorrectly or not at all
• Off-by-one errors in partition indices
• Incorrect median calculation for odd/even lengths

4. What is the time complexity of the Trie-based palindrome pairs solution, given n words each of maximum length k?

medium

A. O(n^2 * k)

B. O(n * k)

C. O(n * k^2)

D. O(n^2 * k^2)

Solution

1. Step 1: Identify outer loop complexity

   We process each of the n words, so at least O(n).

2. Step 2: Analyze inner operations per word

   Adding a word to the Trie involves iterating over k characters and checking palindrome prefixes which can take O(k) each, resulting in O(k^2) per word.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie build and search combined yield O(n * k^2) time [OK]

Hint: Palindrome checks inside Trie add quadratic factor in k [OK]

Common Mistakes:

• Assuming O(n^2 * k) from brute force
• Ignoring palindrome prefix checks cost
• Confusing linear with quadratic in k

5. Suppose you want to compute the minimum edit distance between two strings but now you are allowed to reuse characters from the second string any number of times (i.e., unlimited insertions of any character from word2). Which modification to the DP approach correctly handles this variant?

hard

A. Modify DP to allow insertions without advancing j, but keep other transitions unchanged

B. Use a greedy approach to match characters from word1 to any in word2 without DP

C. Change DP to allow insertions that advance j, but allow deletions to skip characters in word2

D. Use the same DP but allow insert operation to not advance j index

Solution

1. Step 1: Understand reuse means insertions can be repeated without advancing j

   Normally, insertion advances j by 1; here, we can insert the same character multiple times, so insertion does not advance j.

2. Step 2: Modify DP transitions accordingly

   Allow insert operation to keep j fixed while increasing i, other transitions remain the same.

3. Step 3: Confirm other options fail

   Use the same DP but allow insert operation to not advance j index changes DP but does not specify keeping other transitions unchanged; Change DP to allow insertions that advance j, but allow deletions to skip characters in word2 incorrectly allows deletions to skip word2 chars; Use a greedy approach to match characters from word1 to any in word2 without DP is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Allowing insertion without advancing j models reuse correctly [OK]

Hint: Reuse means insertion does not advance j [OK]

Common Mistakes:

• Advancing j on insertion breaks reuse
• Using greedy approach fails correctness