[Java] Clean Union-Find Solution || with detailed comments
This great question utilize the power of Union-Find which enables "constant" time query. The tricks are actually pretty straightforward: \n\n1. sort both querie
This great question utilize the power of **Union-Find** which enables "constant" time query. The tricks are actually pretty straightforward: \n\n1. sort both queries by increasing weight\n2. sort edges by increasing weight\n3. for each query, union all edges whose weight is less than this query\n4. check if two nodes in query belongs to the same group\n\nThis idea is pretty important (yet not unique). We may utilize similar tricks in these problems:\n* [1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/discuss/1192238/xieyun95)\n* [1102. Path With Maximum Minimum Value](https://leetcode.com/problems/path-with-maximum-minimum-value/)\n\n\n\n```\nclass Solution {\n    private int[] parents;\n    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {\n        this.parents = new int[n];\n        for (int i = 0; i < n; i++) parents[i] = i;\n        \n        int m = queries.length;\n        \n        // storing {u, v, weight, original idx} by increasing weight\n        int[][] sortedQueries = new int[m][4];\n        for (int i = 0; i < m; i++) {\n            sortedQueries[i] = new int[]{queries[i][0], queries[i][1], queries[i][2], i};\n        }\n        Arrays.sort(sortedQueries, (a,b) -> a[2] - b[2]);\n        \n        \n        // sort edgeList by increasing weight \n        Arrays.sort(edgeList, (a,b) -> a[2] - b[2]);\n        int idx = 0;\n        \n        boolean[] res = new boolean[m];\n        \n        for (int i = 0; i < m; i++) {\n            int[] q = sortedQueries[i];\n            int w = q[2];\n            \n            // union all edges with weight less than current query\n            while (idx < edgeList.length && edgeList[idx][2] < w) {\n                int[] e = edgeList[idx++];\n                int u = e[0], v = e[1];\n                union(u, v);\n            }\n            \n            int uQuery = q[0], vQuery = q[1], id = q[3];\n            res[id] = (find(uQuery) == find(vQuery));\n        }\n        \n        return res;\n    }\n    \n    private void union(int u, int v) {\n        int uParent = find(u);\n        int vParent = find(v);\n        parents[uParent] = vParent;\n    }\n    \n    private int find(int u) {\n        while (u != parents[u]) {\n            parents[u] = parents[parents[u]];\n            u = parents[u];\n        }\n        return u;\n    }  \n}\n```
['Union Find', 'Java']