Multiple Algorithms

What is this?

The hardest graph problems in this tier are not hard because any one algorithm is hard. They are hard because no single algorithm answers the question. One needs a multi-source BFS to build the input to a binary search whose feasibility check is another BFS. One replaces Dijkstra's dist + weight with max(dist, weight). One is the rare case where the O(V³) algorithm is genuinely the right choice.

💡 Fun fact: Swim in Rising Water changes one operator in Dijkstra and nothing else. The cost of a path is normally the sum of its edges; here it is the maximum — the water level at which the path becomes swimmable. So instead of pushing dist + weight you push max(dist, weight), and the greedy argument survives untouched: the maximum along a path, like a sum of non-negative weights, can never decrease as the path grows, which is the only property Dijkstra's correctness needs. Recognising that a familiar algorithm survives a changed objective is most of what this chapter tests.

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

The one-line idea: ask what the question actually optimises. A minimax objective, an all-pairs requirement or a two-stage input each pick a different tool — and stating why you rejected the other two is the answer they are listening for.

1. BFS → binary search → BFS

The safeness of a cell is its distance to the nearest thief, so stage one is a multi-source BFS seeded with every thief at once:

q = deque(all thief cells); dist[thief] = 0
while q:
    r, c = q.popleft()
    for nr, nc in neighbours(r, c):
        if dist[nr][nc] == -1:
            dist[nr][nc] = dist[r][c] + 1; q.append((nr, nc))

Seeding all sources into the queue together is what makes one pass produce every cell's nearest-thief distance — running a separate BFS per thief gives the same answer for k times the cost.

Stage two searches the answer: for a candidate safeness k, "is there a path using only cells with dist ≥ k?" is a plain BFS. Feasibility is monotonic — if k works then k − 1 works — which is exactly what binary search requires.

lo, hi = 0, 2 * n
while lo < hi:
    mid = (lo + hi + 1) // 2                     # +1: bias up, or this loops forever
    if reachable_with_threshold(mid): lo = mid
    else: hi = mid - 1

The + 1 in the midpoint is mandatory in this "largest feasible value" shape. Without it, lo = mid with lo and hi adjacent never advances.

2. Dijkstra with the operator changed

pq = [(grid[0][0], 0, 0)]; seen = {(0, 0)}
while pq:
    t, r, c = heappop(pq)
    if (r, c) == (n-1, n-1): return t
    for nr, nc in neighbours(r, c):
        if (nr, nc) not in seen:
            seen.add((nr, nc))
            heappush(pq, (max(t, grid[nr][nc]), nr, nc))   # ← max, not +

The starting cell's own elevation is part of the answer and must seed the heap — starting at 0 is a common and quiet error. Note also that this same problem yields to binary search plus BFS, or to union-find adding cells in elevation order until the corners connect. Three correct approaches, and being able to name all three is worth more than any one of them.

3. When O(V³) is right

for k in range(n):                                # k must be the OUTER loop
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Floyd-Warshall looks lazy next to Dijkstra and is the better answer here: the question is about every city's reachability, n ≤ 100, and running Dijkstra n times is more code for no gain. The loop order is the algorithm — k outermost is what makes the invariant "shortest paths using only intermediates < k" hold, and any other nesting silently returns wrong distances.

4. A 30-second worked example (minimax path)

grid = [[0, 2], [1, 3]] — swim from (0,0) to (1,1).

push (0, 0,0)                        the start cell's own elevation

pop  t=0 at (0,0)
     → (1,0): max(0, 1) = 1     push
     → (0,1): max(0, 2) = 2     push

pop  t=1 at (1,0)
     → (1,1): max(1, 3) = 3     push

pop  t=2 at (0,1)   (not the target)
pop  t=3 at (1,1)   → target reached, answer 3

Both routes end at the cell of elevation 3, so both cost 3 — the maximum, not the total, is what is being minimised, and a longer path with a lower peak would have won. Summing instead would have preferred the left route at 0+1+3 = 4 over the right at 0+2+3 = 5, answering a question nobody asked.

5. Where you'll actually meet this

• Flood and terrain modelling. The lowest water level at which two points connect is the minimax path, exactly.
• Network provisioning. Maximising the bottleneck bandwidth along a route is the same objective with the sign flipped.
• Robot and drone routing. Maximising the minimum clearance from obstacles is the safest-path problem.
• Service-mesh latency analysis. All-pairs latency across a few hundred services is a genuine Floyd-Warshall.
• Evacuation and logistics planning. Routes chosen by their worst segment rather than their total length.

6. Problems in this chapter

▶ Find the Safest Path in a Grid

Maximise the minimum distance to any thief along a path. Multi-source BFS for the distances, then binary-search the threshold with a BFS as the check.
Pattern: BFS + binary search + BFS. Target: O(n² log n) time, O(n²) space.

▶ Find the City With the Smallest Number of Neighbors at a Threshold Distance

The city with fewest reachable neighbours within a distance, largest index on a tie. All-pairs shortest paths with Floyd-Warshall, then count.
Pattern: all-pairs shortest path. Target: O(V³) time, O(V²) space.

▶ Swim in Rising Water

The least time at which a path to the far corner exists. Dijkstra propagating max(dist, weight) instead of a sum.
Pattern: Dijkstra with a minimax objective. Target: O(n² log n) time, O(n²) space.

7. Common pitfalls 🚫

• Summing instead of maximising in the minimax Dijkstra — it answers a different question and looks plausible.
• Seeding the heap with 0 rather than the start cell's own elevation.
• Running one BFS per source when a multi-source BFS gives every distance in a single pass.
• Omitting the + 1 in the midpoint of a largest-feasible-value binary search, which loops forever.
• Nesting the Floyd-Warshall loops wrongly. k must be outermost or the distances are simply wrong.
• Reaching for Dijkstra V times when all pairs are wanted and V is small — more code, no gain.
• Getting the tie-break backwards. The city problem wants the largest index among ties, which a <= comparison while scanning ascending gives you.

8. Key takeaways

1. Read the objective before choosing the algorithm. Sum, maximum and all-pairs each point somewhere different.
2. Dijkstra survives a minimax objective because the maximum, like a sum, never decreases along a path.
3. Multi-source BFS is one pass, not one pass per source.
4. Binary search needs monotonic feasibility — say why it holds before writing the loop.
5. O(V³) can be the right answer. Justify it with the constraint, and it is a strength rather than a concession.
6. Loop order carries the invariant in Floyd-Warshall; it is not a stylistic choice.
7. Why interviewers love it: these problems reward naming several valid approaches and choosing between them out loud, which is the closest thing to real engineering on a whiteboard.

Order: Find the Safest Path in a Grid → Find the City With the Smallest Number of Neighbors at a Threshold Distance → Swim in Rising Water.