</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Two-Heap and Dijkstra

What is this?

Two heap problems, each breaking one of the assumptions the easier versions rely on.

Dijkstra normally accumulates by addition over non-negative weights. Here the weights are probabilities that multiply, and you want the largest product rather than the smallest sum. The algorithm survives, but only because of a property you should be able to state.

The two-heap running median normally only grows. Here it slides, so elements leave, and a binary heap has no way to remove something from its middle.

Two ways the easy assumption breaks: multiplying weights and elements leaving the window

Fun fact: lazy deletion works because a heap only ever guarantees its top. A stale element buried in the middle is harmless: it cannot affect any query until it reaches the top, and at that moment you discard it instead of returning it. The cost is amortised, since each element is discarded at most once. The catch is that the heap's physical size stops meaning anything, so the balance condition must be maintained against a separately tracked logical count.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


Core idea: Dijkstra needs only that extending a path cannot improve it. Multiplication by factors in [0, 1] satisfies that as surely as adding non-negative weights. And when a heap must forget something it cannot reach, leave it there and skip it on the way out.


1. Dijkstra with a product

best = [0.0] * n
best[start] = 1.0
heap = [(-1.0, start)]                      # max-heap via negation
while heap:
    p, node = heapq.heappop(heap)
    p = -p
    if node == end: return p                # first pop of the target is optimal
    if p < best[node]: continue             # a stale, worse entry
    for nxt, w in adj[node]:
        if p * w > best[nxt]:
            best[nxt] = p * w
            heapq.heappush(heap, (-best[nxt], nxt))
return 0.0

The correctness argument is the part to say aloud: every probability lies in [0, 1], so extending a path can only reduce its value. That is the exact analogue of non-negative edge weights, and it is why the first pop of a node is final. It is also why you may stop the moment the target is popped: every other entry in the heap is no better, and extending it can only lower it. If a weight could exceed 1, the greedy would be unsound and you would need Bellman-Ford.

The if p < best[node]: continue line is the other standard idiom: rather than decreasing a key in place, which a binary heap cannot do, you push a better entry and ignore the outdated one when it surfaces. That is lazy deletion again, in its most common disguise.

2. Two heaps that can forget

lower  = max-heap of the smaller half
upper  = min-heap of the larger half
pending = map from value -> how many copies are logically deleted

on the window sliding:
   add(entering)        push into the correct half, then rebalance
   remove(leaving)      pending[leaving] += 1
                        adjust the LOGICAL size of whichever half owns it
                        if it happens to be on top, prune immediately
   prune(heap)          while heap's top is pending, pop it and decrement
   median               prune both tops, then read

Three rules keep it honest. Prune before reading a top, never after. Rebalance on logical sizes, because the physical ones now include ghosts. And when the leaving element is not on top, do nothing but record it. Hunting for it is what you are avoiding.

There are simpler structures worth mentioning. A balanced ordered multiset (a tree with order statistics) gives O(n log k) with no stale entries. A plain sorted list with bisect.insort is simpler still, but each insert and delete shifts up to k items, so it is O(n k) in the worst case, though the shift is a fast memmove and it is often quicker for modest k. Either is a reasonable first answer before the two-heap version.


3. A 30-second worked example (lazy deletion)

Window [1, 3, 5] sliding to [3, 5, 7]: the 1 leaves, the 7 arrives.

Worked example: running median with lazy deletion, median ends at 5

The 1 is still physically present and never caused a problem, because it never reached the top while it mattered. Sorted, the window is [3, 5, 7] and the median is indeed 5.


4. Where you'll actually meet this

  • Network routing over lossy links. Most-reliable path is exactly the multiplicative Dijkstra, used where each hop has a delivery probability.
  • Risk and reliability engineering. Chained component reliabilities multiply; finding the most reliable configuration is this search.
  • Real-time analytics. Rolling p50 over a sliding window, where old samples must expire.
  • Trading systems. Windowed median price, where re-sorting per tick is unaffordable.
  • Job schedulers. Lazy deletion is how cancelled jobs are handled without rebuilding the queue.

5. Problems in this chapter

Path with Maximum Probability

Most probable path between two nodes. Dijkstra with a max-heap and multiplication; valid because factors in [0, 1] only shrink a path, which is also why you can stop when the target is first popped. The brute force over simple paths is bounded by O(V!).
Pattern: Dijkstra with a multiplicative objective. Target: O(E log V) time, O(V + E) space.

Sliding Window Median

Median of every window of size k. Two heaps straddling the median in a WindowMedian class, with lazy deletion for departing elements and rebalancing on logical sizes. Stale entries only leave when they reach a top, so the heaps can grow past k.
Pattern: two heaps + lazy deletion. Target: O(n log n) time and O(n) space in the worst case (stale entries linger); rebuilding the heaps when stale entries exceed k restores O(k) space.


6. Common pitfalls

  • Not stating why multiplicative Dijkstra is valid. The [0, 1] range is the whole justification, and an interviewer will ask.
  • Forgetting the negation for a max-heap in Python, or applying it inconsistently between push and pop.
  • Rebalancing on physical heap sizes. Ghost elements make those numbers meaningless.
  • Pruning after reading the top instead of before, which returns a deleted value.
  • Searching the heap for the departing element. That is O(h) for a heap of h entries and is precisely what lazy deletion exists to avoid.
  • Integer division for an even-sized window's median. Average the two middle values as a float.
  • Skipping the stale-entry guard in Dijkstra, which reprocesses nodes and inflates the running time.

7. Key takeaways

  1. Dijkstra needs "extending cannot improve", not addition. Probabilities in [0, 1] satisfy it.
  2. A heap only guarantees its top, which is exactly why burying stale entries is safe.
  3. Lazy deletion turns an impossible removal into an amortised skip.
  4. Track logical sizes separately once ghosts exist, and rebalance on those.
  5. Prune before reading, always.
  6. Offer the simpler structure first. A balanced ordered multiset is a legitimate O(n log k) answer before the two-heap version, and a sorted list is a simple O(n k) one.
  7. Why interviewers like it: both problems look like versions you have seen, and both fail if you apply the remembered solution without checking which assumption changed.

Order: Path with Maximum Probability → Sliding Window Median.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.