3108. Minimum Cost Walk in Weighted Graph LeetCode Solution
In this guide, you will get 3108. Minimum Cost Walk in Weighted Graph LeetCode Solution with the best time and space complexity. The solution to Minimum Cost Walk in Weighted Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Cost Walk in Weighted Graph
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.
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:
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
Complexity Analysis
Time Complexity: O(n\log^* n)
Space Complexity: O(n)
3108. Minimum Cost Walk in Weighted Graph LeetCode Solution in C++
class UnionFind {
public:
// 2^17 - 1 is the minimum number in the form 2^x - 1 > 10^5.
UnionFind(int n) : id(n), rank(n), weight(n, (1 << 17) - 1) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v, int w) {
const int i = find(u);
const int j = find(v);
const int newWeight = weight[i] & weight[j] & w;
weight[i] = newWeight;
weight[j] = newWeight;
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
int getMinCost(int u, int v) {
if (u == v)
return 0;
const int i = find(u);
const int j = find(v);
return i == j ? weight[i] : -1;
}
private:
vector<int> id;
vector<int> rank;
vector<int> weight;
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
};
class Solution {
public:
vector<int> minimumCost(int n, vector<vector<int>>& edges,
vector<vector<int>>& query) {
vector<int> ans;
UnionFind uf(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
const int w = edge[2];
uf.unionByRank(u, v, w);
}
for (const vector<int>& q : query) {
const int u = q[0];
const int v = q[1];
ans.push_back(uf.getMinCost(u, v));
}
return ans;
}
}; /* code provided by PROGIEZ */
3108. Minimum Cost Walk in Weighted Graph LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
weight = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
// 2^17 - 1 is the minimum number in the form 2^x - 1 > 10^5.
Arrays.fill(weight, (1 << 17) - 1);
}
public void unionByRank(int u, int v, int w) {
final int i = find(u);
final int j = find(v);
final int newWeight = weight[i] & weight[j] & w;
weight[i] = newWeight;
weight[j] = newWeight;
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int getMinCost(int u, int v) {
if (u == v)
return 0;
final int i = find(u);
final int j = find(v);
return i == j ? weight[i] : -1;
}
private int[] id;
private int[] rank;
private int[] weight;
private int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}
class Solution {
public int[] minimumCost(int n, int[][] edges, int[][] query) {
int[] ans = new int[query.length];
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
final int w = edge[2];
uf.unionByRank(u, v, w);
}
for (int i = 0; i < query.length; ++i) {
final int u = query[i][0];
final int v = query[i][1];
ans[i] = uf.getMinCost(u, v);
}
return ans;
}
} // code provided by PROGIEZ
3108. Minimum Cost Walk in Weighted Graph LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
# 2^17 - 1 is the minimum number in the form 2^x - 1 > 10^5.
self.weight = [(1 << 17) - 1] * n
def unionByRank(self, u: int, v: int, w: int) -> None:
i = self._find(u)
j = self._find(v)
newWeight = self.weight[i] & self.weight[j] & w
self.weight[i] = newWeight
self.weight[j] = newWeight
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
def getMinCost(self, u: int, v: int) -> int:
if u == v:
return 0
i = self._find(u)
j = self._find(v)
return self.weight[i] if i == j else -1
def _find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self._find(self.id[u])
return self.id[u]
class Solution:
def minimumCost(
self,
n: int,
edges: list[list[int]],
query: list[list[int]],
) -> list[int]:
uf = UnionFind(n)
for u, v, w in edges:
uf.unionByRank(u, v, w)
return [uf.getMinCost(u, v) for u, v in query] # code by PROGIEZ
