[Python] 4 Steps - Alternative to Union Find
Group by ID, is my workaround to the union-find method. Here are a few other problems where this approach can be used:\n\n\nProblem lexicographically-smallest-e
Group by ID, is my workaround to the union-find method. Here are a few other problems where this approach can be used:\n\n\nProblem <b><a href="https://leetcode.com/problems/lexicographically-smallest-equivalent-string">lexicographically-smallest-equivalent-string</a></b> with a similar <b><a href = "https://leetcode.com/problems/lexicographically-smallest-equivalent-string/discuss/776792/python-group-by-id-beats-100-runtime-and-memory">Solution</a></b> (100% runtime and memory)\nProblem <b><a href="https://leetcode.com/problems/friend-circles">friend-circles</a></b> with a similar <b><a href = "https://leetcode.com/problems/friend-circles/discuss/778619/python-alternative-to-union-find-beats-100">Solution</a></b> (100% runtime)\nProblem <b><a href="https://leetcode.com/problems/sentence-similarity-ii">sentence-similarity-ii</a></b> with a similar <b><a href = "https://leetcode.com/problems/sentence-similarity-ii/discuss/784419/python-better-than-union-find-beats-100">Solution</a></b> (100% runtime and 79% memory)\nProblem <b><a href="https://leetcode.com/problems/number-of-operations-to-make-network-connected">number-of-operations-to-make-network-connected</a></b> with a similar <b><a href = "https://leetcode.com/problems/number-of-operations-to-make-network-connected/discuss/783070/python-alternative-to-union-find-beats-100">Solution</a></b> (100% runtime)\nProblem <b><a href="https://leetcode.com/problems/accounts-merge">accounts-merge</a></b> with a similar <b><a href = "https://leetcode.com/problems/accounts-merge/discuss/778528/python-not-union-find-beats-99-annotated">Solution</a></b> (99% runtime and 97% memory)\nProblem <b><a href="https://leetcode.com/problems/synonymous-sentences">synonymous-sentences</a></b> with a similar <b><a href="https://leetcode.com/problems/synonymous-sentences/discuss/776936/Python-Group-and-DFS-Annotated-Beats-97.5">Solution</a></b> (97.5% runtime 75% memory)\nProblem <b><a href="https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends">the-earliest-moment-when-everyone-become-friends</a></b> with a similar <b><a href="https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/discuss/776624/python-pretend-islands-4-steps">Solution</a></b>\n\nPlease upvote if you found this helpful ~\n\n```python\ndef minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n\n\t#1. Convert graph to a list of edges\n\t#   This prevents us from revisiting any graph[i][j] == 0 every iteration.  \n\tR, C = len(graph), len(graph[0])\n\tedges = []\n\tfor a in range(R):\n\t\tfor b in range(a,C):\n\t\t\tif graph[a][b]:\n\t\t\t\tedges.append((a,b))\n\n\t#2. Find out how many nodes get infected when we do not include the "removed" node\n\tremove = {}\n\tfor removed in initial:\n\t\tgroup_id = 0\n\t\tgroup = {}\n\t\tnode_id = {}\n\n\t\t# Collect the nodes into groups based on their shared edges\n\t\t# Remember to ignore the "removed" node\n\t\tfor a,b in edges:\n\n\t\t\tif (a != removed) and (b != removed):\n\n\t\t\t\t#2.1 if node a and node b are in a group, merge the two groups\n\t\t\t\tif a in node_id and b in node_id:\n\t\t\t\t\tif node_id[a] == node_id[b]:\n\t\t\t\t\t\tcontinue\n\t\t\t\t\ttarget_id, obsolete_id = sorted((node_id[a], node_id[b]))\n\t\t\t\t\tfor node in group[obsolete_id]:\n\t\t\t\t\t\tnode_id[node] = target_id\n\t\t\t\t\tgroup[target_id] |= group[obsolete_id]\n\t\t\t\t\tdel group[obsolete_id]\n\n\t\t\t\t#2.2 If only node a or only node b is in a group, add the new node into that group\n\t\t\t\telif (a in node_id)|(b in node_id):\n\t\t\t\t\ta,b = (a,b) if a in node_id else (b,a)\n\t\t\t\t\ttarget_id = node_id[a]\n\t\t\t\t\tgroup[target_id] |= set([b])\n\t\t\t\t\tnode_id[b] = target_id\n\n\t\t\t\t#2.3 If neither a or b has a group, create a new group just for them\n\t\t\t\telse:\n\t\t\t\t\tgroup[group_id] = set([a,b])\n\t\t\t\t\tnode_id[a] = group_id\n\t\t\t\t\tnode_id[b] = group_id\n\t\t\t\t\tgroup_id += 1\n\n\t\t\t#2.4 If a is "removed" treat edge like [b,b]\n\t\t\t#    if b is "removed" treat edge like [a,a]\n\t\t\telse:\n\t\t\t\tif (a != removed) and (a not in node_id):\n\t\t\t\t\tgroup[group_id] = set([a])\n\t\t\t\t\tnode_id[a] = group_id\n\t\t\t\t\tgroup_id += 1\n\t\t\t\telif (b != removed) and (b not in node_id):\n\t\t\t\t\tgroup[group_id] = set([b])\n\t\t\t\t\tnode_id[b] = group_id\n\t\t\t\t\tgroup_id += 1\n\n\t\t#3. Check which groups are infected\n\t\tinfected = set()\n\t\tfor node in initial:\n\t\t\tif node in node_id:\n\t\t\t\tinfected.add(node_id[node])\n\n\t\t#4. Count the number of infected nodes\n\t\tremove[removed] = sum(len(group.get(node,[])) for node in infected)\n\n\tfewest_infected = min(remove.values())\n\treturn min(node for node in remove if (remove[node] == fewest_infected))\n```\n<img src="https://assets.leetcode.com/users/images/e5a061bf-e847-4bf9-b63e-3afe720b10b4_1597090098.4689705.png" width="55%">\n
[]