solution.py

import collections, itertools, sys

coordinate = collections.namedtuple('coordinate', ('r', 'c'))

class Subset:
    def __init__(self, node, rank):
        self.parent = node
        self.rank = rank

class Graph:
    def __init__(self):
        self.V = 1
        self.islands = collections.defaultdict(set)

class NumberOfIslandsII:

    def _findParent(self, subsets, node):
        if subsets[node].parent != node:
            subsets[node].parent = self._findParent(subsets, subsets[node].parent)
        return subsets[node].parent

    def _union(self, head, p, subsets):
        subsets[p].parent = head
        if subsets[head].rank <= subsets[p].rank:
            subsets[head].rank, subsets[p].rank = subsets[p].rank + 1, subsets[head].rank
        return subsets

    def numIslands22(self, m, n, positions):
        if len(positions) <= 1:
            return [len(positions)]

        # Initialization
        island_subsets = collections.defaultdict(Subset)
        island_count = []
        curr_island = 0
        # Iterate thru the positions array
        for pos in positions:
            curr = coordinate(pos[0], pos[1])
            # New node
            if curr not in island_subsets.keys():
                neighbors = set()
                for neigh in [coordinate(curr.r, curr.c - 1), coordinate(curr.r, curr.c + 1),
                              coordinate(curr.r - 1, curr.c), coordinate(curr.r + 1, curr.c)]:
                    if neigh in island_subsets.keys():
                        # Find the node's parent and add it to neighbors set
                        neighbors.add(self._findParent(island_subsets, neigh))

                # No neighbors -> new island
                if len(neighbors) == 0:
                    curr_island += 1
                    head = curr
                else:
                    curr_island -= (len(neighbors) - 1)
                    # Set the largest tree as the parent
                    head = max(neighbors)
                    neighbors.remove(head)

                    # Merge graph
                    for p in neighbors:
                        island_subsets = self._union(head, p, island_subsets)

                # Add current node to the head and island subset
                island_subsets[curr] = Subset(head, 0)
                island_subsets = self._union(head, curr, island_subsets)

            # Update island count
            island_count.append(curr_island)

        return island_count

#     def _dfs(self, pos, islandsCoord, visited, idx):
#         visited.add(pos)
#
#         if coordinate(pos.r, pos.c - 1) in islandsCoord and coordinate(pos.r, pos.c - 1) not in visited:
#             visited.update(self._dfs(coordinate(pos.r, pos.c - 1), islandsCoord, visited, idx))
#
#         if coordinate(pos.r, pos.c + 1) in islandsCoord and coordinate(pos.r, pos.c + 1) not in visited:
#             visited.update(self._dfs(coordinate(pos.r, pos.c + 1), islandsCoord, visited, idx))
#
#         if coordinate(pos.r - 1, pos.c) in islandsCoord and coordinate(pos.r - 1, pos.c) not in visited:
#             visited.update(self._dfs(coordinate(pos.r - 1, pos.c), islandsCoord, visited, idx))
#
#         if coordinate(pos.r + 1, pos.c) in islandsCoord and coordinate(pos.r + 1, pos.c) not in visited:
#             visited.update(self._dfs(coordinate(pos.r + 1, pos.c), islandsCoord, visited, idx))
#
#         return visited
#
#     def numIslands2(self, m, n, positions):
#         if len(positions) <= 1:
#             return [len(positions)]
#
#         # 1. Initialize an empty array
#         #    and a set to keep track of islands' coordinates
#         islands = []
#         islandsCoord = set()
#
#         positionsIter = iter(positions)
#         for posArr in itertools.islice(positionsIter, 1):
#             islands.append(1)
#             islandsCoord.add(coordinate(posArr[0], posArr[1]))
#
#         # 2. a for loop to iterate thru positions array
#         for idx, posArr in enumerate(positionsIter):
#             # 3. Add a new set of land coord to islandsCoord
#             pos = coordinate(posArr[0], posArr[1])
#             currIslands = islands[-1]
#
#             if pos not in islandsCoord:
#                 # 4. Check its L, R, U, D
#                 neighbors = []
#                 coordinates = iter([coordinate(pos.r + 1, pos.c), coordinate(pos.r - 1, pos.c),
#                                         coordinate(pos.r, pos.c + 1), coordinate(pos.r, pos.c - 1)])
#
#                 for neighborCoord in coordinates:
#                     if neighborCoord in islandsCoord:
#                         neighbors.append(self._dfs(neighborCoord, islandsCoord, set(), idx ))
#                         break
#
#                 found = False
#                 for neighborCoord in coordinates:
#                     if neighborCoord in islandsCoord:
#                         for n in neighbors:
#                             if neighborCoord in n:
#                                 found = True
#
#                         if not found:
#                             neighbors.append(self._dfs(neighborCoord, islandsCoord, set(), idx ))
#
#                     found = False
#
#
#                 if len(neighbors) == 0: # no neighboring land -> new island
#                     currIslands += 1
#                 elif len(neighbors) > 1: # Combine multiple islands -> # of island decreases
#                     currIslands -= (len(neighbors) - 1)
#             # 5. Update islands count amd island coordinate
#             islandsCoord.add(pos)
#             islands.append(currIslands)
#
#         return islands