✔💯 DAY 394 | Custom Union-Find | 100% 0ms | [PYTHON/JAVA/C++] | EXPLAINED | Approach 💫
Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n\n# Intuition & Approach\n Describe your approach to solving the problem. \n####
# Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n![image.png](https://assets.leetcode.com/users/images/a2267944-10b8-41f2-b624-81a67ccea163_1680148646.205976.png)\n# Intuition & Approach\n<!-- Describe your approach to solving the problem. -->\n##### \u2022\tproblem is to determine if there is a path between two nodes in an undirected graph such that each edge on the path has a distance strictly less than a given limit.\n##### \u2022\tThe input consists of the number of nodes, the edge list, and the queries.\n##### \u2022\tThe edge list is an array of arrays, where each sub-array represents an edge between two nodes and the distance between them.\n##### \u2022\tThe queries are an array of arrays, where each sub-array represents a query with two nodes and a limit.\n##### \u2022\tThe using the union-find algorithm to determine if there is a path between two nodes.\n##### \u2022\tThe union-find algorithm is used to group nodes into connected components.\n##### \u2022\tFirst sorts the edges in the edge list by their distance in ascending order.\n##### \u2022 Then iterates over the sorted edges and performs a union operation on the nodes connected by the edge.\n##### \u2022\tThe union operation updates the parent and rank arrays to group the nodes into connected components.\n##### \u2022\tThen iterates over the queries and checks if the two nodes are connected and if the distance between them is less than the given limit.\n##### \u2022\tThe isConnectedAndWithinLimit method uses the find method to determine if the two nodes are connected and if the distance between them is less than the given limit.\n##### \u2022\tThe find method uses the parent and weight arrays to find the root of the connected component and checks if the weight of the edge is less than the given limit.\n##### \u2022\tThe union method updates the parent, rank, and weight arrays to group the nodes into connected components and store the weight of the edge.\n##### \u2022\tfinally returns a boolean array where each element represents if there is a path between the two nodes in the corresponding query with edges less than the given limit.\n\n\n\n# Code\n```java []\nclass Solution {\n    private int[] parent;\n    private int[] rank;\n    private int[] weight;\n    public boolean[] distanceLimitedPathsExist(int length, int[][] adjList, int[][] queries) {\n        // Initialize parent, rank, and weight arrays\n        parent = new int[length];\n        rank = new int[length];\n        weight = new int[length];\n        for (int i = 0; i < length ; i++) parent[i] = i;\n\n        // Sort edges in the adjacency list by distance\n        Arrays.sort(adjList, Comparator.comparingInt(a -> a[2]));\n        // Group nodes into connected components using union-find algorithm\n        for (int[] edge : adjList) unionByRank(edge[0], edge[1], edge[2]);\n\n        // Initialize answer array\n        boolean[] answer = new boolean[queries.length];\n        // Check if there is a path between two nodes with distance less than the given limit for each query\n        for (int i = 0 ; i < queries.length; i++)\n            answer[i] = isConnectedAndWithinLimit(queries[i][0], queries[i][1], queries[i][2]);\n\n        return answer;\n    }\n\n    // Check if there is a path between two nodes with distance less than the given limit\n    public boolean isConnectedAndWithinLimit(int p, int q, int limit) {\n        return find(p, limit) == find(q, limit);\n    }\n\n    // Find the root of the connected component for a node with distance less than the given limit\n    private int find (int x, int limit) {\n        while (x != parent[x]) {\n            // If the weight of the edge is greater than or equal to the given limit, break out of the loop\n            if (weight[x] >= limit) {\n                break;\n            }\n            x = parent[x];\n        }\n        return x;\n    }\n\n    // Union two nodes into the same connected component with the given limit as the weight of the edge\n    private void unionByRank (int x, int y, int limit) {\n        // Find the root of the connected component for each node\n        int x_ref = find (x, Integer.MAX_VALUE);\n        int y_ref = find (y, Integer.MAX_VALUE);\n        if (x_ref != y_ref) {\n            // If the rank of the root of x is less than the rank of the root of y, make y the parent of x\n            if (rank[x_ref] < rank[y_ref]) {\n                parent[x_ref] = y_ref;\n                weight [x_ref] = limit;;\n            } else {\n                // Otherwise, make x the parent of y\n                parent[y_ref] = x_ref;\n                weight[y_ref] = limit;\n                // If the ranks of the roots are equal, increment the rank of the root of x\n                if (rank[x_ref] == rank[y_ref]) {\n                    rank[x_ref]++;\n                }\n            }\n        }\n    }\n}\n```\n```python []\nclass Solution:\n    def distanceLimitedPathsExist(self, length: int, adjList: List[List[int]], queries: List[List[int]]) -> List[bool]:\n        parent = [i for i in range(length)]\n        rank = [0 for i in range(length)]\n        weight = [0 for i in range(length)]\n\n        adjList.sort(key=lambda x: x[2])\n        for edge in adjList:\n            self.unionByRank(edge[0], edge[1], edge[2], parent, rank, weight)\n\n        answer = []\n        for query in queries:\n            answer.append(self.isConnectedAndWithinLimit(query[0], query[1], query[2], parent, weight))\n\n        return answer\n\n    def isConnectedAndWithinLimit(self, p: int, q: int, limit: int, parent: List[int], weight: List[int]) -> bool:\n        return self.find(p, limit, parent, weight) == self.find(q, limit, parent, weight)\n\n    def find(self, x: int, limit: int, parent: List[int], weight: List[int]) -> int:\n        while x != parent[x]:\n            if weight[x] >= limit:\n                break\n            x = parent[x]\n        return x\n\n    def unionByRank(self, x: int, y: int, limit: int, parent: List[int], rank: List[int], weight: List[int]) -> None:\n        x_ref = self.find(x, float(\'inf\'), parent, weight)\n        y_ref = self.find(y, float(\'inf\'), parent, weight)\n        if x_ref != y_ref:\n            if rank[x_ref] < rank[y_ref]:\n                parent[x_ref] = y_ref\n                weight[x_ref] = limit\n            else:\n                parent[y_ref] = x_ref\n                weight[y_ref] = limit\n                if rank[x_ref] == rank[y_ref]:\n                    rank[x_ref] += 1\n```\n\n```c++ []\nclass Solution {\npublic:\n    vector<bool> distanceLimitedPathsExist(int length, vector<vector<int>>& adjList, vector<vector<int>>& queries) {\n        vector<int> parent(length);\n        vector<int> rank(length);\n        vector<int> weight(length);\n        for (int i = 0; i < length ; i++) parent[i] = i;\n\n        sort(adjList.begin(), adjList.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[2] < b[2];\n        });\n        for (vector<int>& edge : adjList) unionByRank(edge[0], edge[1], edge[2], parent, rank, weight);\n\n        vector<bool> answer;\n        for (vector<int>& query : queries)\n            answer.push_back(isConnectedAndWithinLimit(query[0], query[1], query[2], parent, weight));\n\n        return answer;\n    }\n\n    bool isConnectedAndWithinLimit(int p, int q, int limit, vector<int>& parent, vector<int>& weight) {\n        return find(p, limit, parent, weight) == find(q, limit, parent, weight);\n    }\n\n    int find(int x, int limit, vector<int>& parent, vector<int>& weight) {\n        while (x != parent[x]) {\n            if (weight[x] >= limit) {\n                break;\n            }\n            x = parent[x];\n        }\n        return x;\n    }\n\n    void unionByRank(int x, int y, int limit, vector<int>& parent, vector<int>& rank, vector<int>& weight) {\n        int x_ref = find(x, INT_MAX, parent, weight);\n        int y_ref = find(y, INT_MAX, parent, weight);\n        if (x_ref != y_ref) {\n            if (rank[x_ref] < rank[y_ref]) {\n                parent[x_ref] = y_ref;\n                weight[x_ref] = limit;\n            } else {\n                parent[y_ref] = x_ref;\n                weight[y_ref] = limit;\n                if (rank[x_ref] == rank[y_ref]) {\n                    rank[x_ref]++;\n                }\n            }\n        }\n    }\n};\n```\n```csharp []\npublic class Solution {\n public bool[] DistanceLimitedPathsExist(int length, int[][] adjList, int[][] queries) {\n        int[] parent = Enumerable.Range(0, length).ToArray();\n        int[] rank = new int[length];\n        int[] weight = new int[length];\n\n        Array.Sort(adjList, (a, b) => a[2].CompareTo(b[2]));\n        foreach (int[] edge in adjList) {\n            Union(edge[0], edge[1], edge[2], parent, rank, weight);\n        }\n\n        bool[] answer = new bool[queries.Length];\n        for (int i = 0; i < queries.Length; i++) {\n            answer[i] = IsConnectedAndWithinLimit(queries[i][0], queries[i][1], queries[i][2], parent, weight);\n        }\n\n        return answer;\n    }\n\n    private bool IsConnectedAndWithinLimit(int p, int q, int limit, int[] parent, int[] weight) {\n        return Find(p, limit, parent, weight) == Find(q, limit, parent, weight);\n    }\n\n    private int Find(int x, int limit, int[] parent, int[] weight) {\n        while (x != parent[x]) {\n            if (weight[x] >= limit) {\n                break;\n            }\n            x = parent[x];\n        }\n        return x;\n    }\n\n    private void Union(int x, int y, int limit, int[] parent, int[] rank, int[] weight) {\n        int xRef = Find(x, int.MaxValue, parent, weight);\n        int yRef = Find(y, int.MaxValue, parent, weight);\n        if (xRef == yRef) {\n            return;\n        }\n        if (rank[xRef] < rank[yRef]) {\n            parent[xRef] = yRef;\n            weight[xRef] = limit;\n        } else {\n            parent[yRef] = xRef;\n            weight[yRef] = limit;\n            if (rank[xRef] == rank[yRef]) {\n                rank[xRef]++;\n            }\n        }\n    }\n}\n```\n\n# Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n\n# 2nd  union by size \n\n```java []\nclass Solution {\n    private int[] parent;\n    private int[] size;\n    private int[] weight;\n    public boolean[] distanceLimitedPathsExist(int length, int[][] adjList, int[][] queries) {\n        // Initialize parent, size, and weight arrays\n        parent = new int[length];\n        size = new int[length];\n        weight = new int[length];\n        for (int i = 0; i < length ; i++) {\n            parent[i] = i;\n            size[i] = 1;\n        }\n\n        // Sort edges in the adjacency list by distance\n        Arrays.sort(adjList, Comparator.comparingInt(a -> a[2]));\n        // Group nodes into connected components using union-find algorithm\n        for (int[] edge : adjList) unionBySize(edge[0], edge[1], edge[2]);\n\n        // Initialize answer array\n        boolean[] answer = new boolean[queries.length];\n        // Check if there is a path between two nodes with distance less than the given limit for each query\n        for (int i = 0 ; i < queries.length; i++)\n            answer[i] = isConnectedAndWithinLimit(queries[i][0], queries[i][1], queries[i][2]);\n\n        return answer;\n    }\n\n    // Check if there is a path between two nodes with distance less than the given limit\n    public boolean isConnectedAndWithinLimit(int p, int q, int limit) {\n        return find(p, limit) == find(q, limit);\n    }\n\n    // Find the root of the connected component for a node with distance less than the given limit\n    private int find (int x, int limit) {\n        while (x != parent[x]) {\n            // If the weight of the edge is greater than or equal to the given limit, break out of the loop\n            if (weight[x] >= limit) {\n                break;\n            }\n            x = parent[x];\n        }\n        return x;\n    }\n\n    // Union two nodes into the same connected component with the given limit as the weight of the edge\n    private void unionBySize (int x, int y, int limit) {\n        // Find the root of the connected component for each node\n        int x_ref = find (x, Integer.MAX_VALUE);\n        int y_ref = find (y, Integer.MAX_VALUE);\n        if (x_ref != y_ref) {\n        // If the size of the root of x is less than the size of the root of y, make y the parent of x\n        if (size[x_ref] < size[y_ref]) {\n            parent[x_ref] = y_ref;\n            weight [x_ref] = limit;\n            size[y_ref] += size[x_ref];\n        } else {\n            // Otherwise, make x the parent of y\n            parent[y_ref] = x_ref;\n            weight[y_ref] = limit;\n            size[x_ref] += size[y_ref];\n          }\n        }\n    }\n}\n```\n# Complexity\n- Time complexity:\nSorting the adjacency list takes O(E log E) time, where E is the number of edges in the graph.\nThe union-find algorithm takes O(E \u03B1(V)) time, where \u03B1 is the inverse Ackermann function and V is the number of vertices in the graph. In practice, \u03B1(V) is a very small value, so we can consider the time complexity to be O(E).\nChecking if there is a path between two nodes with distance less than the given limit takes O(log V) time, where V is the number of vertices in the graph.\nWe perform this check for each query, so the total time complexity for all queries is O(Q log V), where Q is the number of queries.\nTherefore, the overall time complexity of the algorithm is O(E log E + Q log V).\n- Space Complexity:\nWe use three arrays of size V to store the parent, rank, and weight of each node in the graph, so the space complexity is O(V).\nWe also use a boolean array of size Q to store the answer for each query, so the space complexity is O(Q).\nTherefore, the overall space complexity of the algorithm is O(V + Q).\n\n\n# dry run \nFor the first: Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]\nOutput: [false,true]\n\n\nWe have 3 nodes and the following edges: (0,1) with weight 2, (1,2) with weight 4, (2,0) with weight 8, and (1,0) with weight 16.\nWe have 2 queries: (0,1) with limit 2 and (0,2) with limit 5.\nWe initialize the parent, rank, and weight arrays to [0, 1, 2] and [0, 0, 0].\nWe sort the edges in the adjacency list by distance: (0,1) with weight 2, (1,2) with weight 4, (2,0) with weight 8, and (1,0) with weight 16.\nWe group the nodes into connected components using the union-find algorithm. First, we union nodes 0 and 1 with weight 2, then we union nodes 1 and 2 with weight 4, and finally we union nodes 2 and 0 with weight 8. The resulting parent array is [0, 0, 0].\nFor the first query (0,1) with limit 2, we check if there is a path between nodes 0 and 1 with distance less than 2. We find the root of node 0 with limit 2, which is 0, and the root of node 1 with limit 2, which is 0. Since the roots are the same, we return true.\nFor the second query (0,2) with limit 5, we check if there is a path between nodes 0 and 2 with distance less than 5. We find the root of node 0 with limit 5, which is 0, and the root of node 2 with limit 5, which is 0. Since the roots are the same, we return true.\nTherefore, the output is [false, true].\n\nFor the second input:\nInput: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]\nOutput: [true,false]\n\nWe have 5 nodes and the following edges: (0,1) with weight 10, (1,2) with weight 5, (2,3) with weight 9, and (3,4) with weight 13.\nWe have 2 queries: (0,4) with limit 14 and (1,4) with limit 13.\nWe initialize the parent, rank, and weight arrays to [0, 1, 2, 3, 4] and [0, 0, 0, 0, 0].\nWe sort the edges in the adjacency list by distance: (1,2) with weight 5, (0,1) with weight 10, (2,3) with weight 9, and (3,4) with weight 13.\nWe group the nodes into connected components using the union-find algorithm. First, we union nodes 1 and 2 with weight 5, then we union nodes 0 and 1 with weight 10, then we union nodes 2 and 3 with weight 9, and finally we union nodes 3 and 4 with weight 13. The resulting parent array is [0, 0, 0, 2, 3].\nFor the first query (0,4) with limit 14, we check if there is a path between nodes 0 and 4 with distance less than 14. We find the root of node 0 with limit 14, which is 0, and the root of node 4 with limit 14, which is 3. Since the roots are not the same, we return false.\nFor the second query (1,4) with limit 13, we check if there is a path between nodes 1 and 4 with distance less than 13. We find the root of node 1 with limit 13, which is 0, and the root of node 4 with limit 13, which is 3. Since the roots are the same, we return true.\nTherefore, the output is [true, false].\n\n\n# FAQ \n\n# Why we want to merge the smaller tree into the larger tree?\n\nIn the Union-Find algorithm, the rank array is used to keep of the depth of each node in the tree. When performing the union operation, we want to merge the smaller tree into the larger tree to keep the depth of the tree as small as possible. This helps to improve the performance of the  find operation, which is used to determine the root of the tree.\n\nIf we always merge the smaller tree into the larger tree, we can ensure that the depth of the tree does not increase significantly. This is because the depth of the tree is proportional to the logarithm of the number of nodes in the tree. By keeping the depth of the tree small, we can ensure that the find operation runs in O(log n) time, where n is the number of nodes in the tree.\n\nThe rank array is used to keep track of the depth of each node in the tree. When we merge two trees, we compare the  rank of the root nodes of the two trees. If the rank of the root node of the first tree is less than the rank of the root node of the second tree, we make the root node of the first tree a child of the root node of the second tree. Otherwise, we make the root node of the second tree a child of the root node of the first tree. If the rank of the root nodes is the same, we arbitrarily choose one of the root nodes to be the parent and increment its rank by one.\n\nBy always merging the smaller tree into the larger tree, we can ensure that the depth of the tree does not increase significantly, which helps to improve the performance of the find operation.\n\n# How Path Compression will work in the Union-Find.\n\nPath is a technique used in the Union-Find algorithm to improve the performance the find operation The find operation is used to determine the root of the tree that a node belongs to. In the basic implementation of the Union-Find algorithm, the find operation traverses the tree from the node to the root to determine the root of the tree. This can take O(log n) time in the worst case, where n is the number of nodes in the tree.\n\nPath compression is a technique that can be used to reduce the depth of the tree during the find operation. When we perform the find operation on a node, we traverse the tree from the node to the root to determine the root of the tree. During this traversal, we can update the parent of each node along the path to the root to be the root itself. This can be done recursively or iteratively.\n\nBy updating the parent of each node along the path to the root to be the root itself, we can reduce the depth of the tree. This can help to improve the performance of the find operation, as subsequent find operations on the same node or its descendants will take less time.\n\n![BREUSELEE.webp](https://assets.leetcode.com/users/images/062630f0-ef80-4e74-abdb-302827b99235_1680054012.5054147.webp)\n![image.png](https://assets.leetcode.com/users/images/303fa18d-281d-49f0-87ef-1a018fc9a488_1681355186.0923774.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\nhttps://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/solutions/3465024/day-394-union-find-100-0ms-python-java-c-explained-approach/\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A
['Python', 'C++', 'Java', 'Python3', 'C#']