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.
This approach uses a modified version of BFS (Breadth-First Search) with a priority queue to find paths with the minimum bitwise AND cost.
The priority queue helps in exploring paths with lower AND costs first. We start from the source node and aim to reach the target node with the least bitwise AND cost.
This Python solution makes use of a priority queue to perform a BFS-like traversal. The core operation here is maintaining the maximum bitwise AND cost using Dijkstra-like behavior where nodes are explored based on the highest AND-able path cost.
Time Complexity: O(E log V) for each query, where E is the number of edges and V is the number of vertices.
Space Complexity: O(V + E) for the adjacency list and priority queue.
This approach leverages bit manipulation to reduce the problem space. We iteratively refine the set of edges to consider by deconstructing edge weights into significant bits and use these to filter edges in consideration for paths.
The solution uses BFS with an enhancement of bitwise operations to iteratively refine and find the minimum AND path. This Java solution focuses on AND operation behavior to prune unnecessary paths early in the algorithm.
Java
JavaScript
Time Complexity: O(V * E) worst-case per query, making it possible to handle up to moderate graph sizes per query.
Space Complexity: O(V + E) representing the graph storage in adjacency lists.
We note that a positive integer performing bitwise AND operation with several other positive integers will only get smaller. Therefore, to minimize the cost of the journey, we should perform bitwise AND operation on the weights of all edges in the same connected component, and then perform the query.
So, the problem is transformed into how to find all the edges in the same connected component and perform bitwise AND operation.
We can use a union-find set to maintain the connected components.
Specifically, we traverse each edge (u, v, w) and merge u and v. Then, we traverse each edge (u, v, w) again, find the root node root of the connected component where u and v are located, and use an array g to record the result of the bitwise AND operation of the weights of all edges in each connected component.
Finally, for each query (s, t), we first judge whether s equals t. If they are equal, the answer is 0. Otherwise, we judge whether s and t are in the same connected component. If they are in the same connected component, the answer is the g value of the root node of the connected component of this query. Otherwise, the answer is -1.
The time complexity is O((n + m + q) times \alpha(n)), and the space complexity is O(n). Here, n, m, and q represent the number of nodes, edges, and queries, respectively, and \alpha(n) represents the inverse function of the Ackermann function.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: BFS with Priority Queue | Time Complexity: O(E log V) for each query, where E is the number of edges and V is the number of vertices. Space Complexity: O(V + E) for the adjacency list and priority queue. |
| Approach 2: Bitmask Optimization | Time Complexity: O(V * E) worst-case per query, making it possible to handle up to moderate graph sizes per query. Space Complexity: O(V + E) representing the graph storage in adjacency lists. |
| Greedy + Union Find | — |
| 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). |
Minimum Cost Walk in Weighted Graph - Leetcode 3108 - Python • NeetCodeIO • 12,422 views views
Watch 9 more video solutions →Practice Minimum Cost Walk in Weighted Graph with our built-in code editor and test cases.
Practice on FleetCode