Java || 32ms 100% || 2 Sorts and Union-Find, Fastest, Beginner Friendly
--- Algorithm ---\nThe code below has been optimized for speed, which sacrifices some simplicity.  The code uses the following algorithm:\n\n1. Sort the edges i
**--- Algorithm ---**\nThe code below has been optimized for speed, which sacrifices some simplicity.  The code uses the following algorithm:\n\n1. Sort the edges in ascending distance order.\n2. Sort the queries in ascending distance order.\n3. Initialize a union-find for the nodes of the graph.\n4. Initialize boolean array to be returned, to all false.\n5. Initialize iterator for the sorted edges.\n6. Loop through the queries in sorted order.\n7. Add all edges with a distance shorter than the current queries limit distance, using iterator for the sorted edges, and using union-find to add those edges to the graph.\n8. If the two nodes of the query have the same union-find parent, then there must be a valid path between the query\'s two nodes, so set current query\'s entry in the boolean array to true.\n9. Loop back to step #6, until all queries have been processed.\n10. Return boolean array.\n\n**--- Union Find ---**\nIn this leetcode problem, the union-find is used to determine if any two nodes of the graph are connected by some path through the graph.  As the queries are processed in ascending order sorted by their limit distance, we only partially build the graph, using only those edges that have a distance less than the current query\'s limit distance.  Therefore, all edges that have been added to the graph, will always be valid edges for the current query.  Determining if any path exists between the query\'s two nodes is done with a union-find.\n\nThe "**union-find**" is two operations.  The "**find**" operation to find any node\'s "**root**" node in the graph.  And the "**union**" operation to join any two nodes, which in this case is to add an edge between two nodes.  The purpose of the union-find is to collect nodes into groups, where each group has a path or paths connecting all members of the group.  a union-find group is identified by its root node.  Another union-find group with a different root node, will NOT have any graph connections between the two groups.  Union-find groups are connected within the group, but disconnected (or disjoint) from other groups.\n\nA union-find group\'s **root node has no special significance** in this leetcode problem.  The root node has simply been arbitrarily chosen to be the union-find group\'s identifier.  The root node of a group may change when the union operation merges two groups into a single group.\n\nTo implement the union-find data structure, we create an array `parents[]`.  The `parents` array is indexed by a node\'s node number.  The `parents` array contains each node\'s parent node number.  A "**root**" node in the `parents` array is simply any node that is its own parent, or `parents[i]==i` for root nodes.  For non-root nodes, which node is the parent node, has no special significance other than to find the path to that node\'s root node.  The any node\'s parent node number may be modified by the union-find operations, so which node is currently the parent of another has little significance.\n\nTo create the `parents` array, we initialize each node to be its own parent, making each node a root node.  Initially, no edges have been processed, so there are no connections between any nodes, and therefore each node is isolated in its own union-find group, with itself being the root node of its own group.  The nodes will become connected later when performing union operations.  To initialize the `parents` array, use the code:\n```\n        int[] parents = new int[n];\n        for (int i = n - 1; i >= 0; i--)\n            parents[i] = i;\n```\nTo perform the union-find\'s find operation, call the `findRoot()` method.  This method calls itself recursively to find the root of the union-find group.  All nodes in the same union-find group have the same root node, and have edges that create paths between any two nodes in the same union-find group.  The `findParent()` method will also update the nodes it recurses through, so next time they have a shorter path to the root node. The `parents[]` array contains the parent node number for every node.  A node is the root of a union-find group if `parents[i]==i`.\n```\n    private int findRoot(int[] parents, int node) {\n        if (parents[node] == node)  return node;\n        return parents[node] = findRoot(parents, parents[node]);\n    }\n```\nWe use the union-find\'s union operation to add an edge to the graph, using that edge\'s two nodes.  The union operation is very simple.  First we find the root node numbers for the edge\'s two nodes.  If both nodes have the same root node, then some path between the two nodes already exists so nothing to do, because they are already in the same union-find group.  If both nodes have different root nodes, then there was previously no path between the two nodes.  But now this edge will directly connect the two nodes, so we need to merge the two union-find groups by setting the root node of one union-find group, to point to the root node of the other group, thereby demoting one of the root nodes a non-root node.  For the root node that was demoted to a non-root node, any chain of parentage that led to that root node, will now continue that chain to the other root node, which is now the root node of the two groups that have been combined into a single group.  When doing the union operation to merge two groups, it is arbitrary as to which root is demoted to non-root, and which root node becomes the root node for the new combined group.  The union operation is performed with the following code:\n```\n                    int rootU = findRoot(parents, edge[0]);\n                    int rootV = findRoot(parents, edge[1]);\n                    if (rootU != rootV)  parents[rootV] = rootU;\n```\nThis is a very simple implementation of union-find, but this simple implementation is enough for many leetcode problems.  The union-find is also called "disjoint-set data structure", "merge-find set", or "union-find data structure".  In this leetcode problem, the actual graph is NOT stored as edges are added to the graph.  Only the union-find groupings of the graph\'s nodes is needed.\n\n**--- Sorting ---**\nSorting the edges and the queries does NOT modify the `edgeList` and `queries` arrays.  Two sorted arrays are created.  One sorted array for edges, and one sorted array for queries.\n\nTo sort, an array of `long` is created the same length of the array to be sorted.  The distance and original index is written into each `long`.  Then the array of `long` is sorted using `Arrays.sort()`, resulting in edges or queries in increasing distance order.  Each `long` in the sorted array contains the original index back to the `edgeList` or `queries` arrays.  An array of `long` is used for sorting because: 1) sorting an array of primitive types is faster than sorting more complex objects and this code has been optimized for speed, and 2) a `long` is needed to contain the values to be sorted.\n\nEach `long` value in the array to be sorted, is loaded with the distance value and the original index into the `edgeList` or `queries` arrays.  The distance is placed in the more significant digits of the `long` to be able to sort by distance, and the original index is placed in the lowest digits of the `long`.  Then the array is sorted using `Arrays.sort()`.  \n\nThe first code example below has the sorted `long` values storing distance and index inside the `long` in binary bit positions, using SHIFT-LEFT to load the `long` values, and using AND to read the index value from the `long` value.  These `long` values are stored as:\n```\n | Bit 63                                                   Bit 0 |\n+V-------------+------------------------------+-------------------V+\n|   (unused)   |     Bits 20..49 : distance   | Bits 0..19 : index |\n+--------------+------------------------------+--------------------+\n\t\tAssigning value to long:  long = distance << 20 + index\n\t\tReading index from long:  index = long & 0xFFFFF\n\t\t\n```\nThe second code example below has the sorted `long` values storing distance and index inside the `long` in decimal digit positions, using MULTIPLY to load the `long` values, and MODULO to read the index from the `long` value.  Storing the sorted values using binary operators, had runtimes as much as 12% faster as using decimal digit storage.  These `long` values are stored as:\n```\nDecimal digits in 64-bit long:  00_00d_ddd_ddd_ddd_xxx_xxx\n\t\t\t\t\tx = Digits containing index value.\n\t\t\t\t\td = Digits containing distance value.\n\t\t\t\t\t0 = Unused decimal digits.\n\t\tAssigning value to long:  long = distance * 1_000_000 + index\n\t\tReading index from long:  index = long % 1_000_000\n```\n**--- Miscelaneous ---**\nThis code runs as fast as 32ms using binary stored data in the sorted `long` values, and 33ms using decimal stored data in the sorted `long` values, in August 2023.\n\nIf useful, please upvote.\n\n**--- Commented code with binary shift and mask for building and retrieving sorted values (faster) ---**\n\n```\nclass Solution {\n    // These MASK and SHIFT values are used to build sort \n    // arrays for the edges and for the queries.  The arrays \n    // to be sorted contain the higher binary digits, and \n    // the index into the edges or the queries into the \n    // lower binary digits.  After sorting, only the index \n    // in the lower part of the long value is used.\n    static final long MASK = 0xFFFFFL;\n    static final int SHIFT = 20;\n    \n    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, \n                                               int[][] queries) {\n        int eCount = edgeList.length;\n        int qCount = queries.length;\n\n        // Sort the edges by distance.\n        long[] eSort = new long[eCount];\n        for (int i = eCount - 1; i >= 0; i--)\n            eSort[i] = ((long)edgeList[i][2] << SHIFT) + i;\n        Arrays.sort(eSort);\n        \n        // Sort the queries by limit distance.\n        long[] qSort = new long[qCount];\n        for (int i = qCount - 1; i >= 0; i--)\n            qSort[i] = ((long)queries[i][2] << SHIFT) + i;\n        Arrays.sort(qSort);\n        \n        // Build the parents array for the union find.\n        int[] parents = new int[n];\n        for (int i = n - 1; i >= 0; i--)\n            parents[i] = i;\n        \n        boolean[] result = new boolean[qCount];\n        int eSortIdx = 0;\n        int[] e = edgeList[(int)(eSort[0] & MASK)];\n        int eDist = e[2];\n        // Loop through all of the queries, in increasing limit distance \n        // order.\n        for (int qSortIdx = 0; qSortIdx < qCount; qSortIdx++) {\n            int qIdx = (int)(qSort[qSortIdx] & MASK);\n            int[] q = queries[qIdx];\n            int qDist = q[2];\n            // Process all of the unprocessed edges that are within the \n            // current query\'s limit distance.  Because queries are processed \n            // in low to high distance order, and edges are processed in low \n            // to high distance order, we just process edged (i.e. connect \n            // via union-find) until we hit an edge with larger or same \n            // distance as the current query\'s limit distance.\n            if (eSortIdx < eCount) {\n                while (qDist > eDist) {\n                    int rootU = findRoot(parents, e[0]);\n                    int rootV = findRoot(parents, e[1]);\n                    if (rootU != rootV)\n                        parents[rootV] = rootU;\n                    eSortIdx++;\n                    if (eSortIdx >= eCount)  break;\n                    e = edgeList[(int)(eSort[eSortIdx] & MASK)];\n                    eDist = e[2];\n                }\n            }\n            // Use union-find roots to decide if the two query nodes \n            // are connected by some path.\n            if (findRoot(parents, q[0]) == findRoot(parents, q[1])) \n                result[qIdx] = true;\n        }\n        return result;\n    }\n    \n    \n    private int findRoot(int[] parents, int node) {\n        if (parents[node] == node)  return node;\n        return parents[node] = findRoot(parents, parents[node]);\n    }\n}\n```\n**--- Clean Java code with decimal multiply and modulo for building and retrieving sorted values (slower) ---**\n```\nclass Solution {\n    static final long MOD = 1_000_000L;\n    \n    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, \n                                               int[][] queries) {\n        int eCount = edgeList.length;\n        int qCount = queries.length;\n\n        long[] eSort = new long[eCount];\n        for (int i = eCount - 1; i >= 0; i--)\n            eSort[i] = (long)edgeList[i][2] * MOD + i;\n        Arrays.sort(eSort);\n        \n        long[] qSort = new long[qCount];\n        for (int i = qCount - 1; i >= 0; i--)\n            qSort[i] = (long)queries[i][2] * MOD + i;\n        Arrays.sort(qSort);\n        \n        int[] parents = new int[n];\n        for (int i = n - 1; i >= 0; i--)\n            parents[i] = i;\n        \n        boolean[] result = new boolean[qCount];\n        int eSortIdx = 0;\n        int[] e = edgeList[(int)(eSort[0] % MOD)];\n        int eDist = e[2];\n        for (int qSortIdx = 0; qSortIdx < qCount; qSortIdx++) {\n            int qIdx = (int)(qSort[qSortIdx] % MOD);\n            int[] q = queries[qIdx];\n            int qDist = q[2];\n            if (eSortIdx < eCount) {\n                while (qDist > eDist) {\n                    int rootU = findRoot(parents, e[0]);\n                    int rootV = findRoot(parents, e[1]);\n                    if (rootU != rootV)\n                        parents[rootV] = rootU;\n                    eSortIdx++;\n                    if (eSortIdx >= eCount)  break;\n                    e = edgeList[(int)(eSort[eSortIdx] % MOD)];\n                    eDist = e[2];\n                }\n            }\n            if (findRoot(parents, q[0]) == findRoot(parents, q[1])) \n                result[qIdx] = true;\n        }\n        return result;\n    }\n    \n    \n    private int findRoot(int[] parents, int node) {\n        if (parents[node] == node)  return node;\n        return parents[node] = findRoot(parents, parents[node]);\n    }\n}\n```
['Union Find', 'Sorting', 'Java']