Skip to main content

Union-Find

Union-Find (UF) becomes one of the popular algorithms in the tech interview nowadays. As indicated by its name, UF contains two parts: union and find. The step of find is to find the root of the group; and the step of union is to unite two groups with different roots.

A common implementation of the find function uses a recursive searching process. The end condition is when the root is that same as the key, or roots[key] == key;

if roots[X] == X, roots[Y] == Y, and we need to connect them, then we just need to set roots[X] = Y. After this operation, all the elements with X as the root previously now points to Y as the root. So the group with root as X and group with root Y are united. (We can set roots[Y] = X as well, but now the connected group root is X).

The roots could becomes very flat in the searching process, so the find process is of almost O(1) time complexity; the union is also of O(1), so the overall speed of UF is quite fast.

One of the conditions for whether use UF is that: find the connected groups. Once notice this condition, then we can generally consider to use the UF method.


Question List


Upper Layer

Comments

Post a Comment

Popular posts from this blog

Dynamic Programming - Easy Level - Question 1

Dynamic Programming - Easy Level - Question 1 Leetcode 1646  Get Maximum in Generated Array You are given an integer n. An array nums of length n + 1 is generated in the following way: nums[0] = 0 nums[1] = 1 nums[2 * i] = nums[i] when 2 <= 2 * i <= n nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n Return the maximum integer in the array nums​​​. Constraints: 0 <= n <= 100 Analysis: This question is quick straightforward: the state and transitional formula are given; the initialization is also given. So we can just ready the code to iterate all the states and find the maximum. See the code below: class Solution { public: int getMaximumGenerated(int n) { int res = 0; if(n<2) return n; vector<int> f(n+1, 0); f[1] = 1; for(int i=2; i<=n; ++i) { if(i&1) f[i] = f[i/2] + f[i/2+1]; else f[i] = f[i/2]; // cout<<i<<" "<<f[i]<<endl; ...
Post a Comment
Read more

Bit Manipulation - Medium Level

 Leetcode 416 Partition Equal Subset Sum Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Constraints: 1 <= nums.length <= 200 1 <= nums[i] <= 100 Analysis: There are different ways to solve this problem, such as dp with a time complexity of O(N^2). Since N is small to this question, so it is Okay to pass OJ. Besides the small N, the value of each element is also very small. So this gives us some chance to use "space to trad off time". The data structure to be used is bitset. For bitset, each bit can be either 0 or 1. The index of that bit can be used as the corresponding sum. When the bit is 1, means there is a sum with the value of its index. When a new number comes, this number needs to be added to all the previous sums, to form new "previous" sums. Thus for each number, we need to go through all the previous sums, the time co...
Post a Comment
Read more