</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

Weighted Graphs

What is this?

Dijkstra's algorithm rests on one promise: once a node is popped from the frontier, its distance is final. Nothing cheaper can arrive later, because every remaining path is already at least as expensive. That promise is what makes it fast, and it is also what breaks the moment a problem adds a constraint.

If reaching a city cheaply but with no fuel left is worse than reaching it expensively with fuel to spare, then "the node" is not the whole story. The fix is not a different algorithm, it is a bigger definition of state.

Decision flow: shortest path with a twist and how to fix each invariant break

Fun fact: Cheapest Flights Within K Stops is the standard demonstration that Dijkstra's greedy invariant is conditional. Reaching a city for 100 using all your flights can be strictly worse than reaching it for 200 with flights to spare, so "cheapest so far" is no longer sufficient to prune. Two fixes work: promote the state to (city, flights used), or use Bellman-Ford and relax all edges exactly k + 1 times (k stops means at most k + 1 flights), which bounds the path length by construction and is the shorter thing to write.

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


The core idea: when a constraint makes "cheapest so far" an insufficient reason to prune, put the constraint into the state. The algorithm does not change; the graph you are searching gets one dimension larger.


1. The extra dimension

import heapq
INF = float("inf")

# state: (cost so far, city, flights used); k stops allow k + 1 flights
heap = [(0, src, 0)]
best = {}                                   # (city, flights) -> cheapest cost seen

while heap:
    cost, city, stops = heapq.heappop(heap)
    if city == dst:
        return cost                          # first pop of dst is optimal
    if stops > k:                            # a (k+1)-th flight was just used; no more allowed
        continue
    for nxt, price in adj[city]:
        if best.get((nxt, stops + 1), INF) > cost + price:
            best[(nxt, stops + 1)] = cost + price
            heapq.heappush(heap, (cost + price, nxt, stops + 1))
return -1                                    # dst never reached within k + 1 flights

The visited map is keyed on (city, flights used), not on city alone. That single change restores the invariant: within a fixed flight count, cheaper really is better, so popping is safe again.

Bellman-Ford is the alternative and is often the better interview answer for this problem, because relaxing all edges k + 1 times bounds path length structurally. It needs a snapshot of the previous round's distances, or a single round can chain several edges and silently exceed the stop limit. It costs O(k * E) time and O(n) space.

2. When costs multiply

Currency Conversion Rate asks for a path product rather than a sum: converting A→B→C multiplies the two rates. Dijkstra's correctness argument depends on edge weights being non-negative additive costs, so it does not transfer directly. If the rate table is consistent, every path between two currencies gives the same product, so there is nothing to minimise. Two options:

  • BFS over the graph, carrying the running product. This is the lesson's first approach: O(V + E) per query, and it answers "is there a path, and what is the product".
  • Weighted union-find for many queries: each currency stores its ratio to its root, so a query is a find on each side and one division.

For best-rate or arbitrage variants you can take logarithms: log(a × b) = log(a) + log(b), so a product path becomes a sum path. The weights can then be negative, so use Bellman-Ford rather than Dijkstra; a negative cycle is a profitable loop.

3. Time as the ordering

Find All People With Secret is not really a shortest-path problem: meetings happen at timestamps, and the secret can only pass at a meeting if a participant already knows it at that time. Process meetings grouped by timestamp, and within each group propagate knowledge among that group's participants. The lesson does this two ways: a BFS per timestamp group starting from the people who already know, or a union-find that is reset for anyone in the group who did not end up connected to a secret holder. Ordering by time is the whole algorithm; the graph structure is secondary.

4. When an edge is a slide

In The Maze II a ball rolls until it hits a wall, so the neighbours of a cell are not the four adjacent cells but the stopping points in each direction, and the edge weight is the distance travelled to get there. Once the graph is defined that way, it is a shortest-path problem. BFS by number of rolls is wrong, because it minimises rolls rather than cells travelled. The lesson shows a correct but slower re-enqueue version (relax a stop again whenever a shorter distance arrives) and then Dijkstra over stopping points. Almost all the difficulty is in constructing the right graph.


5. Where you'll actually meet this

  • Flight and route search. Cheapest fare with at most k layovers is the literal problem, constraints and all.
  • Currency arbitrage. Log-transformed exchange graphs with negative-cycle detection is how trading systems find risk-free loops.
  • Network routing with hop limits. TTL-bounded shortest paths need the same (node, hops) state.
  • Contact tracing. Time-ordered propagation with retraction is Find All People With Secret under a different name.
  • Game physics and puzzles. Sliding-block movement where the piece continues until obstructed.

6. Problems in this chapter

Cheapest Flights Within K Stops

Cheapest route using at most k stops (k + 1 flights). Either Bellman-Ford relaxed k + 1 times over a snapshot of the previous round, or Dijkstra on (city, flights used).
Pattern: constraint as a state dimension. Target: O(k·E) time and O(n) space for Bellman-Ford; O(k·E·log(k·E)) for the heap version.

Currency Conversion Rate

Convert between currencies through a chain of exchange rates. BFS carrying a running product, or weighted union-find when there are many queries.
Pattern: multiplicative path weights. Target: O(V + E) per query with BFS; O(log V) amortized per query after an O(E log V) build with union-find.

Find All People With Secret

Determine who knows a secret after time-ordered meetings. Group meetings by timestamp, then BFS within each group from the people who know, or use union-find and reset the people who did not learn it.
Pattern: time-ordered propagation with rollback. Target: O(M log M) time for sorting plus near-linear work, O(n + M) space.

The Maze II

Shortest rolling distance to a destination, where the ball slides until it hits a wall. BFS by rolls is wrong. Re-enqueue on improvement is correct but slow; Dijkstra over stopping points, weighted by distance travelled, is the answer.
Pattern: graph construction, then standard Dijkstra. Target: O(mn(m + n) + mn log(mn)) time, O(mn) space.


7. Common pitfalls

  • Keying the visited set on the node alone when a budget exists. This is the bug in constrained shortest paths.
  • Relaxing in place in Bellman-Ford. Without a snapshot of the previous round's distances, one round can chain multiple edges and break the stop limit.
  • Applying Dijkstra to multiplicative weights directly, or to negative weights (which is what log-transformed rates produce).
  • Treating adjacent cells as neighbours in a rolling maze. Neighbours are stopping points; the distance rolled is the weight.
  • Running BFS by number of rolls in The Maze II. It minimises rolls, not cells travelled.
  • Processing meetings one at a time in the secret problem. Simultaneous meetings interact and must be handled as a group.
  • Forgetting to reset. Someone merged into a group that turned out not to know the secret must be reset in the union-find, or the answer over-reports.
  • Missing the early exit. With plain Dijkstra the first pop of the destination is final; with the extra dimension it is still final, but only because the state includes the budget.

8. Key takeaways

  1. Dijkstra's promise is conditional. It holds only when "cheapest so far" is sufficient to prune.
  2. Put the constraint in the state. (node, budget) restores the invariant at the cost of a larger graph.
  3. Bellman-Ford bounds path length structurally, which is often the shorter answer for stop limits, with a snapshot per round.
  4. Multiplicative paths need a traversal that carries a product, or weighted union-find for many queries. Logarithms turn them into sums, but the weights go negative.
  5. Sometimes the ordering is time, not distance, and grouping simultaneous events is what makes it correct.
  6. Most of the work can be graph construction. Defining a neighbour correctly is the whole of the maze problem.
  7. Why interviewers love it: they can watch you reach for Dijkstra, hit the constraint, and either patch it thoughtfully or not notice the invariant broke at all.

Order: Cheapest Flights Within K Stops → Currency Conversion Rate → Find All People With Secret → The Maze II.

Cheapest Flights Within K Stops

Core idea: Plain Dijkstra breaks here: arriving cheaply with no stops left can be worse than arriving expensively with stops to spare. Put the constraint in the state, as (city, flights used), or relax all flights k + 1 times with Bellman-Ford over a snapshot of the previous round.

Problem, rephrased

You're building the price engine for a flight-search site that spans n cities, numbered 0 to n - 1. You're given a list of flights, each [from, to, price], plus a src, a dst and k: where the traveler starts, where they're going, and the most stops (intermediate cities) they'll tolerate.

Return the cheapest total price from src to dst using at most k stops, which means at most k + 1 flights. A cheaper route that overspends the stop budget is not allowed, so sometimes the answer is a pricier, more direct routing. If no such route exists, return -1.

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.