The skyline problem is a classic "hard" question because it combines three ideas at once: turning shapes into events, sweeping left to right, and keeping the current maximum height in a heap. If you can narrate those three steps clearly, the code almost writes itself.
Each building [left, right, height] produces a start event at left and an end event at right. A common trick is to store start events with a negative height so that sorting by (x, height) processes taller starts first and avoids duplicate key points at the same x.
import heapq
def get_skyline(buildings):
events = []
for l, r, h in buildings:
events.append((l, -h, r)) # start: negative height, remember end
events.append((r, 0, 0)) # end marker
events.sort()
result = []
heap = [(0, float('inf'))] # (negative height, end x)
for x, neg_h, r in events:
if neg_h:
heapq.heappush(heap, (neg_h, r))
while heap[0][1] <= x: # lazily drop buildings that ended
heapq.heappop(heap)
height = -heap[0][0]
if not result or result[-1][1] != height:
result.append([x, height])
return result
if at the bottom.Hard sweep-line problems are easier when you practice explaining them live. If you want real-time support during practice rounds, take a look at Linkjob, an AI assistant for technical interviews.
Disclosure: I work on Linkjob AI.