🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART
Intuition
We are given a graph where each edge has a weight, and we need to process queries efficiently.
The goal is to find the minimum path cost between given
![image.png](https://assets.leetcode.com/users/images/fd7b1bbf-a30d-48a8-917f-6c5443ae966a_1742444054.50965.png)

-----


---

## **Intuition**
- We are given a graph where each edge has a weight, and we need to process queries efficiently.
- The goal is to find the **minimum path cost** between given node pairs.
- Since the queries involve checking connectivity and computing the minimum cost over paths, **Disjoint Set Union (DSU) with path compression** is a suitable choice.
- The **bitwise AND** operation is used to determine the **minimum cost along any path**.

---

## **Approach**
1. **Initialize DSU (Disjoint Set Union)**  
   - Create an array `parent[]` where each node is its own parent.
   - Create an array `minPathCost[]` to track the minimum cost in each connected component.

2. **Process the given edges**  
   - Use DSU to **connect** nodes and maintain the **minimum path cost** within components.
   - The minimum cost is updated using **bitwise AND (`&`)**, ensuring that it stores the minimum path cost across all edges in the component.

3. **Process queries**  
   - If `start == end`, return `0` since no cost is required.
   - If `start` and `end` are in **different components**, return `-1` (not connected).
   - Otherwise, return `minPathCost[findRoot(start)]`.

### **Key Observations**
- **DSU with path compression** speeds up **find operations** to almost **O(1)**.
- **Bitwise AND (`&`)** ensures that the minimum path cost is updated efficiently.

---

## **Complexity Analysis**
- **Building DSU (Union-Find) → O(N log N)**
- **Processing queries → O(Q log N)**
- **Overall Complexity:** **O((N + Q) log N)**

---


```dart []
class Solution {
  List<int> parent = [];
  List<int> minPathCost = [];

  int findRoot(int node) {
    while (parent[node] != node) {
      parent[node] = parent[parent[node]]; // Path compression
      node = parent[node];
    }
    return node;
  }

  List<int> minimumCost(int n, List<List<int>> edges, List<List<int>> query) {
    parent = List.generate(n, (index) => index);
    minPathCost = List.filled(n, -1);

    for (var edge in edges) {
      int source = edge[0];
      int target = edge[1];
      int weight = edge[2];

      int sourceRoot = findRoot(source);
      int targetRoot = findRoot(target);

      if (minPathCost[sourceRoot] == -1) minPathCost[sourceRoot] = weight;
      else minPathCost[sourceRoot] &= weight;

      if (minPathCost[targetRoot] == -1) minPathCost[targetRoot] = weight;
      else minPathCost[targetRoot] &= weight;

      if (sourceRoot != targetRoot) {
        // Merge and update minPathCost
        parent[sourceRoot] = targetRoot;
        minPathCost[targetRoot] &= minPathCost[sourceRoot];
      }
    }

    List<int> result = [];
    for (var q in query) {
      int start = q[0];
      int end = q[1];

      if (start == end) {
        result.add(0);
      } else if (findRoot(start) != findRoot(end)) {
        result.add(-1);
      } else {
        result.add(minPathCost[findRoot(start)]);
      }
    }

    return result;
  }
}
```


```java []
import java.util.*;

class Solution {
    int[] parent;
    int[] minPathCost;

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

    public int[] minimumCost(int n, int[][] edges, int[][] queries) {
        parent = new int[n];
        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(source);
            int targetRoot = findRoot(target);

            if (minPathCost[sourceRoot] == -1) minPathCost[sourceRoot] = weight;
            else minPathCost[sourceRoot] &= weight;

            if (minPathCost[targetRoot] == -1) minPathCost[targetRoot] = weight;
            else minPathCost[targetRoot] &= weight;

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

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int start = queries[i][0], end = queries[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;
    }
}
```


```cpp []
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> parent, minPathCost;

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

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        parent.resize(n);
        minPathCost.assign(n, -1);
        for (int i = 0; i < n; i++) parent[i] = i;

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

            if (minPathCost[sourceRoot] == -1) minPathCost[sourceRoot] = weight;
            else minPathCost[sourceRoot] &= weight;

            if (minPathCost[targetRoot] == -1) minPathCost[targetRoot] = weight;
            else minPathCost[targetRoot] &= weight;

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

        vector<int> result;
        for (auto& q : queries) {
            int start = q[0], end = q[1];

            if (start == end) result.push_back(0);
            else if (findRoot(start) != findRoot(end)) result.push_back(-1);
            else result.push_back(minPathCost[findRoot(start)]);
        }

        return result;
    }
};
```


```python []
class Solution:
    def findRoot(self, node, parent):
        if parent[node] != node:
            parent[node] = self.findRoot(parent[node], parent)  # Path compression
        return parent[node]

    def minimumCost(self, n, edges, queries):
        parent = list(range(n))
        minPathCost = [-1] * n

        for source, target, weight in edges:
            sourceRoot = self.findRoot(source, parent)
            targetRoot = self.findRoot(target, parent)

            minPathCost[sourceRoot] = weight if minPathCost[sourceRoot] == -1 else minPathCost[sourceRoot] & weight
            minPathCost[targetRoot] = weight if minPathCost[targetRoot] == -1 else minPathCost[targetRoot] & weight

            if sourceRoot != targetRoot:
                parent[sourceRoot] = targetRoot
                minPathCost[targetRoot] &= minPathCost[sourceRoot]

        result = []
        for start, end in queries:
            if start == end:
                result.append(0)
            elif self.findRoot(start, parent) != self.findRoot(end, parent):
                result.append(-1)
            else:
                result.append(minPathCost[self.findRoot(start, parent)])

        return result
```


``` javascript []
class Solution {
    constructor() {
        this.parent = [];
        this.minPathCost = [];
    }

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

    minimumCost(n, edges, queries) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.minPathCost = new Array(n).fill(-1);

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

            if (this.minPathCost[sourceRoot] === -1) this.minPathCost[sourceRoot] = weight;
            else this.minPathCost[sourceRoot] &= weight;

            if (this.minPathCost[targetRoot] === -1) this.minPathCost[targetRoot] = weight;
            else this.minPathCost[targetRoot] &= weight;

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

        let result = [];
        for (const [start, end] of queries) {
            if (start === end) {
                result.push(0);
            } else if (this.findRoot(start) !== this.findRoot(end)) {
                result.push(-1);
            } else {
                result.push(this.minPathCost[this.findRoot(start)]);
            }
        }

        return result;
    }
}

```

---

## **Final Thoughts**
- **Efficient union-find approach** ensures fast query processing.
- **Bitwise AND (`&`)** is used to maintain the **minimum** path cost.
- **Optimal solution** for large constraints. 🚀



-----

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Bit Manipulation', 'Union Find', 'Graph', 'C', 'Python', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart']