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. You need to design a data structure that supports inserting elements (including duplicates), removing one occurrence of an element, and retrieving a random element--all in average O(1) time. Which approach best guarantees these time complexities?

easy

A. Use a simple list and perform linear search for removals.

B. Use a balanced binary search tree to maintain elements and their counts.

C. Use a hash map to store element to indices mapping, combined with a list to store elements, updating indices on insert and remove.

D. Use a queue to track insertion order and a hash set for membership checks.

Solution

1. Step 1: Understand the operations required

   Insert, remove (one occurrence), and getRandom must all be average O(1), even with duplicates.

2. Step 2: Evaluate approaches

   A simple list with linear search (A) leads to O(n) removals. Balanced BST (C) has O(log n) operations. Queue and hash set (D) do not support random access efficiently. Hash map + list with index tracking (B) supports O(1) insert, remove, and getRandom by maintaining indices of duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + list with index tracking enables O(1) average operations [OK]

Hint: Hash map + list with index tracking enables O(1) ops [OK]

Common Mistakes:

• Assuming balanced BST can do O(1) getRandom
• Using linear search for removal
• Ignoring duplicates in data structure

2. Consider this buggy snippet of the optimal Twitter design's getNewsFeed method:

def getNewsFeed(self, userId: int) -> list:
    users = self.followees.get(userId, set()).copy()
    heap = []  # max heap by time

    for u in users:
        head = self.userTweets.get(u, None)
        if head:
            heapq.heappush(heap, (-head.time, head))

    result = []
    while heap and len(result) < 10:
        time, node = heapq.heappop(heap)
        result.append(node.tweetId)
        if node.next:
            heapq.heappush(heap, (-node.next.time, node.next))
    return result

What is the subtle bug in this code?

medium

A. The user's own tweets are not included because userId is not added to users set.

B. The heap is used as a min heap instead of max heap by pushing negative times.

C. The linked list nodes are not updated correctly after popping from the heap.

D. The followees set is copied unnecessarily causing performance overhead.

Solution

1. Step 1: Check inclusion of user's own tweets

   The code gets followees but never adds the userId itself to the users set, so user's own tweets are excluded.

2. Step 2: Verify heap usage and linked list traversal

   Negative times are correctly used for max heap behavior; linked list next pointers are used properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing userId in users set causes incorrect feed [OK]

Hint: User's own tweets must be explicitly included in feed [OK]

Common Mistakes:

• Forgetting to add userId to followees set
• Misusing heap sign for max heap

3. What is the time complexity of performing addRange, removeRange, or queryRange operations in the optimal RangeModule implementation using a balanced BST with interval merging, assuming n intervals stored?

medium

A. O(n) per operation because intervals must be scanned to merge overlaps.

B. O(log n + k) where k is the number of overlapping intervals merged or removed.

C. O(log n) per operation due to balanced BST operations and interval merging.

D. O(1) amortized due to efficient data structure caching.

Solution

1. Step 1: Identify main operations

   Each operation uses binary search (O(log n)) to find affected intervals and merges or removes overlapping intervals.

2. Step 2: Consider merging/removal cost

   The number of intervals merged or removed, k, affects the cost linearly. So total cost is O(log n + k).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Logarithmic search plus linear merging -> O(log n + k) [OK]

Hint: Operations cost depends on search plus number of intervals merged [OK]

Common Mistakes:

• Assuming always O(log n) ignoring merging cost
• Assuming linear scan O(n) always

4. What is the time complexity of the get operation in the optimal SnapshotArray implementation that uses a hash map per index with binary search, assuming m snapshots and k set operations?

medium

A. O(1) because values are stored directly per index and snap_id

B. O(k) because get must scan all set operations for the index

C. O(m) because linear search is needed over all snapshots

D. O(log m) because binary search is performed on at most m entries per index

Solution

1. Step 1: Identify data structure for get

   Each index stores a sorted list of (snap_id, value) pairs, with length up to number of set operations k but bounded by m snapshots.

2. Step 2: Analyze get operation

   Get uses binary search on this list to find the value for the requested snap_id, which takes O(log m) time since at most one entry per snapshot per index.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search on sorted snapshot list yields O(log m) [OK]

Hint: Binary search on snapshots per index yields O(log m) get time [OK]

Common Mistakes:

• Assuming get is O(1) due to direct indexing
• Confusing linear search with binary search

5. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs