LeetCode 3108 - Minimum Cost Walk in Weighted Graph

This problem gives us an undirected weighted graph with n vertices and up to 10^5 edges. Each edge connects two vertices and has an integer weight. For every query [s, t], we must determine the minimum possible cost of any walk from node s to node t.

leetcodehardarraybit-manipulationunion-findgraph-theory

LeetCode Problem 3108

Difficulty: 🔴 Hard
Topics: Array, Bit Manipulation, Union-Find, Graph Theory

Solution

Problem Understanding

This problem gives us an undirected weighted graph with n vertices and up to 10^5 edges. Each edge connects two vertices and has an integer weight.

For every query [s, t], we must determine the minimum possible cost of any walk from node s to node t.

The key detail is the definition of a walk cost. If the walk traverses edge weights:

$$w_0, w_1, w_2, \dots, w_k$$

then the cost is:

$w_0 ; & ; w_1 ; & ; \cdots ; & ; w_k$

A walk is not restricted to simple paths. We are allowed to revisit vertices and edges any number of times. This completely changes the nature of the problem.

The graph can contain disconnected components, cycles, duplicate edges, and edges with weight 0.

The constraints are large:

  • n <= 10^5
  • edges.length <= 10^5
  • query.length <= 10^5

This immediately tells us that we cannot run a graph traversal independently for every query. Any algorithm worse than roughly O((n + m + q) log n) will likely time out.

The most important observation is that the bitwise AND operation is monotonic. Every time we AND with another edge weight, bits can only turn from 1 to 0, never from 0 to 1.

Since walks may revisit edges, if two nodes belong to the same connected component, we are free to traverse additional edges before reaching the destination. That means we can intentionally include edges whose weights clear more bits and reduce the final AND result.

This leads to the core insight:

For any connected component, the minimum possible walk cost between any two nodes in that component equals the bitwise AND of all edge weights in the component.

Important edge cases include:

  • Nodes belonging to different connected components, answer is -1
  • Components containing an edge with weight 0, every query inside that component becomes 0
  • Multiple edges between the same nodes
  • Sparse graphs with isolated nodes
  • Queries where the optimal walk intentionally revisits edges to reduce the AND value The problem gives us an undirected weighted graph with n nodes and a list of weighted edges. For each query [s, t], we must determine the minimum possible cost of any walk from node s to node t.

The key detail is the definition of the walk cost. Instead of summing weights, the cost is the bitwise AND of all edge weights encountered during the walk. If a walk traverses edges with weights:

$$w_1, w_2, w_3, \dots$$

then the cost is:

$$w_1 & w_2 & w_3 & \dots$$

A walk is not restricted to simple paths. We are allowed to revisit nodes and edges any number of times. This changes the problem dramatically because it means we can intentionally traverse extra edges if doing so reduces the final bitwise AND value.

The graph can contain up to 10^5 nodes, 10^5 edges, and 10^5 queries. These constraints immediately rule out expensive per-query graph traversals such as BFS or DFS from scratch. Any solution that processes each query independently in linear time would be too slow.

The most important observation is that bitwise AND only decreases or stays the same when additional numbers are included. Once a bit becomes 0, it can never become 1 again. Because walks may revisit edges arbitrarily, if two nodes belong to the same connected component, we can potentially traverse every edge in that component before reaching the destination.

This means the minimum possible walk cost between any two connected nodes is simply the bitwise AND of all edge weights in their connected component.

Several edge cases are important:

  • If two nodes are disconnected, the answer is -1.
  • If a connected component contains an edge weight 0, then every query within that component has minimum cost 0.
  • Components with only one edge still work naturally because the AND of a single value is itself.
  • Cycles matter because they allow us to intentionally include more edges in the walk to reduce the AND value.

Approaches

Brute Force Approach

A naive solution would attempt to compute the minimum AND value for every query independently.

One possible brute force method is to perform a modified BFS or Dijkstra-like traversal where the state stores the current AND value accumulated so far. From a node with current value x, traversing an edge of weight w produces:

$x ; & ; w$

Because AND values decrease monotonically, we could attempt to explore all reachable AND states.

This approach is correct because it explicitly explores all possible walks and tracks the best achievable AND value.

However, it is far too slow.

The number of distinct AND states can become very large, and performing graph traversal for each query separately would lead to time complexity close to:

$$O(q \cdot (n + m))$$

With all values near 10^5, this is completely infeasible.

Optimal Approach

The crucial insight comes from understanding how walks behave under bitwise AND.

Suppose two nodes belong to the same connected component. Since walks may revisit edges and vertices, we can traverse any edge in the component as many times as we want before reaching the destination.

Because bitwise AND only removes bits, including more edges can only decrease or preserve the result.

Therefore, the minimum achievable cost between any two nodes in a connected component is simply the AND of all edge weights in that component.

So the problem becomes: A brute-force solution would try to compute the minimum possible AND value for each query independently. One possible interpretation is to perform a graph search where the state includes both the current node and the accumulated AND value so far.

For every traversal step, we update:

$$new_cost = current_cost & edge_weight$$

We could use BFS or Dijkstra-like traversal over states.

This approach is correct because it explicitly explores all possible walks and their resulting AND values. However, it is far too slow for the problem constraints. Since there may be many distinct AND states per node, the search space can become extremely large. Running such a traversal for up to 10^5 queries is infeasible.

Optimal Approach

The crucial insight comes from the fact that walks may revisit edges and vertices.

Suppose nodes u and v are in the same connected component. Because the graph is undirected and walks may repeat edges, we can:

  1. Travel from u to any edge in the component
  2. Traverse that edge
  3. Continue exploring other edges
  4. Eventually reach v

Therefore, we are free to include any edge in the connected component in our walk.

Since bitwise AND only decreases when more edges are included, the minimum possible cost is achieved by AND-ing all edge weights in the connected component.

This transforms the problem into:

  1. Find connected components
  2. Compute the AND of all edge weights inside each component
  3. For each query:
  • If nodes are disconnected, return -1
  • Otherwise return the component AND value

Union-Find, also called Disjoint Set Union or DSU, is perfect for this.

  • If nodes belong to different components, answer -1
  • Otherwise, answer the component AND value

A Union-Find data structure, also called Disjoint Set Union (DSU), is ideal for efficiently maintaining connected components.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(q × (n + m)) or worse O(n + m) Explores walks for every query independently
Optimal O((n + m + q) × α(n)) O(n) Uses connected components and component-wide AND values

Here, α(n) is the inverse Ackermann function, which is effectively constant in practice.

Algorithm Walkthrough

Step 1: Initialize Union-Find

Create a DSU structure where every node initially belongs to its own component.

We maintain:

  • parent[i], the representative parent of node i
  • rank or size for union optimization

This allows us to efficiently determine whether two nodes belong to the same connected component.

Step 2: Union All Edges

For every edge [u, v, w], union nodes u and v.

After processing all edges, every connected component in the graph has a unique representative root.

We only care about connectivity here, not weights yet.

Step 3: Compute Component AND Values

Now we compute the AND value for every connected component.

We create a map:

component_and[root]

Initially, a component's AND value is undefined.

For every edge [u, v, w]:

  1. Find the component root of u
  2. If this is the first edge seen for that component:
  • initialize component AND to w
  1. Otherwise:
  • update using bitwise AND

Mathematically:

$component_and[root] = component_and[root] ; & ; w$

At the end, each component stores the AND of all edge weights inside that component.

Step 4: Process Queries

For every query [s, t]:

  1. Find roots of s and t
  2. If roots differ:
  • return -1
  1. Otherwise:
  • return the AND value for that component

Each query becomes nearly constant time.

Why it works

The correctness relies on one critical property.

If two nodes are connected, a walk may traverse arbitrary edges inside the connected component before reaching the destination.

Since bitwise AND is monotonic decreasing, traversing additional edges can only reduce or preserve the final result.

Therefore, the minimum possible walk cost is achieved by including every edge whose bits help reduce the AND value.

Thus, the optimal answer for a connected component equals the AND of all edge weights in that component. | Brute Force | O(Q × (V + E) × states) | O(V × states) | Explores many possible AND states per query | | Optimal | O(E α(N) + Q α(N)) | O(N) | Uses Union-Find and component-wide AND aggregation |

Here, α(N) is the inverse Ackermann function, which is effectively constant in practice.

Algorithm Walkthrough

Step 1: Build Connected Components Using Union-Find

We initialize a Union-Find structure where each node starts in its own component.

For every edge [u, v, w], we union u and v. After processing all edges, every connected component in the graph is represented by a single root node.

Union-Find is chosen because it supports nearly constant-time merging and lookup operations.

Step 2: Compute the AND Value for Each Component

After components are formed, we need the bitwise AND of all edge weights inside each component.

We iterate through every edge again:

  1. Find the root component of the edge
  2. If this is the first edge for that component, initialize the component value with w
  3. Otherwise:

$$component_and[root] &= w$$

At the end, each component stores the AND of all edge weights belonging to it.

Step 3: Process Queries

For each query [s, t]:

  1. Find the roots of s and t
  2. If the roots differ, the nodes are disconnected, so return -1
  3. Otherwise, return the AND value stored for that component

Step 4: Return the Answers

Collect all query results into an array and return it.

Why it works

The correctness relies on a key property of walks in undirected graphs. Since vertices and edges may be revisited arbitrarily, any edge in the connected component can be incorporated into a walk between two connected nodes.

Bitwise AND is monotonic decreasing:

$$a & b \le a$$

Including more edges can only decrease or preserve the result. Therefore, the minimum achievable value is obtained by AND-ing all edges in the component.

Because every connected node pair can traverse all component edges, every query inside the same component shares the same minimum possible cost.

Python Solution

from typing import List

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
from collections import defaultdict

class Solution:
    def minimumCost(
        self,
        n: int,
        edges: List[List[int]],
        query: List[List[int]]
    ) -> List[int]:

        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> None:
            root_x = find(x)
            root_y = find(y)

            if root_x == root_y:
                return

            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 1

        # Build connected components
        for u, v, _ in edges:
            union(u, v)

        # Compute AND value for each component
        component_and = {}

        for u, v, w in edges:
            root = find(u)

            if root not in component_and:
                component_and[root] = w
            else:
                component_and[root] &= w

        # Answer queries
        answer = []

        for s, t in query:
            root_s = find(s)
            root_t = find(t)

            if root_s != root_t:
                answer.append(-1)
            else:
                answer.append(component_and[root_s])

        return answer

The implementation begins with a standard Union-Find data structure using path compression and union by rank. These optimizations ensure that connectivity operations remain nearly constant time.

The first loop unions all endpoints of edges, constructing connected components.

The second loop computes the AND value for every component. Since all nodes in a connected component share the same root, we can use the root as the dictionary key.

Finally, each query checks whether the two nodes share the same root. If not, no walk exists and the answer is -1. Otherwise, we return the precomputed component AND value. The implementation starts by constructing a standard Union-Find structure using path compression and union by rank. These optimizations ensure nearly constant-time operations even for very large inputs.

The first loop unions all connected vertices. After this phase, every connected component has a representative root.

The second loop computes the AND value for each component. Since every edge belongs entirely within one connected component, we can use the component root as the key. The first edge initializes the component AND value, and subsequent edges continue reducing it using bitwise AND.

Finally, each query checks whether the two nodes belong to the same component. If they do not, the graph contains no walk between them, so the answer is -1. Otherwise, the precomputed component AND value is returned immediately.

Go Solution

package main

func minimumCost(n int, edges [][]int, query [][]int) []int {
	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	var find func(int) int

	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(x, y int) {
		rootX := find(x)
		rootY := find(y)

		if rootX == rootY {
			return
		}

		if rank[rootX] < rank[rootY] {
			parent[rootX] = rootY
		} else if rank[rootX] > rank[rootY] {
			parent[rootY] = rootX
		} else {
			parent[rootY] = rootX
			rank[rootX]++
		}
	}

	// Build connected components
	for _, edge := range edges {
		union(edge[0], edge[1])
	}

	// Compute component AND values
		u, v := edge[0], edge[1]
		union(u, v)
	}

	// Compute AND value for each component
	componentAnd := make(map[int]int)

	for _, edge := range edges {
		u, w := edge[0], edge[2]
		root := find(u)

		if val, exists := componentAnd[root]; exists {
			componentAnd[root] = val & w
		} else {
			componentAnd[root] = w
		}
	}

	// Answer queries
	answer := make([]int, 0, len(query))
	// Process queries
	result := make([]int, 0, len(query))

	for _, q := range query {
		s, t := q[0], q[1]

		rootS := find(s)
		rootT := find(t)

		if rootS != rootT {
			answer = append(answer, -1)
		} else {
			answer = append(answer, componentAnd[rootS])
		}
	}

	return answer
}

The Go implementation mirrors the Python solution closely. Maps are used for storing component AND values. Slices replace Python lists, and closures are used for the find and union functions.

Since edge weights are at most 10^5, standard Go int values are completely safe. result = append(result, -1) } else { result = append(result, componentAnd[rootS]) } }

return result

}


The Go implementation closely mirrors the Python solution. The primary difference is explicit slice management and the use of closures for `find` and `union`.

Go maps require checking whether a key exists before updating, which is handled using:

```go
val, exists := componentAnd[root]

Integer overflow is not a concern because edge weights are bounded by 10^5, well within Go's int range.

Worked Examples

Example 1

Input:

n = 5
edges = [[0,1,7],[1,3,7],[1,2,1]]
query = [[0,3],[3,4]]

Step 1: Build Components

Edge Union Result
(0,1) {0,1}
(1,3) {0,1,3}
(1,2) {0,1,2,3}

Node 4 remains isolated.

Final components:

{0,1,2,3}
{4}

Step 2: Compute Component AND

Start with first edge:

7

AND with second edge:

$7 ; & ; 7 = 7$

AND with third edge:

$7 ; & ; 1 = 1$

Component value becomes:

1

Step 3: Answer Queries

Query Same Component? Answer
[0,3] Yes 1
[3,4] No -1

Step 2: Compute Component AND

Start with empty map.

Edge Component AND
7 7
7 & 7 7
7 & 1 1

Final component AND:

Component AND Value
{0,1,2,3} 1

Step 3: Answer Queries

Query Connected? Answer
(0,3) Yes 1
(3,4) No -1

Final output:

[1, -1]

Example 2

Example 2

Input:

n = 3
edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]]
query = [[1,2]]

Build Component

Step 1: Build Components

All nodes become connected:

{0,1,2}

Compute AND

Start:

7

Then:

$7 ; & ; 15 = 7$

Then:

$7 ; & ; 6 = 6$

Then:

$6 ; & ; 1 = 0$

Final component value:

0

Answer:

Step 2: Compute AND

Operation Result
7 7
7 & 15 7
7 & 6 6
6 & 1 0

Component AND becomes 0.

Step 3: Query

Query Connected? Answer
(1,2) Yes 0

Final output:

[0]

Complexity Analysis

Measure Complexity Explanation
Time O((n + m + q) × α(n)) DSU operations are nearly constant time
Space O(n) Parent arrays, rank arrays, and component map

The algorithm processes each edge a constant number of times and answers each query in nearly constant time. Path compression and union by rank make DSU extremely efficient in practice.

Test Cases

from typing import List

class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        parent = list(range(n))
        rank = [0] * n

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

        def union(x, y):
            rx = find(x)
            ry = find(y)

            if rx == ry:
                return

            if rank[rx] < rank[ry]:
                parent[rx] = ry
            elif rank[rx] > rank[ry]:
                parent[ry] = rx
            else:
                parent[ry] = rx
                rank[rx] += 1

        for u, v, _ in edges:
            union(u, v)

        component_and = {}

        for u, v, w in edges:
            root = find(u)

            if root not in component_and:
                component_and[root] = w
            else:
                component_and[root] &= w

        result = []

        for s, t in query:
            if find(s) != find(t):
                result.append(-1)
            else:
                result.append(component_and[find(s)])

        return result

| Time | O(E α(N) + Q α(N)) | Union-Find operations are nearly constant time |
| Space | O(N) | Parent, rank, and component maps store linear data |

The algorithm processes every edge a constant number of times and every query once. Union-Find with path compression and union by rank gives amortized inverse Ackermann complexity, which is effectively constant for all practical input sizes.

## Test Cases

sol = Solution()

Example 1

assert sol.minimumCost( 5, [[0,1,7],[1,3,7],[1,2,1]], [[0,3],[3,4]] ) == [1, -1] ) == [1, -1] # connected component and disconnected node

Example 2

assert sol.minimumCost( 3, [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], [[1,2]] ) == [0] ) == [0] # repeated traversal reduces AND to zero

Single edge

assert sol.minimumCost( 2, [[0,1,5]], [[0,1]] ) == [5] # AND of one edge is itself

Disconnected graph

assert sol.minimumCost( 4, [[0,1,3],[2,3,5]], [[0,2]] ) == [-1]

Single connected component

assert sol.minimumCost( 3, [[0,1,7],[1,2,3]], [[0,2]] ) == [3]

Component AND becomes zero

assert sol.minimumCost( 3, [[0,1,2],[1,2,1]], [[0,2]] ) == [0]

Multiple queries

assert sol.minimumCost( 6, [[0,1,15],[1,2,7],[3,4,3]], [[0,2],[3,4],[0,5]] ) == [7, 3, -1]

Duplicate edges

assert sol.minimumCost( 2, [[0,1,7],[0,1,3]], [[0,1]] ) == [3]

Large weights

assert sol.minimumCost( 2, [[0,1,100000]], [[0,1]] ) == [100000] [[0,1,3]], [[0,2],[2,3]] ) == [-1, -1] # no paths exist

Zero edge weight

assert sol.minimumCost( 3, [[0,1,7],[1,2,0]], [[0,2]] ) == [0] # AND with zero becomes zero

Multiple components

assert sol.minimumCost( 6, [[0,1,7],[1,2,3],[3,4,12]], [[0,2],[3,4],[0,5]] ) == [3, 12, -1] # independent components

Cycle reducing AND

assert sol.minimumCost( 4, [[0,1,15],[1,2,14],[2,0,8]], [[0,2]] ) == [8] # walk can include all edges in cycle

All edges same weight

assert sol.minimumCost( 4, [[0,1,7],[1,2,7],[2,3,7]], [[0,3]] ) == [7] # AND unchanged

Large AND reduction

assert sol.minimumCost( 3, [[0,1,31],[1,2,14],[0,2,7]], [[0,2]] ) == [6] # 31 & 14 & 7 = 6


## Test Summary

| Test | Why |
| --- | --- |
| Example 1 | Validates standard connected/disconnected behavior |
| Example 2 | Validates repeated traversal reducing AND to zero |
| Disconnected graph | Ensures unreachable queries return `-1` |
| Single component | Verifies normal AND accumulation |
| Component AND zero | Confirms zero propagation |
| Multiple queries | Tests mixed query outcomes |
| Duplicate edges | Ensures repeated edges handled correctly |
| Large weights | Verifies upper constraint handling |

## Edge Cases

One important edge case occurs when the graph is disconnected. A naive implementation might accidentally attempt to compute an AND value even when no path exists. The DSU structure prevents this by explicitly checking whether both nodes belong to the same connected component before answering a query.

Another subtle case occurs when a component contains an edge weight of `0`. Since:

$x \; \& \; 0 = 0$

the entire component AND immediately becomes zero. Any walk can include that edge because revisiting edges is allowed, so every query inside that component must return zero. The implementation naturally handles this through repeated AND accumulation.

Duplicate edges can also cause bugs in some graph algorithms. Here they are completely valid and important. Multiple edges may further reduce the component AND value. Since the algorithm processes every edge independently while computing the component AND, duplicate edges are handled correctly.

A final edge case involves isolated vertices. If a node has no incident edges, it forms a singleton connected component with no valid walk to any other node. Since the problem guarantees `si != ti`, queries involving isolated nodes always return `-1`, which the connectivity check handles automatically.
| Example 1 | Verifies connected and disconnected queries |
| Example 2 | Verifies cycles can reduce AND to zero |
| Single edge | Confirms trivial component behavior |
| Disconnected graph | Ensures unreachable nodes return -1 |
| Zero edge weight | Confirms zero propagation through AND |
| Multiple components | Verifies component independence |
| Cycle reducing AND | Tests revisiting edges in walks |
| All edges same weight | Ensures stable AND behavior |
| Large AND reduction | Validates cumulative bitwise reduction |

## Edge Cases

### Disconnected Nodes

If two query nodes belong to different connected components, no walk exists between them. A naive implementation might accidentally return some default AND value instead of `-1`.

The Union-Find structure prevents this bug cleanly. Before answering a query, the implementation compares component roots. Different roots immediately imply no valid walk.

### Components Containing a Zero Weight Edge

Bitwise AND with zero always produces zero:

$$x \& 0 = 0$$

If even one edge in a component has weight `0`, then every query within that component has minimum cost `0`, because we can include that edge in the walk.

The implementation naturally handles this during component aggregation because repeated AND operations propagate the zero value automatically.

### Cycles and Repeated Traversals

A common mistake is assuming the answer depends only on simple paths. The problem explicitly allows walks, meaning edges and vertices may be revisited.

This is crucial because revisiting edges allows us to include additional weights that further reduce the AND result. The implementation correctly captures this by AND-ing all edges in the connected component rather than trying to optimize over individual paths.