</> 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%

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 (or a max-heap Dijkstra using min). One replaces Dijkstra's dist + weight with max(dist, weight). One is a case where the O(V³) algorithm is a reasonable choice, though Dijkstra from every city also works.

Multiple algorithms: layering BFS, binary search, Dijkstra, and Floyd-Warshall

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, never decreases 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.


Core idea: ask what the question actually optimises. A minimax objective, an all-pairs requirement or a two-stage input each point to a different tool, and saying why you rejected the alternatives is part of the answer.


1. BFS, then binary search, then 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 at one BFS per thief instead of one in total.

Stage two searches the answer: for a candidate safeness k, "is there a path using only cells with dist ≥ k?" is a plain BFS or DFS. Feasibility is monotonic (if k works then k − 1 works), which is exactly what binary search requires. The upper bound is min(dist[0][0], dist[n-1][n-1]), because the path includes both corners.

lo, hi = 0, min(dist[0][0], dist[n-1][n-1])   # the path includes both corners
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.

The alternative removes the binary search: run Dijkstra with a max-heap and min(current, dist[neighbour]) as the new value. Extending a path can only lower its score, so the first time the far corner is popped its value is final. Both versions cost O(n² log n).

2. Dijkstra with the operator changed

pq = [(grid[0][0], 0, 0)]; done = set()
while pq:
    t, r, c = heappop(pq)
    if (r, c) in done: continue
    done.add((r, c))
    if (r, c) == (n-1, n-1): return t
    for nr, nc in neighbours(r, c):
        if (nr, nc) not in done:
            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: on [[3,2],[0,1]] it returns 1 instead of 3. The same problem also yields to binary search on the water level with a BFS check (O(n² log n)), or to union-find flooding cells in height order until the corners connect (O(n² α(n²)), which relies on the heights being a permutation of 0 .. n² − 1). Three correct approaches, and being able to name all three is worth more than any one of them.

3. All pairs: Floyd-Warshall or Dijkstra from every city

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])

For Find the City With the Smallest Number of Neighbors the question is about every city, and n ≤ 100, so Floyd-Warshall at about a million steps is the short answer: no heap, no adjacency list. Then count, per city, the distances at most the threshold. The alternative is Dijkstra from every city, abandoning any path longer than the threshold. That costs about O(n · E log n), which loses on a dense graph but wins on a large sparse one. 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).

Swim in Rising Water minimax path worked example, 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, which answers a different question.


5. Where you'll actually meet this

  • Flood and terrain modelling. The lowest water level at which two points connect is the minimax path.
  • Bottleneck routing. The smallest limit you must be willing to use on a route (a bridge clearance, a link capacity) is a minimax or maximin path.
  • Clearance planning. Keeping a route as far as possible from hazards is the safest-path problem: build a clearance map once, then ask what threshold still leaves a connected route.
  • Small distance tables. A precomputed table of distances between a few dozen sites, such as warehouses, is an all-pairs shortest-path job.

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 distance map, then either binary-search the threshold with a flood fill as the check, or run a max-heap Dijkstra with min.
Pattern: BFS + binary search + BFS (or Dijkstra with min). 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 cities within a distance threshold, largest index on a tie. Floyd-Warshall for all pairs, then count; Dijkstra from every city with a threshold cutoff is the sparse-graph alternative.
Pattern: all-pairs shortest path. Target: O(V³) time, O(V²) space (Floyd-Warshall).

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, or binary search plus BFS, or union-find in height order.
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 on a small dense graph. It costs about V³ log V and more code than Floyd-Warshall. On a large sparse graph it is the better choice.
  • 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 (n ≤ 100, all pairs wanted), and say when Dijkstra from every node would win instead.
  6. Loop order carries the invariant in Floyd-Warshall; it is not a stylistic choice.
  7. Name several approaches. Each problem here has more than one valid solution, and choosing between them out loud is the point.

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.

Find the Safest Path in a Grid

Core idea: Three algorithms stacked. A multi-source BFS seeded with every thief at once gives each cell its distance to the nearest thief in one pass. Then binary search the answer: for a candidate safeness k, "is there a path using only cells with distance at least k?" is a plain graph search, and the answer is monotonic (if k works, so does k - 1), which is what licenses the binary search. Because we want the largest feasible k, the midpoint must be (lo + hi + 1) // 2; without the + 1 the loop never terminates. O(n² log n) time, O(n²) space.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

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.