The Skyline Problem

▶

Steps

setup

Start: Divide the buildings list

The algorithm begins by checking the input buildings list length. Since there are multiple buildings, it splits the list into two halves for recursive processing.

💡 Dividing the problem reduces complexity by handling smaller building groups separately before merging.

Line:

mid = len(buildings) // 2
left = getSkyline(buildings[:mid])
right = getSkyline(buildings[mid:])

💡 Divide and conquer breaks the problem into manageable subproblems.

setup

Base case: Compute skyline for single building [2,9,10]

The left half is further divided until a single building [2,9,10] is isolated. The skyline for this building is created as two points: start height and end zero.

💡 Base case returns a simple skyline for one building, forming the foundation for merges.

Line:

if len(buildings) == 1:
    L, R, H = buildings[0]
    return [[L, H], [R, 0]]

💡 A single building's skyline is straightforward: rise at start, fall at end.

setup

Base case: Compute skyline for single building [3,7,15]

Similarly, the next building [3,7,15] is isolated and its skyline is created as two points: rise at 3 to height 15, fall at 7 to zero.

💡 Each building individually forms a simple skyline for merging.

Line:

if len(buildings) == 1:
    L, R, H = buildings[0]
    return [[L, H], [R, 0]]

💡 Each building's skyline is a pair of points marking height changes.

merge

Merge skylines from left half: [[2,10],[9,0]] and [[3,15],[7,0]]

Initialize pointers i and j at 0 for left and right skylines. Heights h1 and h2 start at 0. Begin merging by comparing x-coordinates.

💡 Merging combines two skylines into one by walking through both arrays simultaneously.

Line:

h1 = h2 = 0
i = j = 0
merged = []

💡 Tracking pointers and heights is essential to correctly merge skylines.

compare

Compare left[i]=[2,10] and right[j]=[3,15], left[i][0]<right[j][0]

Since 2 < 3, take point from left skyline: x=2, update h1=10. Move i to 1.

💡 We always take the point with smaller x to maintain order in merged skyline.

Line:

if left[i][0] < right[j][0]:
    x, h1 = left[i]
    i += 1

💡 Choosing the smaller x-coordinate ensures correct skyline order.

compare

Compare left[i]=[9,0] and right[j]=[3,15], right[j][0]<left[i][0]

Now 3 < 9, so take point from right skyline: x=3, update h2=15. Move j to 1.

💡 We switch to right skyline because its next point is earlier on x-axis.

Line:

elif right[j][0] < left[i][0]:
    x, h2 = right[j]
    j += 1

💡 Merging requires careful pointer movement to maintain skyline order.

compare

Compare left[i]=[9,0] and right[j]=[7,0], right[j][0]<left[i][0]

7 < 9, so take point from right skyline: x=7, update h2=0. Move j to 2 (end of right).

💡 Right skyline pointer moves again because its point is earlier on x-axis.

Line:

elif right[j][0] < left[i][0]:
    x, h2 = right[j]
    j += 1

💡 Heights can drop to zero, marking end of building influence.

merge

Append remaining left skyline points

Right skyline is exhausted. Append remaining left skyline points starting at i=1: [9,0].

💡 Appending leftover points completes the merged skyline.

Line:

merged.extend(left[i:])
merged.extend(right[j:])

💡 Merging ends by adding leftover points from either skyline.

setup

Compute skyline for right half recursively

The right half [[5,12,12],[15,20,10],[19,24,8]] is recursively processed similarly: split, base cases, and merges.

💡 The same divide and conquer logic applies to the right half.

Line:

mid = len(buildings) // 2
left = getSkyline(buildings[:mid])
right = getSkyline(buildings[mid:])

💡 Divide and conquer applies recursively to all building subsets.

setup

Base case: Skyline for building [5,12,12]

Single building [5,12,12] returns skyline [[5,12],[12,0]].

💡 Base case returns simple skyline for one building.

Line:

if len(buildings) == 1:
    L, R, H = buildings[0]
    return [[L, H], [R, 0]]

💡 Each building's skyline is two points marking height changes.

setup

Base case: Skyline for building [15,20,10]

Single building [15,20,10] returns skyline [[15,10],[20,0]].

💡 Base case returns simple skyline for one building.

Line:

if len(buildings) == 1:
    L, R, H = buildings[0]
    return [[L, H], [R, 0]]

💡 Each building's skyline is two points marking height changes.

setup

Base case: Skyline for building [19,24,8]

Single building [19,24,8] returns skyline [[19,8],[24,0]].

💡 Base case returns simple skyline for one building.

Line:

if len(buildings) == 1:
    L, R, H = buildings[0]
    return [[L, H], [R, 0]]

💡 Each building's skyline is two points marking height changes.

merge

Merge right half right skylines: [[15,10],[20,0]] and [[19,8],[24,0]]

Initialize i=0, j=0, h1=0, h2=0. Compare points to merge these two skylines.

💡 Merging two skylines requires careful pointer and height tracking.

Line:

h1 = h2 = 0
i = j = 0
merged = []

💡 Setup for merging two skyline arrays.

compare

Compare left[i]=[15,10] and right[j]=[19,8], left[i][0]<right[j][0]

15 < 19, take left point: x=15, h1=10, i=1.

💡 Take smaller x to maintain order.

Line:

if left[i][0] < right[j][0]:
    x, h1 = left[i]
    i += 1

💡 Height from left skyline updated.

compare

Compare left[i]=[20,0] and right[j]=[19,8], right[j][0]<left[i][0]

19 < 20, take right point: x=19, h2=8, j=1.

💡 Right pointer moves because its x is smaller.

Line:

elif right[j][0] < left[i][0]:
    x, h2 = right[j]
    j += 1

💡 Height from right skyline updated.

compare

Compare left[i]=[20,0] and right[j]=[24,0], left[i][0]<right[j][0]

20 < 24, take left point: x=20, h1=0, i=2 (end of left).

💡 Left pointer moves to end.

Line:

if left[i][0] < right[j][0]:
    x, h1 = left[i]
    i += 1

💡 Height drops to zero, marking end of building.

merge

Append remaining right skyline points [[24,0]]

Left skyline exhausted, append remaining right points starting at j=1.

💡 Appending leftover points completes the merge.

Line:

merged.extend(left[i:])
merged.extend(right[j:])

💡 Merging ends by adding leftover points.

merge

Merge final skylines: left [[2,10],[3,15],[7,0],[9,0]] and right [[5,12],[12,0],[15,10],[19,8],[20,0],[24,0]]

Initialize pointers i=0, j=0, heights h1=0, h2=0. Begin merging the two large skylines from left and right halves.

💡 Final merge combines all partial skylines into the full skyline.

Line:

h1 = h2 = 0
i = j = 0
merged = []

💡 Final merge is the core step producing the full skyline.

compare

Compare left[i]=[2,10] and right[j]=[5,12], left[i][0]<right[j][0]

2 < 5, take left point: x=2, h1=10, i=1.

💡 Take smaller x to maintain order.

Line:

if left[i][0] < right[j][0]:
    x, h1 = left[i]
    i += 1

💡 Height from left skyline updated.

compare

Compare left[i]=[3,15] and right[j]=[5,12], left[i][0]<right[j][0]

3 < 5, take left point: x=3, h1=15, i=2.

💡 Left pointer moves again because its x is smaller.

Line:

if left[i][0] < right[j][0]:
    x, h1 = left[i]
    i += 1

💡 Height rises to 15, higher than right skyline's 0 so far.

def mergeSkylines(left, right):  # STEP 4, 13, 18
    h1 = h2 = 0  # STEP 4, 13, 18
    i = j = 0  # STEP 4, 13, 18
    merged = []  # STEP 4, 13, 18
    while i < len(left) and j < len(right):  # STEP 5-7, 14-16, 19-20
        if left[i][0] < right[j][0]:  # STEP 5, 6, 7, 14, 16, 19, 20
            x, h1 = left[i]  # STEP 5, 6, 7, 14, 16, 19, 20
            i += 1  # STEP 5, 6, 7, 14, 16, 19, 20
        elif right[j][0] < left[i][0]:  # STEP 6, 7, 15
            x, h2 = right[j]  # STEP 6, 7, 15
            j += 1  # STEP 6, 7, 15
        else:  # STEP 8
            x = left[i][0]  # STEP 8
            h1 = left[i][1]  # STEP 8
            h2 = right[j][1]  # STEP 8
            i += 1  # STEP 8
            j += 1  # STEP 8
        maxH = max(h1, h2)  # STEP 5-8
        if not merged or merged[-1][1] != maxH:  # STEP 5-8
            merged.append([x, maxH])  # STEP 5-8
    merged.extend(left[i:])  # STEP 8
    merged.extend(right[j:])  # STEP 8
    return merged  # STEP 8

def getSkyline(buildings):  # STEP 1, 2, 9
    if not buildings:  # STEP 1
        return []  # STEP 1
    if len(buildings) == 1:  # STEP 2, 3, 10-12
        L, R, H = buildings[0]  # STEP 2, 3, 10-12
        return [[L, H], [R, 0]]  # STEP 2, 3, 10-12
    mid = len(buildings) // 2  # STEP 1, 9
    left = getSkyline(buildings[:mid])  # STEP 1, 9
    right = getSkyline(buildings[mid:])  # STEP 1, 9
    return mergeSkylines(left, right)  # STEP 1, 9

if __name__ == '__main__':  # STEP 1
    buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]  # STEP 1
    print(getSkyline(buildings))  # STEP 1

📊

The Skyline Problem - Watch the Algorithm Execute, Step by Step

Watching each pointer move and merge decision reveals how the skyline is constructed from overlapping buildings, making the complex merging logic intuitive.

setup

[2,9,10]

0

[3,7,15]

1

[5,12,12]

2

[15,20,10]

3

[19,24,8]

4

Result: []

setup

0

1

Result: [[2,10],[9,0]]

setup

0

1

Result: [[3,15],[7,0]]

setup

j

0

1

Result: []

move_left

j

0

i

1

Result: [[2,10]]

move_right

0

j

1

Result: [[2,10],[3,15]]

move_right

0

i

1

Result: [[2,10],[3,15],[7,0]]

record

0

Result: [[2,10],[3,15],[7,0],[9,0]]

setup

[5,12,12]

0

[15,20,10]

1

[19,24,8]

2

Result: []

setup

0

1

Result: [[5,12],[12,0]]

setup

0

1

Result: [[15,10],[20,0]]

setup

0

1

Result: [[19,8],[24,0]]

setup

j

0

1

Result: []

move_left

j

0

i

1

Result: [[15,10]]

move_right

0

j

1

Result: [[15,10],[19,8]]

move_left

0

Result: [[15,10],[19,8],[20,0]]

record

0

Result: [[15,10],[19,8],[20,0],[24,0]]

setup

j

0

1

2

3

Result: []

move_left

j

0

i

1

2

3

Result: [[2,10]]

move_left

j

0

1

i

2

Result: [[2,10],[3,15]]

Key Takeaways

✓ Divide and conquer breaks the complex skyline problem into manageable subproblems.

This insight is hard to see from code alone because recursion and merging are intertwined.

✓ Merging skylines requires careful pointer movement and height tracking to correctly combine contours.

Visualizing pointer moves and height updates clarifies how overlapping buildings affect the skyline.

✓ Height changes in the merged skyline occur only when the maximum height between left and right skylines changes.

This explains why some points are skipped and others recorded, which is subtle in code but clear in visualization.

Practice

1. Consider the following code snippet for computing the maximum path sum in a binary tree. Given the tree with root value 1, left child 2, and right child 3, what is the final returned maximum path sum?

easy

A. 3

B. 6

C. 5

D. 4

Solution

1. Step 1: Trace helper on left child (2):

   left and right children are null, so left=0, right=0, max_sum updated to max(-inf, 2+0+0)=2, returns 2+max(0,0)=2.

2. Step 2: Trace helper on right child (3):

   Similarly, max_sum updated to max(2, 3+0+0)=3, returns 3+max(0,0)=3.

3. Step 3: Trace helper on root (1):

   left=2, right=3, max_sum updated to max(3, 1+2+3)=6, returns 1+max(2,3)=4.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Max path is 2 -> 1 -> 3 with sum 6 [OK]

Hint: Sum includes node plus max gains from both children [OK]

Common Mistakes:

• Returning sum of one child only
• Off-by-one in max_sum update
• Ignoring zero cutoff for negative gains

2. The following code attempts to solve the Burst Balloons problem using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def maxCoins(nums):
    nums = nums  # Bug here: missing virtual balloons
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for i in range(left + 1, right):
                coins = nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]
                dp[left][right] = max(dp[left][right], coins)
    return dp[0][n - 1]

medium

A. Line 3: dp = [[0] * n for _ in range(n)]

B. Line 1: nums = nums # missing virtual balloons

C. Line 6: for left in range(n - length):

D. Line 9: dp[left][right] = max(dp[left][right], coins)

Solution

1. Step 1: Check initialization of nums

   The code does not add virtual balloons (1) at the start and end, which are essential for correct coin calculation at edges.

2. Step 2: Understand impact of missing virtual balloons

   Without virtual balloons, the dp indices and coin calculations are incorrect, leading to wrong results on edge cases.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Adding [1] at both ends fixes the bug [OK]

Hint: Missing virtual balloons breaks boundary calculations [OK]

Common Mistakes:

• Not adding virtual balloons
• Incorrect dp initialization
• Wrong dp update line

3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the edit distance problem, where the input strings have lengths m and n respectively?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(3^(m + n))

Solution

1. Step 1: Identify nested loops over m and n

   The algorithm iterates over all pairs of indices (i, j) with i in [0, m) and j in [0, n), performing constant work per pair.

2. Step 2: Confirm no extra multiplicative factors

   Each cell computation is O(1), so total time is O(m * n). The recursion stack or auxiliary space does not affect time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table size m*n and constant work per cell [OK]

Hint: DP over m*n cells -> O(m*n) time [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming exponential due to recursion without memoization

4. Consider the following buggy implementation of the two-pointer approach for trapping rain water. Which line contains the subtle bug that can cause incorrect trapped water calculation?

medium

A. Line 7: if height[left] < height[right]:

B. Line 15: if height[right] >= right_max:

C. Line 17: water += right_max - height[right]

D. Line 9: if height[left] > left_max:

Solution

1. Step 1: Compare condition for updating left_max

   The original buggy code used '>' instead of '>=' which causes left_max not to update when height[left] equals left_max.

2. Step 2: Effect of bug

   When height[left] == left_max, water is incorrectly added (left_max - height[left] = 0), which is harmless but logically incorrect and can cause issues in some cases.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Using '>=' ensures correct max update and prevents unnecessary water addition [OK]

Hint: Use '>=' when updating max heights to avoid underestimation [OK]

Common Mistakes:

• Using '>' instead of '>=' for max updates
• Incorrect pointer movement
• Adding water without checking max heights

5. Examine the following snippet from an implementation of the optimal Word Search II solution. Which line contains a subtle bug that can cause incorrect results or infinite recursion?

medium

A. Line where curr_node.word is not set to null after found

B. Line where board[r][c] is set to '#'

C. Line where curr_node.word is appended to res

D. Line where backtrack is recursively called on neighbors

Solution

1. Step 1: Identify purpose of setting curr_node.word to None

   This prevents adding the same word multiple times by marking it as found.

2. Step 2: Analyze effect of missing this line

   Without setting curr_node.word to None, duplicates can be appended and redundant searches occur, possibly causing inefficiency or infinite recursion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing word removal after found causes duplicates [OK]

Hint: Mark found words None to avoid duplicates [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Not pruning found words
• Incorrect recursion boundaries