Algorithm in LeetCode —— Union Find
Tips for Union Find:
- Apply the Union Find idea flexibly, and be familiar with the Union Find template. The template includes two implementations: one with path compression + union by rank, and another that tracks the number of elements in each set + the size of the largest set. Each version has its own applicable scenarios. Problems that can use the first Union Find template include: Problem 128, Problem 130, Problem 547, Problem 684, Problem 721, Problem 765, Problem 778, Problem 839, Problem 924, Problem 928, Problem 947, Problem 952, Problem 959, and Problem 990. Problems that can use the second Union Find template include: Problem 803 and Problem 952. In Problem 803, union by rank and set-size accounting are critical for performance; without these optimizations, it will TLE.
- Union Find is a way of thinking. Some problems require applying this idea flexibly rather than mechanically using a template. For example, Problem 399 is a stringUnionFind implemented with the Union Find idea. Here, each node is based on strings and a map, rather than simply being represented by int node IDs.
- For some problems, blindly applying the template will not work. For example, in Problem 685, you cannot use path compression or union by rank, because the problem involves a directed graph and you need to know each node’s predecessor. If paths are compressed, this problem can no longer be solved. This problem does not require path compression or union by rank.
- Flexibly abstract the information given by the problem, assign reasonable IDs to that information, solve the problem with Union Find, and use a map to reduce time complexity, as in Problem 721 and Problem 959.
- For problems involving maps, bricks, or grids, you can create a special node and union() all bricks or grid cells on the boundary into this special node. See Problem 130 and Problem 803.
- Problems that can be solved with Union Find can generally also be solved with DFS or BFS, but the time complexity will usually be higher.
| Title | Solution | Difficulty | Time | Space | Favorite |
|---|---|---|---|---|---|
| 128. Longest Consecutive Sequence | Go | Hard | O(n) | O(n) | ❤️ |
| 130. Surrounded Regions | Go | Medium | O(m*n) | O(m*n) | |
| 200. Number of Islands | Go | Medium | O(m*n) | O(m*n) | |
| 399. Evaluate Division | Go | Medium | O(n) | O(n) | |
| 547. Friend Circles | Go | Medium | O(n^2) | O(n) | |
| 684. Redundant Connection | Go | Medium | O(n) | O(n) | |
| 685. Redundant Connection II | Go | Hard | O(n) | O(n) | |
| 721. Accounts Merge | Go | Medium | O(n) | O(n) | ❤️ |
| 765. Couples Holding Hands | Go | Hard | O(n) | O(n) | ❤️ |
| 778. Swim in Rising Water | Go | Hard | O(n^2) | O(n) | ❤️ |
| 803. Bricks Falling When Hit | Go | Hard | O(n^2) | O(n) | ❤️ |
| 839. Similar String Groups | Go | Hard | O(n^2) | O(n) | |
| 924. Minimize Malware Spread | Go | Hard | O(m*n) | O(n) | |
| 928. Minimize Malware Spread II | Go | Hard | O(m*n) | O(n) | ❤️ |
| 947. Most Stones Removed with Same Row or Column | Go | Medium | O(n) | O(n) | |
| 952. Largest Component Size by Common Factor | Go | Hard | O(n) | O(n) | ❤️ |
| 959. Regions Cut By Slashes | Go | Medium | O(n^2) | O(n^2) | ❤️ |
| 990. Satisfiability of Equality Equations | Go | Medium | O(n) | O(n) |
