Category: union_find
-
LeetCode 399: Evaluate Division
link All equations and valid queries are divisions. So, we can we can model a valid query, as a weighted path between and . We build a graph of variables where the edge has weight . We also get the edge with weight . As we build the adjacency list of the graph, we also…
-
LeetCode 218: The Skyline Problem
link For skyline, building roofs are important. Roofs are intervals at some height. If we jump from the end of a roof, we fall to the next higher roof or we fall to the ground. We can find the skyline points from the groups of heights at different locations — from each group, just take…
-
LeetCode 924: Minimize Malware Spread
link Simulate with BFS For each node in the initial, with one BFS, we can simulate what the spread would have been if we removed that node. We want to find the node which if removed, would cause minimum spread. If there is a tie, we break in favor of smaller node id. Say len(initial)…
-
LeetCode 721: Accounts Merge
link UnionFind We can build an email graph where vertices are the unique emails and an edge between two vertices exists if the emails belong to the same person. We can use UnionFind to keep track of the connected components (cc) of this email graph. In the end, we emit the (sorted) cc’s along with…
-
LeetCode 959: Regions Cut By Slashes
link We need to count the connected components in the undirected grid graph. Since putting “/” in a cell divides the cell into two not-connected regions: [ / ], we shall consider each cell having left and right halves. We treat ” ” like “/”, only difference is for ” ” the two halves of…
-
LeetCode 1971: Find if Path Exists in Graph
There is a path between source and destination if and only if the two vertices belong to the same connected component (cc). With Union-Find, we start with connected components — one per vertex. As we union the two ends of edges, the number of connected components goes down. At the end, we check if source…
-
LeetCode 1970: Last Day Where You Can Still Cross
link The grid can be considered as an undirected graph where land cells are the vertices and an edge exists between two vertices if the land cells are neighbors. DFS In the grid graph, for each day, we can check if there is a path from any of the sources (land cells on first row)…
-
LeetCode 128: Longest Consecutive Sequence
link Union-Find We can consider an undirected graph where the distinct numbers are the vertices and an edge between two distinct vertices u and v exists if u = v-1 or u = v+1. The largest connected component of this number graph will have the longest path having consecutive numbers. Using Union-Find we can determine…
-
LeetCode 947: Most Stones Removed with Same Row or Column
link The relation “shares-row-or-column-with” is an equivalence relation on the set of stones. In other words, there is an undirected graph where stones are the vertices and an edge between two stones exist if they share a row or a column. In this stone graph, we can remove all but one stones from each connected…
-
LeetCode 200: Number of Islands
link The grid can be considered as an undirected graph where cells are the vertices and an edge (u, v) means both cells have “1” in them and they are neighbor of each other. DFS Each island is a connected component (cc) in the grid graph. So, we can count the cc’s in one DFS.…
unreasonably effective 