Checking Existence of Edge Length Limited Paths LeetCode solution in Java

1
class Solution {
2
  private int[] parents;
3

4
  public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
5
    this.parents = new int[n];
6
    for (int i = 0; i < n; i++) parents[i] = i;
7

8
    int m = queries.length;
9

10
    // storing {u, v, weight, original idx} by increasing weight
11
    int[][] sortedQueries = new int[m][4];
12
    for (int i = 0; i < m; i++) {
13
      sortedQueries[i] = new int[] {queries[i][0], queries[i][1], queries[i][2], i};
14
    }
15
    Arrays.sort(sortedQueries, (a, b) -> a[2] - b[2]);
16

17
    // sort edgeList by increasing weight
18
    Arrays.sort(edgeList, (a, b) -> a[2] - b[2]);
19
    int idx = 0;
20

21
    boolean[] res = new boolean[m];
22

23
    for (int i = 0; i < m; i++) {
24
      int[] q = sortedQueries[i];
25
      int w = q[2];
26

27
      // union all edges with weight less than current query
28
      while (idx < edgeList.length && edgeList[idx][2] < w) {
29
        int[] e = edgeList[idx++];
30
        int u = e[0], v = e[1];
31
        union(u, v);
32
      }
33

34
      int uQuery = q[0], vQuery = q[1], id = q[3];
35
      res[id] = (find(uQuery) == find(vQuery));
36
    }
37

38
    return res;
39
  }
40

41
  private void union(int u, int v) {
42
    int uParent = find(u);
43
    int vParent = find(v);
44
    parents[uParent] = vParent;
45
  }
46

47
  private int find(int u) {
48
    while (u != parents[u]) {
49
      parents[u] = parents[parents[u]];
50
      u = parents[u];
51
    }
52
    return u;
53
  }
54
}