Path With Minimum Maximum Weight — Binary Search the Answer + BFS [Bottleneck Shortest Path, Google, Amazon]

Problem Statement#

You are given an undirected connected weighted graph with n nodes and m edges. Find a path from node 0 to node n - 1 that minimises the maximum edge weight along the path. Return that minimax weight. (The dual variant — maximise the minimum edge weight — appears as LeetCode 1102 Path With Maximum Minimum Value.)

Constraints:

• 2 <= n <= 10^5
• n - 1 <= m <= 2 * 10^5
• 1 <= w <= 10^9

Example 1:

Input:  n = 4, edges = [[0,1,4],[1,2,2],[0,2,5],[2,3,1]], src = 0, dst = 3
Output: 4
Explanation: 0 -> 1 -> 2 -> 3 has max edge 4. The direct edge 0-2 has weight 5.

Example 2:

Input:  n = 3, edges = [[0,1,10],[1,2,20],[0,2,15]], src = 0, dst = 2
Output: 15
Explanation: Direct path 0 -> 2 has max weight 15, beating 0 -> 1 -> 2 with max 20.

Why This Problem Matters#

The bottleneck shortest path is a high-leverage interview pattern at Google, Amazon, and Meta because it tests two skills FAANG engineers need together: binary searching on the answer and modelling reachability as a graph problem. It is the algorithmic backbone behind LeetCode 1102 Path With Maximum Minimum Value, LeetCode 1631 Path With Minimum Effort, and LeetCode 778 Swim in Rising Water — three problems with the same template.

In production, minimax paths are used to plan the most reliable network route (minimise the worst link's failure probability), the smoothest hiking trail (minimise the steepest segment), the most fuel-efficient flight path (minimise the worst headwind), and disaster-evacuation routes (minimise the worst water level along the way). Whenever the optimisation is "the worst-case step matters more than the sum," reach for the bottleneck pattern.

The reason this technique earns interview points is that candidates who solve it correctly demonstrate both algorithmic taste — choosing binary search over Dijkstra-with-modified-relax — and complexity intuition. The binary-search-on-answer template solves the original problem and unlocks dozens of cousins.

The Core Insight#

If you can reach the destination using only edges with weight <= T, then the answer is <= T. The reachability predicate is monotonic: increasing T can only add edges, never remove them. Monotonicity is exactly the precondition for binary search.

We binary search on the candidate threshold T, and for each T run a BFS/DFS using only edges with weight <= T. The smallest T for which BFS reaches the destination is the answer.

There are two natural ways to bound the search space:

• Sorted unique weights: collect every edge weight, deduplicate, sort, then binary search the index. This pins the answer to an actual edge weight.
• Numerical range [wmin, wmax]: binary search the integer range directly. Useful when weights span a continuous range (O(log W) checks).

Total time: O((V + E) log K) where K is the number of unique weights or the weight range. With m = 2*10^5 edges and K = 2*10^5, this is roughly O(m log m) ~ 4 * 10^6 operations.

Alternative — modified Dijkstra: replace dist[v] = min(dist[v], dist[u] + w) with dist[v] = min(dist[v], max(dist[u], w)). Single pass, O(E log V). This is faster asymptotically and elegant once you spot it. Both approaches are accepted; the binary-search version is easier to motivate from first principles.

Visual Dry Run#

edges = [[0,1,4], [1,2,2], [0,2,5], [2,3,1]], src = 0, dst = 3. Sorted unique weights: [1, 2, 4, 5].

Loop exits with ans = 4. Notice we never enumerate paths — only reachability under the threshold.

Solution (Optimal)#

Python — Binary Search + BFS#

from collections import defaultdict, deque
 
def minMaxEdgeOnPath(n, edges, src, dst):
    adj = defaultdict(list)
    weights = set()
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
        weights.add(w)
    sorted_w = sorted(weights)
 
    def reachable(limit):
        seen = {src}
        q = deque([src])
        while q:
            u = q.popleft()
            if u == dst:
                return True
            for v, w in adj[u]:
                if w <= limit and v not in seen:
                    seen.add(v)
                    q.append(v)
        return False
 
    lo, hi, ans = 0, len(sorted_w) - 1, sorted_w[-1]
    while lo <= hi:
        mid = (lo + hi) // 2
        if reachable(sorted_w[mid]):
            ans = sorted_w[mid]
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

Python — Modified Dijkstra (single pass)#

import heapq
 
def minMaxEdgeOnPath(n, edges, src, dst):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
 
    bottleneck = [float('inf')] * n
    bottleneck[src] = 0
    heap = [(0, src)]
    while heap:
        b, u = heapq.heappop(heap)
        if u == dst:
            return b
        if b > bottleneck[u]:
            continue
        for v, w in adj[u]:
            nb = max(b, w)
            if nb < bottleneck[v]:
                bottleneck[v] = nb
                heapq.heappush(heap, (nb, v))
    return -1

JavaScript — Binary Search + BFS#

function minMaxEdgeOnPath(n, edges, src, dst) {
    const adj = Array.from({ length: n }, () => []);
    const set = new Set();
    for (const [u, v, w] of edges) {
        adj[u].push([v, w]);
        adj[v].push([u, w]);
        set.add(w);
    }
    const sorted = [...set].sort((a, b) => a - b);
 
    const reachable = (lim) => {
        const seen = new Array(n).fill(false);
        const q = [src];
        seen[src] = true;
        while (q.length) {
            const u = q.shift();
            if (u === dst) return true;
            for (const [v, w] of adj[u]) {
                if (w <= lim && !seen[v]) {
                    seen[v] = true;
                    q.push(v);
                }
            }
        }
        return false;
    };
 
    let lo = 0, hi = sorted.length - 1, ans = sorted[hi];
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (reachable(sorted[mid])) { ans = sorted[mid]; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

Complexity#

The Kruskal variant sorts edges ascending and unions them until src and dst share a component — that last edge weight is the answer.

Common Mistakes#

• Confusing min-max with max-min. Read the prompt carefully. Min-max minimises the heaviest edge; max-min (LeetCode 1102) maximises the lightest. The relax step flips accordingly.
• Using sum-Dijkstra unchanged. Standard Dijkstra minimises path sums, not bottlenecks. You must change dist[u] + w to max(dist[u], w).
• Binary searching the wrong space. If you search numeric values without monotonicity in mind, you can converge to a non-edge-weight value that no path actually realises.
• Skipping the early-exit on u == dst in BFS. Costs an unnecessary full traversal per check.
• Using DFS recursion on n = 10^5. Risk of stack overflow. Prefer iterative BFS.

Interview Tips#

• Restate the problem as "minimise the maximum edge along any source-to-destination path." Explicitly distinguish from sum-shortest-path.
• Sketch the monotonicity argument before coding: "if T works, every T' > T also works, so binary search applies."
• Walk through the smaller K versus W trade-off — it shows you can pick the right search space.
• Mention modified Dijkstra and Kruskal variants. The interviewer usually appreciates seeing three independent approaches.
• For the modified Dijkstra version, double-check the relax: max(b, w), not b + w.

Follow-up Questions#

• Maximum Minimum Path (LC 1102)? Flip relax to min(b, w) and use a max-heap. The answer is the largest bottleneck among all paths.
• Multiple sources or sinks? Push every source into the heap with bottleneck = 0. Stop at the first sink reached.
• Dynamic edges (online updates)? Use a link-cut tree or maintain a Boruvka-style MST — bottleneck path between two nodes equals the maximum edge on the path between them in the MST.
• Negative weights? Bottleneck paths handle them fine; only the comparison <= matters.

Key Takeaways#

• Bottleneck shortest path = minimise the maximum edge on a path; the dual maximises the minimum.
• Binary search on the answer + BFS reachability check is the most teachable approach in interviews.
• Modified Dijkstra with max(b, w) relax achieves a single-pass solution in O(E log V).
• Kruskal-style union-find on sorted edges yields the same answer in O(E log E).
• The pattern powers LeetCode 1102, 1631, and 778, plus production network-routing and trail-planning problems.
• Companies that ask this: Google, Amazon, Meta, Uber, Bloomberg, Stripe, Apple.