Union find
https://leetcode.com/contest/weekly-contest-106/problems/minimize-malware-spread/
Union find solution (1900ms)
928. Minimize Malware Spread II
https://leetcode.com/contest/weekly-contest-107/problems/minimize-malware-spread-ii/
using union found for both
1) without delete any nodes
2) delete one node will avoid how many nodes uninfected: at this step, we know that if we keep the node undeleted, the infected whole area. Collect this whole area information. And delete one node. Redo union find and we can get how many will not be infected after deletion. Then we can get_this_res(to_be_deleted_node)
One trick we can use is an earlier return if we find that the current deletion can not achieve a smaller result than current min_res.
The run time is kind of slow. It is 1900 ms.
naive union find (1900ms)
547. Friend Circles
https://leetcode.com/problems/friend-circles/
class Solution:
def findCircleNum(self, M: List[List[int]]) -> int:
self.uf = {}
def find(x):
#print(x)
self.uf.setdefault(x, x)
if self.uf[x]!=x:
self.uf[x] = find(self.uf[x])
return self.uf[x]
def union(x, y):
self.uf[find(y)] = find(x)
N = len(M)
for i in range(N):
for j in range(i+1, N):
if M[i][j]:
union(i,j)
#print(self.uf)
return len(set(find(i) for i in range(N)))765. Couples Holding Hands
“Think about each couple as a vertex in the graph. So if there are N couples, there are N vertices. Now if in position 2i and 2i +1 there are person from couple u and couple v sitting there, that means that the permutations are going to involve u and v. So we add an edge to connect u and v. The min number of swaps = N — number of connected components. This follows directly from the theory of permutations. Any permutation can be decomposed into a composition of cyclic permutations. If the cyclic permutation involve k elements, we need k -1 swaps. You can think about each swap as reducing the size of the cyclic permutation by 1. So in the end, if the graph has k connected components, we need N — k swaps to reduce it back to N disjoint vertices.
Then there are many ways of doing this. We can use dfs for example to compute the number of connected components. The number of edges isn O(N). So this is an O(N) algorithm. We can also use union-find. I think a union-find is usually quite efficient. The following is an implementation.”
Cyclic findings can be used to solve this problem. Union find is used to solve this problem. Code is here.
class Solution(object):
def minSwapsCouples(self, row):
self.uf = {}
def union(x, y):
self.uf[find(y)] = find(x)
def find(x):
self.uf.setdefault(x, x)
if self.uf[x] !=x :
self.uf[x] = find(self.uf[x])
return self.uf[x]
N = len(row)//2
for i in range(N):
a, b = row[2*i], row[2*i+1]
union(a//2, b//2)
return len(row)-len({find(i) for i in range(2*N)})839. Similar String Groups
Union find TLE solution
59 / 62 test cases passed.
class Solution:
def numSimilarGroups(self, A: List[str]) -> int:
self.uf = {}
def union(x, y):
self.uf[find(y)]=self.uf[find(x)]
def find(x):
self.uf.setdefault(x,x)
if x!=self.uf[x]:
self.uf[x] = find(self.uf[x])
return self.uf[x]
if len(set(list(A[0])))==1:return 1
for a,b in itertools.combinations(A, 2):
dif =0
for aa,bb in zip(a,b):
if aa!=bb:
dif+=1
if dif>2:break
else:
union(a,b)
return len({find(a) for a in A})Failed cases
“[“aaaaacedfb”,”aaaaacfbde”,”aaaaabecfd”,”aaaaaefdbc”,”aaaaafdecb”,”aaaaacefdb”,”…]
We can do some trick to reduce the word size if they have the same character for a position.
If we do so, the above failed test case will become:
“[“cedfb”,”cfbde”,”becfd”,”efdbc”,”fdecb”,”cefdb”,”…] as the first several letters for all words are the same.
We can do this trick naively, and still we will get TLE.
59 / 62 test cases passed.
class Solution:
def numSimilarGroups(self, A: List[str]) -> int:
self.uf = {}
def union(x, y):
self.uf[find(y)]=self.uf[find(x)]
def find(x):
self.uf.setdefault(x,x)
if x!=self.uf[x]:
self.uf[x] = find(self.uf[x])
return self.uf[x]
A_by_col = [new_a for new_a in zip(*A) if len(set(new_a))!=1]
if not A_by_col:return 1
for a,b in itertools.combinations(zip(*A_by_col), 2):
dif =0
for aa,bb in zip(a,b):
if aa!=bb:
dif+=1
if dif>2:break
else:
union(a,b)
return len({find(a) for a in zip(*A_by_col)})Never give up, if we do this by sorting A firstly, and then only compare first A[0] with last word A[-1] from the first position letter to last one. If they are the same, then all words are the same for this position. If not, we break. It is faster than the previous solution and got AC by lucky. I think if the same part is not putting at the beginning and it is randomly put, we will still get TLE.
AC solution (7484 ms)
class Solution:
def numSimilarGroups(self, A: List[str]) -> int:
self.uf = {}
def union(x, y):
self.uf[find(y)]=self.uf[find(x)]
def find(x):
self.uf.setdefault(x,x)
if x!=self.uf[x]:
self.uf[x] = find(self.uf[x])
return self.uf[x]
A.sort()
valid_idx = []
for i in range(len(A[0])):
if A[-1][i]==A[0][i]:continue
else:
valid_idx += list(range(i, len(A[0])))
break
if not valid_idx:return 1
for a,b in itertools.combinations(A, 2):
dif =0
for k in valid_idx:
if a[k]!=b[k]:
dif+=1
if dif>2:break
else:
union(a,b)
return len({find(a) for a in A})827. Making A Large Island
https://leetcode.com/problems/making-a-large-island/
Union find
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
R, C = len(grid), len(grid[0])
self.uf = {}
def find(x):
self.uf.setdefault(x,x)
if x!=self.uf[x]:
self.uf[x]=find(self.uf[x])
return self.uf[x]
def union(x ,y):
self.uf[find(y)] = find(x)
ones = set()
for i in range(R):
for j in range(C):
if grid[i][j]:
x= C*i+j
ones.add(x)
neighbors = [(i+di,j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]]
for r, c in neighbors:
if 0<=r<R and 0<=c<C and grid[r][c]:
y = C*r+c
ones.add(y)
union(x,y)
cnt = collections.defaultdict(int)
for i in ones:
cnt[find(i)]+=1
if not cnt:return 1
M = max(cnt.values())
if M==0:return 1
for i in range(R):
for j in range(C):
if not grid[i][j]:
neighbors = [(i+di,j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]]
good_nei = [(r,c) for r,c in neighbors if 0<=r<R and 0<=c<C and grid[r][c]]
if good_nei:
roots = set()
for r, c in good_nei:
y = C*r+c
roots.add(find(y))
new_M = 1+sum(cnt[key] for key in roots)
M =max(M, new_M)
return MThanks for reading.
