✔️ Easy | Union Find | Python | C++ | Java | JS | C# | Go | Kotlin | Swift | Rust
SUPPORT BY UPVOTING THE POST ⬆️IntuitionThe problem asks us to find the minimum cost walk between nodes for multiple queries, where cost is defined as the bitwi
# SUPPORT BY UPVOTING THE POST ⬆️

# Intuition
The problem asks us to find the minimum cost walk between nodes for multiple queries, where cost is defined as the bitwise AND of all edge weights in the walk. The key insight is that **for any connected component, the minimum cost between any two nodes will be the bitwise AND of all edges that might be included in any possible walk.**

# Approach
We use a modified `Union-Find` data structure that not only tracks connectivity between nodes but also maintains the minimum possible bitwise AND value for each connected component.
1. Initialize each node as its own component with an AND value of -1 (all bits set to 1 in binary).
2. Process each edge by:
    - Finding the root nodes of the components containing the edge's endpoints
    - Updating the target component's AND value with the edge weight
    - If the endpoints are in different components, merge them and combine their AND values
3. For each query (s, t):
    - If s and t are the same node, return 0
    - If s and t are not in the same component, return -1
    - Otherwise, return the AND value of their component

The beauty of this approach is that as we build the graph, we simultaneously calculate the minimum possible AND value for any potential walk between nodes in the same component.

# Complexity
- Time complexity: `O(N + E + Q)`, where `E` is the number of edges and `Q` is the number of queries
    - Union-Find operations with path compression have nearly constant amortized time
    - We process each edge once and each query once

- Space complexity: `O(N)` for the parent array and the minimum path cost array

# Code
```python3 []
class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        parent = list(range(n))
        
        min_path_cost = [-1] * n
        
        def find_root(node: int) -> int:
            if parent[node] != node:
                parent[node] = find_root(parent[node])
            return parent[node]
        
        for source, target, weight in edges:
            source_root = find_root(source)
            target_root = find_root(target)
            
            min_path_cost[target_root] &= weight
            
            if source_root != target_root:
                min_path_cost[target_root] &= min_path_cost[source_root]
                parent[source_root] = target_root
        
        result = []
        for start, end in query:
            if start == end:
                result.append(0)
            elif find_root(start) != find_root(end):
                result.append(-1)
            else:
                result.append(min_path_cost[find_root(start)])
                
        return result
```
```cpp []
class Solution {
public:
    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        vector<int> parent(n), min_path_cost(n, -1);
        iota(parent.begin(), parent.end(), 0);

        function<int(int)> find_root = [&](int node) {
            if (parent[node] != node) {
                parent[node] = find_root(parent[node]);
            }
            return parent[node];
        };

        for (auto& edge : edges) {
            int source = edge[0], target = edge[1], weight = edge[2];
            int source_root = find_root(source);
            int target_root = find_root(target);

            min_path_cost[target_root] &= weight;

            if (source_root != target_root) {
                min_path_cost[target_root] &= min_path_cost[source_root];
                parent[source_root] = target_root;
            }
        }

        vector<int> result;
        for (auto& q : query) {
            int start = q[0], end = q[1];
            if (start == end) {
                result.push_back(0);
            } else if (find_root(start) != find_root(end)) {
                result.push_back(-1);
            } else {
                result.push_back(min_path_cost[find_root(start)]);
            }
        }
        return result;
    }
};
```
```java []
class Solution {
    private int findRoot(int[] parent, int node) {
        if (parent[node] != node) {
            parent[node] = findRoot(parent, parent[node]);
        }
        return parent[node];
    }

    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        int[] parent = new int[n];
        int[] minPathCost = new int[n];
        Arrays.fill(minPathCost, -1);

        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        for (int[] edge : edges) {
            int source = edge[0], target = edge[1], weight = edge[2];
            int sourceRoot = findRoot(parent, source);
            int targetRoot = findRoot(parent, target);

            minPathCost[targetRoot] &= weight;

            if (sourceRoot != targetRoot) {
                minPathCost[targetRoot] &= minPathCost[sourceRoot];
                parent[sourceRoot] = targetRoot;
            }
        }

        int[] result = new int[query.length];
        for (int i = 0; i < query.length; i++) {
            int start = query[i][0], end = query[i][1];
            if (start == end) {
                result[i] = 0;
            } else if (findRoot(parent, start) != findRoot(parent, end)) {
                result[i] = -1;
            } else {
                result[i] = minPathCost[findRoot(parent, start)];
            }
        }
        return result;
    }
}
```
```javascript []
var minimumCost = function(n, edges, query) {
    let parent = Array.from({ length: n }, (_, i) => i);
    let minPathCost = Array(n).fill(-1);

    const findRoot = (node) => {
        if (parent[node] !== node) {
            parent[node] = findRoot(parent[node]); // Path compression
        }
        return parent[node];
    };

    for (let [source, target, weight] of edges) {
        let sourceRoot = findRoot(source);
        let targetRoot = findRoot(target);

        minPathCost[targetRoot] &= weight;

        if (sourceRoot !== targetRoot) {
            minPathCost[targetRoot] &= minPathCost[sourceRoot];
            parent[sourceRoot] = targetRoot;
        }
    }

    return query.map(([start, end]) => {
        if (start === end) return 0;
        if (findRoot(start) !== findRoot(end)) return -1;
        return minPathCost[findRoot(start)];
    });
};
```
```csharp []
public class Solution {
    public int[] MinimumCost(int n, int[][] edges, int[][] query) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        int[] minPathCost = new int[n];
        Array.Fill(minPathCost, -1);

        int FindRoot(int node) {
            if (parent[node] != node) {
                parent[node] = FindRoot(parent[node]);
            }
            return parent[node];
        }

        foreach (var edge in edges) {
            int source = edge[0], target = edge[1], weight = edge[2];
            int sourceRoot = FindRoot(source);
            int targetRoot = FindRoot(target);

            minPathCost[targetRoot] &= weight;

            if (sourceRoot != targetRoot) {
                minPathCost[targetRoot] &= minPathCost[sourceRoot];
                parent[sourceRoot] = targetRoot;
            }
        }

        int[] result = new int[query.Length];

        for (int i = 0; i < query.Length; i++) {
            int start = query[i][0], end = query[i][1];

            if (start == end) result[i] = 0;
            else if (FindRoot(start) != FindRoot(end)) result[i] = -1;
            else result[i] = minPathCost[FindRoot(start)];
        }

        return result;
    }
}
```
```go []
func findRoot(parent []int, node int) int {
	if parent[node] != node {
		parent[node] = findRoot(parent, parent[node]) // Path compression
	}
	return parent[node]
}

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

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

	for _, edge := range edges {
		source, target, weight := edge[0], edge[1], edge[2]
		sourceRoot := findRoot(parent, source)
		targetRoot := findRoot(parent, target)

		minPathCost[targetRoot] &= weight

		if sourceRoot != targetRoot {
			minPathCost[targetRoot] &= minPathCost[sourceRoot]
			parent[sourceRoot] = targetRoot
		}
	}

	result := make([]int, len(query))
	for i, q := range query {
		start, end := q[0], q[1]
		if start == end {
			result[i] = 0
		} else if findRoot(parent, start) != findRoot(parent, end) {
			result[i] = -1
		} else {
			result[i] = minPathCost[findRoot(parent, start)]
		}
	}

	return result
}
```
```kotlin []
class Solution {
    private fun findRoot(parent: IntArray, node: Int): Int {
        if (parent[node] != node) {
            parent[node] = findRoot(parent, parent[node]) // Path compression
        }
        return parent[node]
    }

    fun minimumCost(n: Int, edges: Array<IntArray>, query: Array<IntArray>): IntArray {
        val parent = IntArray(n) { it }
        val minPathCost = IntArray(n) { -1 }

        for ((source, target, weight) in edges) {
            val sourceRoot = findRoot(parent, source)
            val targetRoot = findRoot(parent, target)

            minPathCost[targetRoot] = minPathCost[targetRoot] and weight

            if (sourceRoot != targetRoot) {
                minPathCost[targetRoot] = minPathCost[targetRoot] and minPathCost[sourceRoot]
                parent[sourceRoot] = targetRoot
            }
        }

        return query.map { (start, end) ->
            when {
                start == end -> 0
                findRoot(parent, start) != findRoot(parent, end) -> -1
                else -> minPathCost[findRoot(parent, start)]
            }
        }.toIntArray()
    }
}
```
```swift []
class Solution {
    private func findRoot(_ parent: inout [Int], _ node: Int) -> Int {
        if parent[node] != node {
            parent[node] = findRoot(&parent, parent[node]) // Path compression
        }
        return parent[node]
    }

    func minimumCost(_ n: Int, _ edges: [[Int]], _ query: [[Int]]) -> [Int] {
        var parent = Array(0..<n)
        var minPathCost = Array(repeating: -1, count: n)

        for edge in edges {
            let source = edge[0], target = edge[1], weight = edge[2]
            let sourceRoot = findRoot(&parent, source)
            let targetRoot = findRoot(&parent, target)

            minPathCost[targetRoot] &= weight

            if sourceRoot != targetRoot {
                minPathCost[targetRoot] &= minPathCost[sourceRoot]
                parent[sourceRoot] = targetRoot
            }
        }

        return query.map { q in
            let start = q[0], end = q[1]
            if start == end {
                return 0
            } else if findRoot(&parent, start) != findRoot(&parent, end) {
                return -1
            } else {
                return minPathCost[findRoot(&parent, start)]
            }
        }
    }
}
```
```rust []
impl Solution {
    pub fn minimum_cost(n: i32, edges: Vec<Vec<i32>>, query: Vec<Vec<i32>>) -> Vec<i32> {
        let mut parent: Vec<i32> = (0..n).collect();
        let mut min_path_cost: Vec<i32> = vec![-1; n as usize];

        fn find_root(parent: &mut Vec<i32>, node: i32) -> i32 {
            if parent[node as usize] != node {
                parent[node as usize] = find_root(parent, parent[node as usize]);
            }
            parent[node as usize]
        }

        for edge in edges.iter() {
            let source = edge[0];
            let target = edge[1];
            let weight = edge[2];

            let source_root = find_root(&mut parent, source);
            let target_root = find_root(&mut parent, target);

            min_path_cost[target_root as usize] &= weight;

            if source_root != target_root {
                min_path_cost[target_root as usize] &= min_path_cost[source_root as usize];
                parent[source_root as usize] = target_root;
            }
        }

        let mut result = Vec::new();
        for q in query.iter() {
            let start = q[0];
            let end = q[1];

            if start == end {
                result.push(0);
            } else if find_root(&mut parent, start) != find_root(&mut parent, end) {
                result.push(-1);
            } else {
                result.push(min_path_cost[find_root(&mut parent, start) as usize]);
            }
        }

        result
    }
}
```

---

![upvote.png](https://assets.leetcode.com/users/images/9baabf31-0e0b-40f6-9a91-242973b6f84d_1742431767.4036734.png)

['Union Find', 'Swift', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'Kotlin', 'JavaScript', 'C#']