Shortest Path & MST

Problem: times[i] = (u, v, w) is a directed edge from node u to v taking w time. A signal starts at k. Return the time until all n nodes have received it, or -1 if some never do.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ k ≤ n ≤ 100 · 1 ≤ times.length ≤ 6000 · times[i].length == 3 · 1 ≤ ui, vi ≤ n · ui != vi · 0 ≤ wi ≤ 100 · All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

From brute force to the pattern: BFS ignores weights; trying all paths is exponential; Bellman–Ford is O(V · E). With non-negative weights Dijkstra is O(E log E).

Spot it: Shortest travel times from one source with non-negative weights → Dijkstra. The answer is the largest of those shortest times (the last node to hear the signal).

Approach:

1. Build an adjacency list u → [(v, w), …].
2. Push (0, k) onto a min-heap. dist stores each node's final shortest time.
3. Pop the smallest time. If that node is already settled, skip it; otherwise settle it and push (time + w, v) for every unsettled neighbour.
4. If all n nodes are settled, return the largest time; else -1.

import heapq

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = {}
        for u, v, w in times:
            if u not in graph:
                graph[u] = []
            graph[u].append((v, w))
        dist = {}                      # node -> final shortest time
        heap = [(0, k)]                # (time so far, node)
        while heap:
            time, node = heapq.heappop(heap)
            if node in dist:
                continue               # already settled by a faster route
            dist[node] = time
            for nxt, w in graph.get(node, []):
                if nxt not in dist:
                    heapq.heappush(heap, (time + w, nxt))
        if len(dist) < n:
            return -1                  # some node never received the signal
        return max(dist.values())

What the code is doing, line by line:

1. graph: adjacency list of outgoing edges with their weights.
2. heap = [(0, k)]: tuples compare by their first item, so the heap always pops the smallest known time.
3. if node in dist: continue: a node can be pushed several times with different times; only the first pop (the smallest) counts. This "lazy deletion" replaces a decrease-key operation.
4. dist[node] = time: final. With non-negative weights, no later route can be shorter than the smallest time on the heap.
5. heapq.heappush(heap, (time + w, nxt)): a candidate time for each neighbour.
6. if len(dist) < n: return -1, else max(dist.values()): everyone must be reached, and the slowest arrival is the answer.

Dry run on the example:

times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2 (LeetCode Example 1). Returns 2.

All 4 nodes are settled; the largest time is 2.

Edge cases to test:

• An unreachable node → −1.
• A single node → 0.
• Several edges between the same pair.

Complexity: O(E log E) time with a binary heap, O(V + E) space.

Problem: Connect all points on a plane so every pair is connected by some path. The cost of an edge between two points is their Manhattan distance |x1 − x2| + |y1 − y2|. Return the minimum total cost.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ points.length ≤ 1000 · -10⁶ ≤ xi, yi ≤ 10⁶ · All pairs (xi, yi) are distinct.

From brute force to the pattern: Trying all spanning trees is exponential. Prim's with a heap is O(n² log n) on this complete graph (or O(n²) with an array); Kruskal sorts the n² edges.

Spot it: "Connect everything as cheaply as possible" is a minimum spanning tree. The graph is complete (every pair can be connected), so Prim's algorithm, which grows one tree from a start point, is a natural fit.

Approach:

1. Start the tree with point 0: push (0, 0) = (cost to attach, point) onto a min-heap.
2. Pop the cheapest entry. If that point is already in the tree, skip it. Otherwise add it and its cost to the total.
3. Push (distance, j) for every point j not yet in the tree.
4. Stop when all points are in the tree.

import heapq

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        in_tree = [False] * n
        heap = [(0, 0)]          # (cost to attach this point, point index)
        total = 0
        added = 0
        while added < n:
            cost, i = heapq.heappop(heap)
            if in_tree[i]:
                continue         # already attached more cheaply
            in_tree[i] = True
            total = total + cost
            added = added + 1
            xi, yi = points[i]
            for j in range(n):
                if not in_tree[j]:
                    xj, yj = points[j]
                    heapq.heappush(heap, (abs(xi - xj) + abs(yi - yj), j))
        return total

What the code is doing, line by line:

1. in_tree: which points are already connected.
2. heap = [(0, 0)]: attaching the first point is free.
3. if in_tree[i]: continue: a point can be on the heap several times; only its cheapest entry (popped first) is used.
4. total = total + cost: the cheapest edge leaving the tree is always safe to add. That's the cut property that makes Prim correct.
5. for j in range(n): ... heappush(...): new candidate edges from the point we just added.
6. while added < n: a spanning tree is finished when all n points are in it (n − 1 edges).

Dry run on the example:

points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] (LeetCode Example 1). Returns 20.

Edge cases to test:

• A single point → 0.
• Duplicate points (distance 0).
• Collinear points.

Complexity: O(n² log n) time (up to n² heap pushes), O(n²) heap space. (An array-based Prim without a heap is O(n²) time, O(n) space.)

Problem: Return the cheapest price from src to dst using at most k stops (k + 1 flights), or −1.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 100 · 0 ≤ flights.length ≤ (n * (n - 1) / 2) · flights[i].length == 3 · 0 ≤ fromi, toi < n · fromi != toi · 1 ≤ pricei ≤ 10⁴ · There will not be any multiple flights between two cities. · 0 ≤ src, dst, k < n · src != dst

From brute force to the pattern: DFS over all routes is exponential; limited Bellman–Ford is O(kE).

Spot it: A shortest path with a limit on the number of edges. Bellman–Ford's round i finds the best prices using at most i edges, so run exactly k + 1 rounds. Relax from a copy of the previous round so one round never chains two flights.

Why not another pattern? Plain Dijkstra ignores the stop limit: a cheaper path with too many stops can block a valid one.

Approach:

1. price[src] = 0, others ∞.
2. Repeat k + 1 times: new = price[:]; for each flight (u, v, w): new[v] = min(new[v], price[u] + w).
3. Return price[dst] or −1.

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        INF = float("inf")
        price = [INF] * n
        price[src] = 0
        for _ in range(k + 1):  # at most k + 1 flights
            new = price[:]  # read old values so each round adds only one flight
            for u, v, w in flights:
                if price[u] + w < new[v]:
                    new[v] = price[u] + w
            price = new
        return price[dst] if price[dst] < INF else -1

What the code is doing, line by line:

1. After round i, price[v] is the cheapest cost using at most i flights.
2. Reading from price (old) while writing to new prevents using two flights in one round.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• src == dst.
• A cheap route with too many stops.
• No route → −1.

Complexity: O(k · E) time, O(n) space.

Problem: Edges have success probabilities. Return the maximum probability of a path from start_node to end_node.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10^4 · 0 ≤ start, end < n · start != end · 0 ≤ a, b < n · a != b · 0 ≤ succProb.length == edges.length ≤ 2*10^4 · 0 ≤ succProb[i] ≤ 1 · There is at most one edge between every two nodes.

From brute force to the pattern: Bellman–Ford is O(VE); Dijkstra is O(E log V).

Spot it: Multiplying by numbers ≤ 1 never increases the probability, just as adding non-negative weights never decreases a distance → Dijkstra with a max-heap.

Why not another pattern? BFS ignores weights; Bellman–Ford is O(VE).

Approach:

1. best[start] = 1; heap of (−prob, node).
2. Pop the most probable node; skip stale entries; stop at the end node.
3. Relax: p · edge_prob > best[v] → update and push.

import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        adj = [[] for _ in range(n)]
        for (a, b), p in zip(edges, succProb):
            adj[a].append((b, p))
            adj[b].append((a, p))
        best = [0.0] * n
        best[start_node] = 1.0
        heap = [(-1.0, start_node)]  # max-heap via negation
        while heap:
            neg, u = heapq.heappop(heap)
            p = -neg
            if u == end_node:
                return p  # the first time we pop it, it's optimal
            if p < best[u]:
                continue  # stale entry
            for v, q in adj[u]:
                if p * q > best[v]:
                    best[v] = p * q
                    heapq.heappush(heap, (-best[v], v))
        return 0.0

What the code is doing, line by line:

1. Probabilities only shrink along a path, which is what makes Dijkstra's greedy choice valid.
2. Stale heap entries are skipped by comparing with best.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No path → 0.
• start == end → 1 (not in constraints but handled).
• Several paths with equal probability.

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

Problem: A path's effort is its largest absolute height difference between consecutive cells. Return the minimum effort from top-left to bottom-right.

Solve it on LeetCode ↗

Constraints: rows == heights.length · columns == heights[i].length · 1 ≤ rows, columns ≤ 100 · 1 ≤ heights[i][j] ≤ 10⁶

From brute force to the pattern: All paths are exponential; binary search + BFS is O(mn log H); Dijkstra is O(mn log mn).

Spot it: Minimising a maximum along a path still works with Dijkstra: the cost max(effort so far, step) never decreases along a path.

Why not another pattern? Plain BFS ignores the costs; DP right/down only misses paths that go up or left.

Approach:

1. effort[0][0] = 0; heap (0, 0, 0).
2. Pop the smallest effort; for each neighbour: e = max(effort, |Δh|); if smaller, update and push.
3. Return when the target is popped.

import heapq

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        effort = [[float("inf")] * cols for _ in range(rows)]
        effort[0][0] = 0
        heap = [(0, 0, 0)]
        while heap:
            e, r, c = heapq.heappop(heap)
            if (r, c) == (rows - 1, cols - 1):
                return e
            if e > effort[r][c]:
                continue  # stale
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols:
                    ne = max(e, abs(heights[nr][nc] - heights[r][c]))  # the path's worst step
                    if ne < effort[nr][nc]:
                        effort[nr][nc] = ne
                        heapq.heappush(heap, (ne, nr, nc))
        return 0

What the code is doing, line by line:

1. The cost of extending a path is max, which is monotone, so Dijkstra's first pop of a cell is optimal.
2. The answer is returned as soon as the target is popped.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A 1×1 grid → 0.
• A detour that avoids a big step.
• All equal heights → 0.

Complexity: O(mn log(mn)) time, O(mn) space.

Problem: A path's safeness is the minimum distance from any of its cells to the nearest thief. Maximise it from (0, 0) to (n−1, n−1).

Solve it on LeetCode ↗

Constraints: 1 ≤ grid.length == n ≤ 400 · grid[i].length == n · grid[i][j] is either 0 or 1. · There is at least one thief in the grid.

From brute force to the pattern: BFS from every cell to find thieves is O(n⁴); multi-source BFS + Dijkstra is O(n² log n).

Spot it: Two steps: multi-source BFS from all thieves computes each cell's distance to the nearest thief. Then maximise the minimum along a path: Dijkstra with a max-heap (the bottleneck path).

Why not another pattern? Computing distances by BFS from every cell is O(n⁴).

Approach:

1. BFS from all thieves at once: dist[r][c].
2. Max-heap from (0, 0) with value dist[0][0]; the value of a path is min(path value, dist[cell]).
3. Return when the target is popped.

import heapq
from collections import deque

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dist = [[-1] * n for _ in range(n)]
        queue = deque()
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    dist[r][c] = 0  # every thief is a BFS source
                    queue.append((r, c))
        while queue:
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] < 0:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
        best = [[-1] * n for _ in range(n)]
        best[0][0] = dist[0][0]
        heap = [(-dist[0][0], 0, 0)]  # max-heap on the path's safeness
        while heap:
            neg, r, c = heapq.heappop(heap)
            safe = -neg
            if (r, c) == (n - 1, n - 1):
                return safe
            if safe < best[r][c]:
                continue
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < n and 0 <= nc < n:
                    s = min(safe, dist[nr][nc])  # the path is only as safe as its worst cell
                    if s > best[nr][nc]:
                        best[nr][nc] = s
                        heapq.heappush(heap, (-s, nr, nc))
        return 0

What the code is doing, line by line:

1. Multi-source BFS layer d is exactly the cells at distance d from the nearest thief.
2. Safeness along a path only decreases (min), so Dijkstra with a max-heap finds the best bottleneck.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A thief at the start or end → 0.
• One thief.
• Grid of size 1.

Complexity: O(n² log n) time, O(n²) space.

Problem: Unsafe cells cost 1 health. Can you get from (0, 0) to (m−1, n−1) and still have health ≥ 1?

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 50 · 2 ≤ m * n · 1 ≤ health ≤ m + n · grid[i][j] is either 0 or 1.

From brute force to the pattern: Trying all paths is exponential; 0-1 BFS is linear.

Spot it: Minimise the number of unsafe cells on a path: a shortest path with weights 0 and 1 → 0-1 BFS with a deque (push front for cost 0, back for cost 1).

Why not another pattern? Plain BFS counts steps, not unsafe cells; Dijkstra works but 0-1 BFS is simpler and linear.

Approach:

1. cost[0][0] = grid[0][0]; deque with the start.
2. Pop front; for each neighbour nc = cost + grid[nr][nc]; if better, update; push front if the cell is safe, back otherwise.
3. Return cost[end] < health.

from collections import deque

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])
        cost = [[float("inf")] * n for _ in range(m)]  # fewest unsafe cells to reach each cell
        cost[0][0] = grid[0][0]
        dq = deque([(0, 0)])
        while dq:
            r, c = dq.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n:
                    w = grid[nr][nc]
                    if cost[r][c] + w < cost[nr][nc]:
                        cost[nr][nc] = cost[r][c] + w
                        if w == 0:
                            dq.appendleft((nr, nc))  # free step: same distance level
                        else:
                            dq.append((nr, nc))  # costs one health
        return cost[m - 1][n - 1] < health  # at least 1 health left

What the code is doing, line by line:

1. The deque stays sorted by cost: cost-0 moves go to the front, cost-1 moves to the back.
2. The start cell counts too if it's unsafe.
3. Health stays positive if the unsafe cells on the best path are fewer than health.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Unsafe start cell.
• Health exactly equal to the unsafe count → false.
• A detour around unsafe cells.

Complexity: O(m · n) time and space.

Problem: Return the indices of critical MST edges (removing them increases the MST weight) and pseudo-critical ones (in some MST, not all).

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 100 · 1 ≤ edges.length ≤ min(200, n * (n - 1) / 2) · edges[i].length == 3 · 0 ≤ ai < bi < n · 1 ≤ weighti ≤ 1000 · All pairs (ai, bi) are distinct.

From brute force to the pattern: Listing every MST is exponential; two Kruskal runs per edge are O(E²).

Spot it: With ≤ 200 edges, test each edge with Kruskal + union-find: skipping it makes the MST heavier (or disconnected) → critical; otherwise, forcing it in first still gives the optimal weight → pseudo-critical.

Why not another pattern? Enumerating all MSTs is exponential.

Approach:

1. Sort edge indices by weight; best = kruskal().
2. For each edge e: kruskal(skip=e) > best → critical.
3. Else kruskal(force=e) == best → pseudo-critical.

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        order = sorted(range(len(edges)), key=lambda i: edges[i][2])

        def kruskal(skip=-1, force=-1):
            parent = list(range(n))

            def find(x):
                while parent[x] != x:
                    parent[x] = parent[parent[x]]
                    x = parent[x]
                return x

            weight = 0
            used = 0
            if force >= 0:
                a, b, w = edges[force]
                parent[find(a)] = find(b)  # this edge goes in first
                weight += w
                used += 1
            for i in order:
                if i == skip:
                    continue
                a, b, w = edges[i]
                ra, rb = find(a), find(b)
                if ra != rb:
                    parent[ra] = rb  # cheapest edge joining two components
                    weight += w
                    used += 1
            return weight if used == n - 1 else float("inf")  # inf: not connected

        best = kruskal()
        critical, pseudo = [], []
        for i in range(len(edges)):
            if kruskal(skip=i) > best:
                critical.append(i)  # every MST needs it
            elif kruskal(force=i) == best:
                pseudo.append(i)  # some MST can use it
        return [critical, pseudo]

What the code is doing, line by line:

1. Kruskal adds the cheapest edge that connects two components; union-find detects that.
2. If the graph without e has a heavier MST (or is disconnected), e is in every MST.
3. Otherwise, if an MST containing e still has the optimal weight, e is in some but not all MSTs.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal weights (everything pseudo-critical).
• A bridge edge (critical).
• Tie-breaking between equal weights.

Complexity: O(E² · α(n)) time after sorting, O(n) space.

Problem: Build a spanning tree containing all must edges; up to k optional edges may double their strength. Maximise the weakest edge of the tree, or −1.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10⁵ · 1 ≤ edges.length ≤ 10⁵ · edges[i] = [ui, vi, si, musti] · 0 ≤ ui, vi < n · ui != vi · 1 ≤ si ≤ 10⁵ · musti is either 0 or 1. · 0 ≤ k ≤ n · There are no duplicate edges.

From brute force to the pattern: Enumerating spanning trees is exponential; binary search + three union-find passes is near-linear per check.

Spot it: "Maximise the minimum" → binary search on the stability x. For a fixed x, greedily build the tree with union-find: must edges first (each needs strength ≥ x), then optional edges already ≥ x (free), then edges that reach x only when doubled (each costs one upgrade).

Why not another pattern? Trying every spanning tree is exponential; a single maximum spanning tree ignores the must edges and the upgrade budget.

Approach:

1. Must edges forming a cycle → −1. Graph not connectable even using every edge → −1.
2. feasible(x): union the must edges (fail if any has strength < x); add optional edges with s ≥ x; then those with 2s ≥ x, counting upgrades; feasible if connected with ≤ k upgrades.
3. Binary-search the largest feasible x.

class Solution:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:
        def build(x):  # can we span the graph with every edge >= x? returns upgrades used, or -1
            parent = list(range(n))

            def find(a):
                while parent[a] != a:
                    parent[a] = parent[parent[a]]
                    a = parent[a]
                return a

            joined = 0
            for u, v, s, must in edges:
                if must:
                    if s < x or find(u) == find(v):
                        return -1  # a required edge is too weak, or makes a cycle
                    parent[find(u)] = find(v)
                    joined += 1
            for u, v, s, must in edges:
                if not must and s >= x and find(u) != find(v):
                    parent[find(u)] = find(v)  # strong enough as it is
                    joined += 1
            upgrades = 0
            for u, v, s, must in edges:
                if not must and s < x <= 2 * s and find(u) != find(v):
                    parent[find(u)] = find(v)  # needs doubling
                    joined += 1
                    upgrades += 1
            return upgrades if joined == n - 1 else -1

        if build(0) < 0:
            return -1  # impossible even without a strength requirement
        lo, hi = 0, 2 * max(s for _, _, s, _ in edges)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            used = build(mid)
            if 0 <= used <= k:
                lo = mid  # stability mid is achievable
            else:
                hi = mid - 1
        return lo

What the code is doing, line by line:

1. Must edges are always in the tree, so they cap the stability and can't be upgraded.
2. Using free edges before upgradable ones minimises upgrades (spanning trees form a matroid, so the greedy is optimal).
3. If stability x is achievable, every smaller value is too, so binary search applies.
4. build(0) checks that a spanning tree exists at all (and that must edges have no cycle).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Must edges with a cycle → −1.
• Disconnected graph → −1.
• k = 0 (no upgrades).

Complexity: O(E · α(n) · log S) time, O(n) space.

Problem: Odd actions should move right/down, even actions left/up; violating moves and waits cost penalty of the current cell, and every move pays the destination's entry cost (i + 1)(j + 1). Return the minimum total cost to reach the bottom-right cell.

Solve it on LeetCode ↗

Constraints: 1 ≤ m, n ≤ 10⁵ · 2 ≤ m * n ≤ 10⁵ · penalty.length == m · penalty[i].length == n · 0 ≤ penalty[i][j] ≤ 10⁵

From brute force to the pattern: Exploring action sequences is exponential; Dijkstra over 2·m·n states is near-linear.

Spot it: Costs depend on the cell and whether the next action is odd or even, so the state is (cell, parity). All costs are positive → Dijkstra on 2 · m · n states with up to 5 edges each (4 moves + wait).

Why not another pattern? A right/down DP misses that waiting (or stepping back) can be cheaper to fix the parity.

Approach:

1. Start: dist[(0, 0), odd] = 1 (the entry cost of (0, 0)).
2. From (r, c, p): each neighbour costs its entry cost, plus penalty[r][c] if the direction violates p; waiting costs penalty[r][c]. The parity flips either way.
3. Return the smallest distance to the target in either parity.

import heapq

class Solution:
    def minCost(self, m: int, n: int, penalty: List[List[int]]) -> int:
        INF = float("inf")
        dist = [[[INF, INF] for _ in range(n)] for _ in range(m)]  # [cell][next action is odd(0) / even(1)]
        dist[0][0][0] = 1  # pay the entrance of (0, 0)
        heap = [(1, 0, 0, 0)]
        while heap:
            d, r, c, p = heapq.heappop(heap)
            if (r, c) == (m - 1, n - 1):
                return d
            if d > dist[r][c][p]:
                continue  # stale entry
            q = 1 - p  # parity after this action
            options = [(r, c, penalty[r][c])]  # wait
            for nr, nc, forward in ((r + 1, c, True), (r, c + 1, True), (r - 1, c, False), (r, c - 1, False)):
                if 0 <= nr < m and 0 <= nc < n:
                    follows = forward if p == 0 else not forward  # odd: right/down, even: left/up
                    cost = (nr + 1) * (nc + 1) + (0 if follows else penalty[r][c])
                    options.append((nr, nc, cost))
            for nr, nc, cost in options:
                if d + cost < dist[nr][nc][q]:
                    dist[nr][nc][q] = d + cost
                    heapq.heappush(heap, (d + cost, nr, nc, q))
        return -1

What the code is doing, line by line:

1. Parity 0 means the next action is odd-numbered (right/down follow the rule); parity 1 means even (left/up follow it).
2. Every action flips the parity, whether it was a move or a wait.
3. All costs are positive (entry costs are at least 1), so Dijkstra's first pop of the target is optimal.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Waiting on a zero-penalty cell to fix the parity.
• A single row or column.
• Stepping back being cheaper than waiting.

Complexity: O(mn log(mn)) time, O(mn) space.

Problem: In a DAG with offline nodes, find a path from 0 to n−1 through online nodes with total cost ≤ k that maximises its smallest edge cost, or −1.

Solve it on LeetCode ↗

From brute force to the pattern: All paths can be exponential; binary search + DAG DP is O((n + m) log m).

Spot it: "Maximise the minimum edge" → binary search on the score x: using only edges with cost ≥ x, is the shortest path (a DP in topological order, since it's a DAG) at most k? Feasibility only gets harder as x grows.

Why not another pattern? Enumerating all paths in a DAG can be exponential.

Approach:

1. Topological order of the DAG (Kahn).
2. ok(x): DP dist[v] = min(dist[u] + c) over edges with c ≥ x and online endpoints; feasible if dist[n − 1] ≤ k.
3. Binary-search x over the sorted distinct costs; −1 if even x = 0 fails.

from collections import deque

class Solution:
    def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
        n = len(online)
        out = [[] for _ in range(n)]
        indeg = [0] * n
        for u, v, c in edges:
            out[u].append((v, c))
            indeg[v] += 1
        order = []
        queue = deque(i for i in range(n) if indeg[i] == 0)
        while queue:
            u = queue.popleft()
            order.append(u)
            for v, _ in out[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)

        def cheapest_with_min(x):  # cheapest 0 -> n-1 path using only edges of cost >= x
            INF = float("inf")
            dist = [INF] * n
            dist[0] = 0
            for u in order:
                if dist[u] == INF or not online[u]:
                    continue
                for v, c in out[u]:
                    if c >= x and online[v] and dist[u] + c < dist[v]:
                        dist[v] = dist[u] + c
            return dist[n - 1]

        costs = sorted({c for _, _, c in edges})
        if cheapest_with_min(0) > k:
            return -1  # no valid path at all
        lo, hi = 0, len(costs) - 1  # answer is one of the edge costs
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if cheapest_with_min(costs[mid]) <= k:
                lo = mid  # a path with every edge >= costs[mid] fits the budget
            else:
                hi = mid - 1
        return costs[lo]

What the code is doing, line by line:

1. The score of the best path is one of the edge costs, so searching over sorted costs suffices.
2. Raising the threshold removes edges, so the cheapest path can only get more expensive: monotone.
3. In a DAG, relaxing edges in topological order gives shortest paths in linear time.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No valid path → −1.
• Offline intermediate nodes.
• Budget exactly equal to a path's cost.

Complexity: O((n + m) log m) time, O(n + m) space.

Problem: From each shop i, either buy locally, or travel empty to shop j, buy there, and return carrying apples (roads cost cost · tax). Return the minimum for every shop.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 1000 · prices.length == n · 1 ≤ prices[i] ≤ 10⁹ · 0 ≤ roads.length ≤ min(n × (n - 1) / 2, 2000) · roads[i] = [ui, vi, costi, taxi] · 0 ≤ ui, vi ≤ n - 1 · ui != vi · 1 ≤ costi ≤ 10⁹ · 1 ≤ taxi ≤ 100 · There are no repeated edges.

From brute force to the pattern: Trying every shop j with separate shortest paths needs the same distances; the layered graph computes them in one search per start.

Spot it: Model the trip as a shortest path on two copies of the graph: layer 0 (travelling empty, edge cost cost) and layer 1 (carrying, edge cost cost · tax). Buying at shop j jumps from (j, 0) to (j, 1) for price[j]. Then ans[i] = distance from (i, 0) to (i, 1) → Dijkstra.

Why not another pattern? Trying every shop j with two separate shortest paths is the same work but more code; one layered Dijkstra per start handles it.

Approach:

1. Adjacency list with (v, cost, tax).
2. For each start i: Dijkstra over states (node, carrying); buying is the edge (j, 0) → (j, 1) with weight price[j].
3. Stop when (i, 1) is popped.

import heapq

class Solution:
    def minCost(self, n: int, prices: List[int], roads: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(n)]
        for u, v, cost, tax in roads:
            adj[u].append((v, cost, tax))
            adj[v].append((u, cost, tax))
        answer = []
        for start in range(n):
            dist = {(start, 0): 0}
            heap = [(0, start, 0)]  # (cost so far, shop, carrying apples?)
            while heap:
                d, u, carry = heapq.heappop(heap)
                if (u, carry) == (start, 1):
                    answer.append(d)  # back home with apples
                    break
                if d > dist.get((u, carry), float("inf")):
                    continue
                moves = [] if carry else [(u, 1, prices[u])]  # buy apples here
                for v, cost, tax in adj[u]:
                    moves.append((v, carry, cost * tax if carry else cost))  # carrying is pricier
                for v, c2, w in moves:
                    if d + w < dist.get((v, c2), float("inf")):
                        dist[(v, c2)] = d + w
                        heapq.heappush(heap, (d + w, v, c2))
        return answer

What the code is doing, line by line:

1. Layer 0 is "still looking for apples", layer 1 is "carrying apples home".
2. The only way into layer 1 is buying, so every path from (i, 0) to (i, 1) is a valid plan, including buying locally (zero roads).
3. Positive weights make Dijkstra exact; each start costs O((n + m) log n).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Buying locally is cheapest.
• No roads.
• High tax makes far shops useless.

Complexity: O(n · (n + m) log n) time, O(n + m) space (n ≤ 1000, m ≤ 2000).

Problem: Travel from city 0 to city n−1 within maxTime, paying each passed city's fee. Return the minimum total fee, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ maxTime ≤ 1000 · n == passingFees.length · 2 ≤ n ≤ 1000 · n - 1 ≤ edges.length ≤ 1000 · 0 ≤ xi, yi ≤ n - 1 · 1 ≤ timei ≤ 1000 · 1 ≤ passingFees[j] ≤ 1000 · The graph may contain multiple edges between two nodes. · The graph does not contain self loops.

From brute force to the pattern: Exploring all paths is exponential; the time-indexed DP is O(maxTime · E).

Spot it: A shortest path with a resource limit: the state needs the time used. With maxTime ≤ 1000 and 1000 edges, a DP over time relaxing every edge is fast (a constrained Dijkstra also works).

Why not another pattern? Plain Dijkstra on fees ignores the time limit; on time it ignores fees.

Approach:

1. best[t][v] = min fee arriving at v at time t; best[0][0] = fee[0].
2. For t ascending, for each edge both ways: best[t + w][v] = min(best[t][u] + fee[v]).
3. Answer: min over t ≤ maxTime of best[t][n − 1].

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        n = len(passingFees)
        INF = float("inf")
        best = [[INF] * n for _ in range(maxTime + 1)]  # best[t][v]: cheapest fees reaching v at time t
        best[0][0] = passingFees[0]
        for t in range(maxTime + 1):
            row = best[t]
            for u, v, w in edges:
                if t + w > maxTime:
                    continue
                if row[u] < INF and row[u] + passingFees[v] < best[t + w][v]:
                    best[t + w][v] = row[u] + passingFees[v]  # drive u -> v
                if row[v] < INF and row[v] + passingFees[u] < best[t + w][u]:
                    best[t + w][u] = row[v] + passingFees[u]  # drive v -> u
        answer = min(best[t][n - 1] for t in range(maxTime + 1))
        return answer if answer < INF else -1

What the code is doing, line by line:

1. Times only increase along a path, so processing t in increasing order sees every predecessor first.
2. Fees are paid on entering a city (and for the start city).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Too far in the time limit → −1.
• Parallel roads with different times.
• Cheaper but slower route.

Complexity: O(maxTime · E) time, O(maxTime · n) space.