Union Find | Python / JS Solution
Hello Tenno Leetcoders, \nFor this problem, we have an undirected graph of n nodes defined by edgeList, where edgeList[i] = [ui, vi, disi]. denotes an edge betw
Hello **Tenno Leetcoders**, \nFor this problem, we have an undirected graph of `n` nodes defined by `edgeList`, where `edgeList[i] = [ui, vi, disi]`. denotes an edge between nodes `ui` and `v`i with distance `disi`.\n\nWe are given an `array queries`, where `queries[j] = [pj, qj, limitj]`, we want to determine for each `queries[i]`, whether there is a path between `pj` and `qj` such that each edge on the path has a distance strictly less than `limitj`.\n\n\nWe want to return a `boolean array answer`, where `answer.length == queries.length` and the `jth value` of answer is `true` if there is a `path` for `queries[j]` is `true`, and `false` otherwise.\n\n## Explanation\n\nThis problem want us to determine for each query in `queries` array, we want to know if there exists a path between node `pj` and `qj` in an undirected graph defined by `edgeList` such that each edge on the path has a distance stricly less than `limitj`\n\nSince, we want to determine if there is a path between two nodes such that each edges within the path has a distance strictly less than the given limit denoted as `limitj`\n\nWe can use `Union-find` to help us determine wether there is a path between two nodes that satisfy the given limit condition \n\nA basic usage of `Union-find` will be first, initializing each node as its own seperate component. \n\nAs we proceed each edge, we check whether the connection between two nodes are in the same component. \n\nWe can then determine the same two nodes belonging to the same component have the same root node.\n\nFor this problem though, we can use the same basic usage of`Union-find` with some modifications. We should first merge componenets by considering the weight of each edges. \n\nAs we merge two componenets, we want to choose the smallest edge weight between the parent and child.\n\nTo keep track of each parent node, we want to use an array and another array to keep track of distances betwen each node and its parent and set the  starting distance as `0s`.\n\nWe will iterate our given `edgeList`. For each edge, we will find the parent nodes using `union-find`, comparing the distances between each node and its parent with their weight. If their weight is less than the distance, we can update the parent and the starting distances with the new parents distance.\n\nWe will need to check if there is a path between two nodes. by finding the root of the parent and child nodes using `union-find` again. We can then calculate the distance between each node and its root.\n\nIf their distance is less than the given limit denoted as `limitj` then we return `true` else `false`\n\n\n### Code\n\n**Python**\n```\nclass UnionFind:\n    \n    def __init__(self,n):\n        self.parent = [i for i in range(n)]\n        self.size = [0] * n\n        \n    def find(self, node):\n        if self.parent[node] != node:\n            self.parent[node] = self.find(self.parent[node])\n        \n        return self.parent[node]\n    \n    \n\n    def union(self, node1, node2):\n        root1 = self.find(node1)\n        root2 = self.find(node2)\n        \n        if root1 == root2: return \n        \n        if self.size[root1] > self.size[root2]: self.parent[root2] = root1\n        elif self.size[root1] < self.size[root2]: self.parent[root1] = root2\n        else: \n            self.parent[root1] = root2\n            self.size[root2] += 1\n                \n    def connected(self, node1, node2):\n        return self.find(node1) == self.find(node2)\n    \nclass Solution:               \n    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:\n        uf = UnionFind(n)\n        \n        edgeList.sort(key=lambda x: x[2])\n        \n        queries_sorted = [(limit, i, p, q) for i, (p,q, limit) in enumerate(queries)]\n        \n        queries_sorted.sort()\n        \n        result = [False] * len(queries)\n        \n        edges_index = 0\n        \n        for limit, query_index, p, q in queries_sorted:\n            while edges_index < len(edgeList) and edgeList[edges_index][2] < limit:\n                uf.union(edgeList[edges_index][0], edgeList[edges_index][1])\n                edges_index += 1\n                \n            if uf.connected(p,q):\n                result[query_index] = True\n                \n        return result\n```\n\n**JavaScript**\n\n```\nclass UnionFind{\n    \n    constructor(n){\n        this.parent = Array(n).fill().map((_, i) => i)\n        this.size = Array(n).fill(0)\n    }\n    \n    find(node){\n        if(this.parent[node] !== node){\n            this.parent[node] = this.find(this.parent[node])\n        }\n        return this.parent[node]\n    }    \n    \n    union(node1, node2){\n        let root1 = this.find(node1)\n        let root2 = this.find(node2)\n        \n        if (root1 === root2) return\n        \n        if(this.size[root1] > this.size[root2]) {\n            this.parent[root2] = root1\n        }\n        else if(this.size[root1] < this.size[root2]){\n            this.parent[root1] = root2\n        }\n        else{\n            this.parent[root1] = root2\n            this.size[root2] += 1\n        }\n    }\n    \n    connected(node1, node2){\n        return this.find(node1) === this.find(node2)\n    }\n    \n}\n\nvar distanceLimitedPathsExist = function(n, edgeList, queries) {\n    \n    let uf = new  UnionFind(n)\n    \n    edgeList.sort((a,b) => a[2] - b[2])\n    \n    let queries_sorted = queries.map((q,i) => [q[2], i, q[0], q[1]])\n    queries_sorted.sort((a,b ) => a[0] - b[0])\n    \n    let result = Array(queries_sorted.length).fill(false)\n\n    \n    let edges_index = 0\n    \n    \n    for(let [limit, query_index, p, q] of queries_sorted){\n       \n        while(edges_index < edgeList.length && edgeList[edges_index][2] < limit){\n            \n            uf.union(edgeList[edges_index][0], edgeList[edges_index][1])\n            edges_index += 1\n        }\n        \n        if(uf.connected(p,q)){\n            result[query_index] = true\n        }\n   \n    }\n       \n  return result\n};\n```\n\n***Warframe\'s Darvo wants you to upvote this post  \uD83D\uDE4F\uD83C\uDFFB \u2764\uFE0F\u200D\uD83D\uDD25***\n\n![image](https://assets.leetcode.com/users/images/814f5668-c966-46d7-ba42-e5435c4c1761_1675302761.3081913.gif)
['Union Find', 'Python', 'JavaScript']