Watch 10 video solutions for Minimum Cost Walk in Weighted Graph, a hard level problem involving Array, Bit Manipulation, Union Find. This walkthrough by NeetCodeIO has 12,422 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is an undirected weighted graph with n vertices labeled from 0 to n - 1.
You are given the integer n and an array edges, where edges[i] = [ui, vi, wi] indicates that there is an edge between vertices ui and vi with a weight of wi.
A walk on a graph is a sequence of vertices and edges. The walk starts and ends with a vertex, and each edge connects the vertex that comes before it and the vertex that comes after it. It's important to note that a walk may visit the same edge or vertex more than once.
The cost of a walk starting at node u and ending at node v is defined as the bitwise AND of the weights of the edges traversed during the walk. In other words, if the sequence of edge weights encountered during the walk is w0, w1, w2, ..., wk, then the cost is calculated as w0 & w1 & w2 & ... & wk, where & denotes the bitwise AND operator.
You are also given a 2D array query, where query[i] = [si, ti]. For each query, you need to find the minimum cost of the walk starting at vertex si and ending at vertex ti. If there exists no such walk, the answer is -1.
Return the array answer, where answer[i] denotes the minimum cost of a walk for query i.
Example 1:
Input: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
Output: [1,-1]
Explanation:
To achieve the cost of 1 in the first query, we need to move on the following edges: 0->1 (weight 7), 1->2 (weight 1), 2->1 (weight 1), 1->3 (weight 7).
In the second query, there is no walk between nodes 3 and 4, so the answer is -1.
Example 2:
Input: n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
Output: [0]
Explanation:
To achieve the cost of 0 in the first query, we need to move on the following edges: 1->2 (weight 1), 2->1 (weight 6), 1->2 (weight 1).
Constraints:
2 <= n <= 1050 <= edges.length <= 105edges[i].length == 30 <= ui, vi <= n - 1ui != vi0 <= wi <= 1051 <= query.length <= 105query[i].length == 20 <= si, ti <= n - 1si != tiProblem Overview: You are given an undirected weighted graph and multiple queries asking for the minimum possible cost of a walk between two nodes. The cost of a walk depends on bitwise operations applied to the weights along the path, which means revisiting nodes or choosing specific edges can reduce the final cost.
Approach 1: BFS with Priority Queue (O(E log V) time, O(V + E) space)
This approach treats the graph like a shortest-path problem and explores nodes using a priority queue. Instead of summing weights, each step applies a bitwise operation to accumulate the walk cost. The algorithm repeatedly extracts the current best candidate from the heap and relaxes neighboring edges, similar to Dijkstra’s algorithm. You maintain the best cost found for each node and update it whenever a lower bitwise result is discovered. This approach works well when you want an intuitive path exploration strategy and need to process queries dynamically on a graph.
Approach 2: Bitmask Optimization with Union-Find (O(E log W + Q) time, O(N) space)
The key observation is that the minimum walk cost between two nodes depends on the bitwise AND of edges within the same connected component. Instead of exploring paths repeatedly, group nodes using Union Find. While processing edges, track the cumulative bitwise mask representing all edges in that component. Because bitwise AND only decreases as more edges are included, any walk inside the component can potentially use edges that reduce the final value. Queries then become simple component checks: if two nodes belong to the same set, return the stored mask; otherwise return -1. This technique relies heavily on bit manipulation and drastically reduces repeated traversal.
Recommended for interviews: The union-find + bitmask insight is typically the expected optimal solution. A brute traversal such as BFS with a priority queue demonstrates understanding of graph search and path relaxation, but the optimized component-based reasoning shows stronger algorithmic insight. Interviewers usually look for the realization that the walk can reuse edges, allowing the entire component’s bitwise properties to determine the answer.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Priority Queue | O(E log V) | O(V + E) | Useful when exploring paths dynamically or when the component insight is not obvious. |
| Bitmask Optimization with Union-Find | O(E log W + Q) | O(N) | Best for multiple queries. Precompute component bitmasks and answer each query in near O(1). |