# Python Union-Find, Detailed English Explanation

• The key idea is to make each land position in an island point to a "root" land position in that island. Also maintain a mapping from roots to all land positions in the island

``````posToRoot = {}
rootToPos = {}
``````

When a new land position has no neighboring island, initialize a new island and set the new land position to its root

When a new land position has 1 neighboring island, make a new island with that position as the root

When a new land position has 2+ neighboring islands, combine the multiple islands with multiple roots to have just one root

``````from sets import Set

class Solution(object):
def numIslands2(self, m, n, positions):
"""
:type m: int
:type n: int
:type positions: List[List[int]]
:rtype: List[int]
"""
def getNeighbors(i, j):
# helper that gives list of indexes within m, n
neighbors = []
if i>0: neighbors.append((i-1, j))
if j>0: neighbors.append((i, j-1))
if i+1<m: neighbors.append((i+1, j))
if j+1<n: neighbors.append((i, j+1))
return neighbors

def getNeighborRoots(i, j):
# helper that returns list of roots for unique islands neighboring position i, j
return list(Set([posToRoot.get(x, None) for x in getNeighbors(i, j) if posToRoot.get(x, None)]))

posToRoot = {}
rootToPos = {}
res = []

for i, j in positions:
# for each new land position to add

neighborRoots = getNeighborRoots(i, j)
if not neighborRoots:
# no connected islands, make new island
rootToPos[(i, j)] = [(i, j)]
posToRoot[(i, j)] = (i, j)
else:
# has 1 or more connected islands
targetRoot = neighborRoots[0]
posToRoot[(i, j)] = targetRoot
rootToPos[targetRoot].append((i, j))
for i in range(1, len(neighborRoots)):
# if has more than 1 connected islands, combine
# extra islands into one single island
myroot = neighborRoots[i]
for pos in rootToPos[myroot]:
posToRoot[pos] = targetRoot
rootToPos[targetRoot].append(pos)
del rootToPos[myroot]
res.append(len(rootToPos))
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.