Skip to main content
Talentd

Minimum Cost Walk in Weighted Graph - Solution & Explanation

HardArrayBit ManipulationUnion FindGraph18 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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 <= 105
  • 0 <= edges.length <= 105
  • edges[i].length == 3
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 0 <= wi <= 105
  • 1 <= query.length <= 105
  • query[i].length == 2
  • 0 <= si, ti <= n - 1
  • si != ti

Approach Overview

Problem 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 1: Approach 1: BFS with Priority Queue

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Bitmask Optimization

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Greedy + Union Find

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with Priority QueueO(E log V)O(V + E)Useful when exploring paths dynamically or when the component insight is not obvious.
Bitmask Optimization with Union-FindO(E log W + Q)O(N)Best for multiple queries. Precompute component bitmasks and answer each query in near O(1).

Video Solution

Minimum Cost Walk in Weighted Graph - Leetcode 3108 - Python • NeetCodeIO • 12,692 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Cost Walk in Weighted Graph easy or hard?
Minimum Cost Walk in Weighted Graph is classified as a Hard problem. The difficulty comes from recognizing that a walk can revisit nodes, which allows component-level bitwise reasoning instead of standard shortest-path logic.
Minimum Cost Walk in Weighted Graph Python/Java solution
Python and C++ implementations typically use a priority queue with adjacency lists for the BFS-style approach. Java and JavaScript implementations often use Union-Find with bitmask tracking to preprocess components and answer queries efficiently.
How to solve Minimum Cost Walk in Weighted Graph in O(n)?
A near-linear solution uses Union-Find to group nodes into connected components while maintaining a bitwise mask of edge weights in each component. After preprocessing edges in roughly O(E), queries only require checking the component parent of each node, which takes almost constant time with path compression.
What is the best approach for Minimum Cost Walk in Weighted Graph?
The most efficient approach uses Union-Find combined with bitmask tracking. All nodes in the same connected component share a cumulative bitwise mask derived from their edges. After building components in O(E log W) time, each query can be answered in nearly O(1) by checking whether both nodes belong to the same component and returning the stored mask.
Is Minimum Cost Walk in Weighted Graph asked at Google/Amazon/Meta?
Graph problems involving Union-Find, bitwise reasoning, and path optimization frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that mix graph traversal with bit manipulation are common in advanced algorithm rounds.
What data structure is used in Minimum Cost Walk in Weighted Graph?
Key data structures include adjacency lists for graph traversal, priority queues for BFS/Dijkstra-style exploration, and Union-Find (Disjoint Set Union) for efficiently grouping connected components. Bitmasks are used to track cumulative bitwise properties of edges.
What is the time complexity of Minimum Cost Walk in Weighted Graph?
Using a BFS or Dijkstra-style traversal with a priority queue takes O(E log V) time and O(V + E) space. The optimized Union-Find with bitmask approach preprocesses edges in about O(E log W) time and answers queries in O(1), which is faster for large numbers of queries.

Ready to solve this problem?

Practice Minimum Cost Walk in Weighted Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays