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. Given the following code snippet for the optimal Twitter design, what is the output of getNewsFeed(1) after these operations?

twitter = Twitter()
twitter.postTweet(1, 5)
twitter.postTweet(2, 6)
twitter.followees[1] = {2}
print(twitter.getNewsFeed(1))

Assume getNewsFeed returns a list of tweetIds sorted from most recent to oldest.

easy

A. [6]

B. [5, 6]

C. [5]

D. [6, 5]

Solution

1. Step 1: Trace postTweet calls

   User 1 posts tweet 5 at time=1, user 2 posts tweet 6 at time=2.

2. Step 2: Trace getNewsFeed(1)

   User 1 follows user 2, so heap contains tweets with times 1 (tweet 5) and 2 (tweet 6). Max heap pops tweet 6 first, then tweet 5.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap orders tweets by descending time, so output is [6, 5] [OK]

Hint: Heap orders tweets by negative time for max behavior [OK]

Common Mistakes:

• Returning tweets in posting order instead of time order
• Ignoring followees' tweets

2. You need to design a data structure that supports adding numbers from a stream and retrieving the median efficiently at any time. Which approach best balances insertion and median retrieval time for large data streams?

easy

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

B. Sort the entire list of numbers every time you query the median.

C. Use a balanced binary search tree to keep all numbers sorted and find the median by in-order traversal.

D. Store numbers in an unsorted array and scan it fully to find the median on each query.

Solution

1. Step 1: Understand the problem constraints

   We need efficient insertion and median retrieval for a data stream, so sorting on every query (Sort the entire list of numbers every time you query the median.) or scanning unsorted arrays (Store numbers in an unsorted array and scan it fully to find the median on each query.) is too slow.

2. Step 2: Evaluate data structures

   Using two heaps (max-heap for lower half, min-heap for upper half) allows O(log n) insertion and O(1) median retrieval by balancing sizes, which is optimal for streaming data.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two heaps balance halves efficiently for median [OK]

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

Common Mistakes:

• Sorting on every query is too slow for streams
• Using one heap only cannot track median efficiently

3. Given the following addRange method snippet from the optimal RangeModule implementation, what is the value of self.starts after calling addRange(2, 6) on an initially empty RangeModule?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] >= left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

easy

A. [2, 6, 7]

B. [2, 6]

C. [2]

D. [6]

Solution

1. Step 1: Trace bisect indices on empty starts list

   Initially, self.starts = []. Calling bisect_left([], 2) returns 0, and bisect_right([], 6) returns 0.

2. Step 2: Update intervals and starts

   Since i == 0, the first if condition is skipped. Also, j == 0, so second if is skipped. No intervals to delete. Insert left=2 at self.starts[0:0], so self.starts = [2]. Interval stored as {2:6}.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starts list after first addRange is [2] [OK]

Hint: Bisect on empty list returns 0, so starts list gets single element [OK]

Common Mistakes:

• Assuming right endpoint is also inserted in starts list

4. Examine the following buggy remove method from the optimized Insert Delete GetRandom O(1) with duplicates data structure. Which line contains the subtle bug that can cause incorrect behavior or runtime errors?

def remove(self, val: int) -> bool:
    if val not in self.idx_map or not self.idx_map[val]:
        return false
    remove_idx = self.idx_map[val].pop()
    last_val = self.nums[-1]
    self.nums[remove_idx] = last_val
    self.idx_map[last_val].add(remove_idx)
    # BUG: missing discard of old index for last_val
    self.nums.pop()
    if not self.idx_map[val]:
        del self.idx_map[val]
    return true

medium

A. Missing line to discard old index of last_val from idx_map[last_val]

B. Line adding remove_idx to idx_map[last_val] (self.idx_map[last_val].add(remove_idx))

C. Line popping remove_idx from idx_map[val] (remove_idx = self.idx_map[val].pop())

D. Line removing the last element from nums (self.nums.pop())

Solution

1. Step 1: Understand index updates during removal

   When swapping last_val into remove_idx, we must update idx_map[last_val] by adding remove_idx and discarding the old index (len(nums)-1).

2. Step 2: Identify missing discard

   The code adds remove_idx to idx_map[last_val] but does not discard the old index, causing stale indices and incorrect removals later.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing discard leads to incorrect index tracking [OK]

Hint: Always discard old indices after swapping during removal [OK]

Common Mistakes:

• Forgetting to discard old index after swap
• Removing wrong element from idx_map
• Incorrect pop from idx_map[val]

5. Suppose you want to modify the skiplist to support duplicate values and allow searching for the k-th occurrence of a target. Which modification is the most appropriate to maintain efficient search and insertion?

hard

A. Insert duplicate nodes at the lowest level only, ignoring higher levels

B. Store a count of duplicates in each node and update counts on insert/erase

C. Use a hash map to track occurrences separately from the skiplist

D. Disallow duplicates and reject insertions of existing values

Solution

1. Step 1: Understand duplicate handling

   To support duplicates and k-th occurrence search, nodes must track counts or occurrences.

2. Step 2: Evaluate options

   Storing counts in nodes and updating them maintains skiplist structure and efficient operations.

3. Step 3: Reject other options

   Inserting duplicates only at lowest level breaks skiplist invariants; hash map adds overhead; disallowing duplicates contradicts requirement.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting duplicates in nodes preserves skiplist efficiency and supports k-th occurrence [OK]

Hint: Count duplicates in nodes to handle multiple occurrences efficiently [OK]

Common Mistakes:

• Ignoring duplicates in higher levels
• Using external structures breaking skiplist properties
• Disallowing duplicates despite requirement