Shortest paths

Weighted graphs. Which algorithm depends entirely on the weights.

Trigger in the prompt: 'Cheapest route', 'minimum cost', 'earliest time to reach'.

mediumCheapest Flights Within K Stops

Find the cheapest route with at most k intermediate stops.

Trigger

'At most k stops' — a hop constraint on top of a shortest path.

Approach
  1. Dijkstra alone is wrong: the cheapest path may exceed the stop limit.
  2. The constraint maps exactly onto Bellman-Ford's rounds — k+1 relaxation passes.
  3. Use a snapshot of the distances per round, so one round cannot cascade into itself.
  4. Alternative: Dijkstra with (cost, node, stops) in the state.
Target complexity

O(k · E) time, O(V) space.

Pitfall

Relaxing in place rather than from a snapshot. A single round then chains and allows more hops than allowed.

Say it out loud

“The stop limit is what makes this Bellman-Ford rather than Dijkstra: k stops means k plus one rounds of relaxation, which maps onto the algorithm exactly. The detail is relaxing from a snapshot of the previous round, otherwise one pass chains through multiple edges.”

Solve on LeetCode
mediumMin Cost to Connect All Points

Connect all points with minimum total edge cost.

Trigger

'Connect everything at minimum cost' — a minimum spanning tree.

Approach
  1. Name it: this is an MST.
  2. The graph is complete (n² implicit edges), so Prim with an adjacency-free approach beats Kruskal here — Kruskal would need to sort n² edges.
  3. Prim: keep the cheapest known distance from the tree to each outside point, take the minimum, add it, update.
  4. Kruskal is better on sparse graphs — say when you would pick each.
Target complexity

O(n²) with dense Prim; O(n² log n) with a heap.

Pitfall

Reaching for Kruskal on a complete graph. Sorting n² edges is worse than dense Prim.

Say it out loud

“This is a minimum spanning tree on a complete graph. Because every pair is an edge, Kruskal would have to sort n squared edges — dense Prim is n squared with no sort. On a sparse graph I'd flip that choice and use Kruskal with union-find.”

Solve on LeetCode
mediumNetwork Delay Time

Find how long until a signal from one node reaches every node in a weighted directed graph.

Trigger

Positive weights, single source, 'time for all to receive'.

Approach
  1. Positive weights and one source: Dijkstra.
  2. Heap of (distance, node); skip stale entries with `if d > dist[u]: continue`.
  3. The answer is the maximum finalised distance; if any node is unreachable, return −1.
Target complexity

O(E log V) time, O(V + E) space.

Pitfall

Omitting the stale-entry check. Without it you reprocess nodes and the complexity degrades.

Say it out loud

“Weights are positive and there's a single source, so Dijkstra. Python's heap has no decrease-key, so I push duplicates and skip stale entries on pop — that's the lazy deletion that gives the E log V bound.”

Solve on LeetCode
mediumPath With Minimum Effort

Find the path across a grid minimising the largest single elevation change.

Trigger

'Minimise the maximum edge' — a Dijkstra variant, or binary search plus BFS.

Approach
  1. The cost of a path is a maximum, not a sum. Say that — it is the whole twist.
  2. Dijkstra still works: relax with max(current_effort, edge) instead of a sum.
  3. Alternative: binary search the threshold and check connectivity with BFS.
Target complexity

O(m·n·log(m·n)) with Dijkstra.

Pitfall

Summing the differences. The objective is a maximum, and summing gives a different answer.

Say it out loud

“The twist is that path cost is a maximum rather than a sum, but Dijkstra's argument survives: the relaxation just becomes max of the running effort and the edge. There's also a binary search on the threshold with a plain BFS check, which is often easier to explain.”

Solve on LeetCode
mediumShortest Path in Binary Matrix

Find the shortest clear path from corner to corner in a binary grid, moving in eight directions.

Trigger

'Shortest path' on an unweighted grid.

Approach
  1. All moves cost one, so BFS — not Dijkstra. Say that explicitly.
  2. Eight directions, so the neighbour list has eight offsets.
  3. Then the extension: A* with the Chebyshev heuristic, because diagonal movement is allowed.
  4. Say why Manhattan would be wrong here: it overestimates with diagonals, so it is not admissible and you lose optimality.
Target complexity

O(n²) time and space with BFS.

Pitfall

Using the Manhattan heuristic with eight-directional movement. It overestimates and breaks the optimality guarantee.

Say it out loud

“Every move costs the same, so BFS is enough — Dijkstra would be overkill. If we want to expand fewer nodes, A* with a Chebyshev heuristic works, since diagonals are allowed. Manhattan would overestimate here, which makes it inadmissible and loses the optimality guarantee.”

Solve on LeetCode
hardSliding Puzzle

Find the fewest moves to solve a small sliding tile puzzle.

Trigger

'Fewest moves' over a state space rather than a map.

Approach
  1. The graph is the state space: each board configuration is a vertex, each legal move an edge.
  2. Encode the board as a string or tuple so it can be hashed into the visited set.
  3. BFS gives the optimal move count since every move costs one.
  4. A* with the sum of Manhattan distances is the natural improvement — and it is admissible because each move fixes at most one tile's distance by one.
Target complexity

O(states) with BFS; far fewer expansions with A*.

Pitfall

Not hashing the state. Without a visited set the search revisits configurations endlessly.

Say it out loud

“The graph here is implicit — vertices are board states. I encode each board as a tuple so it can go in a visited set, and BFS gives the optimal move count. A* with summed Manhattan distances is admissible, because one move can only reduce one tile's distance by one, and it cuts the expansions dramatically.”

Solve on LeetCode
hardSwim in Rising Water

Find the earliest time you can cross a grid where each cell becomes passable at its own height.

Trigger

'Earliest time', with cells unlocking over time — the same minimax-path shape.

Approach
  1. Same structure as minimum effort: the cost of a path is the maximum cell value on it.
  2. Dijkstra with max-relaxation, or binary search on the time plus a BFS reachability check.
  3. Union-find sorted by height also works: add cells in height order until start and end connect.
Target complexity

O(n² log n) with Dijkstra on an n×n grid.

Pitfall

Treating it as a sum of heights. It is a bottleneck path, not a shortest path.

Say it out loud

“This is the same minimax-path problem as minimum effort: I want the path whose highest cell is lowest. Dijkstra with a max relaxation gives it directly. The union-find version is elegant — add cells in increasing height until the two corners connect.”

Solve on LeetCode