[LeetCode][399. Evaluate Division] 4 Approaches: BFS, DFS, Floyd, Union Find

By Long Luo

This article is the solution 4 Approaches: BFS, DFS, Floyd, Union Find of Problem 399. Evaluate Division.

Here shows 4 Approaches to slove this problem: BFS, DFS, Floyd, Union Find.

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int len = equations.size();
Map<String, Integer> varMap = new HashMap<>();
int varCnt = 0;
for (int i = 0; i < len; i++) {
if (!varMap.containsKey(equations.get(i).get(0))) {
varMap.put(equations.get(i).get(0), varCnt++);
}
if (!varMap.containsKey(equations.get(i).get(1))) {
varMap.put(equations.get(i).get(1), varCnt++);
}
}

List<Pair>[] edges = new List[varCnt];
for (int i = 0; i < varCnt; i++) {
edges[i] = new ArrayList<>();
}

for (int i = 0; i < len; i++) {
int va = varMap.get(equations.get(i).get(0));
int vb = varMap.get(equations.get(i).get(1));
edges[va].add(new Pair(vb, values[i]));
edges[vb].add(new Pair(va, 1.0 / values[i]));
}

int queriesCnt = queries.size();
double[] ans = new double[queriesCnt];
for (int i = 0; i < queriesCnt; i++) {
List<String> query = queries.get(i);
double result = -1.0;
if (varMap.containsKey(query.get(0)) && varMap.containsKey(query.get(1))) {
int idxA = varMap.get(query.get(0));
int idxB = varMap.get(query.get(1));
if (idxA == idxB) {
result = 1.0;
} else {
Queue<Integer> points = new LinkedList<>();
points.offer(idxA);
double[] ratios = new double[varCnt];
Arrays.fill(ratios, -1.0);
ratios[idxA] = 1.0;
while (!points.isEmpty() && ratios[idxB] < 0) {
int cur = points.poll();
for (Pair pair : edges[cur]) {
int y = pair.index;
double value = pair.value;
if (ratios[y] < 0) {
ratios[y] = ratios[cur] * value;
points.offer(y);
}
}
}

result = ratios[idxB];
}
}

ans[i] = result;
}

return ans;
}

class Pair {
int index;
double value;

public Pair(int index, double value) {
this.index = index;
this.value = value;
}
}
}

Analysis

  • Time Complexity: O(n^2logn)
  • Space Complexity: O(n^2)

DFS

1

Analysis

  • Time Complexity: O(klogn)
  • Space Complexity: O(n)

Floyd

1

Analysis

  • Time Complexity: O(nlog(r-l)
  • Space Complexity: O(1)

Union Find

1

Analysis

  • Time Complexity: O(nlog(r-l)
  • Space Complexity: O(1)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗