Number of Islands II

Problem: Number of Islands II

Since this problem has a larger input and at each position we need to check all of its four neighbors, we need to optimize our solution. We need to implement path compression so that we can do union faster. To do this, we can attach smaller set to bigger set during union so that the set won't be too tall. We can also compress the path during finding by assign the parent of parent of current element to its parent.

Code in Python:

class Solution(object):
    def __init__(self):
        self.id = {}
        self.size = {}
        self.count = 0

    def add(self, position):
        self.id[position] = position
        self.size[position] = 1
        self.count += 1

    def root(self, i):
        while i != self.id[i]:
            self.id[i] = self.id[self.id[i]]
            i = self.id[i]
        return i

    def union(self, position, neighbor):
        i, j = self.root(position), self.root(neighbor)
        if i == j:
            return
        if self.size[i] > self.size[j]:
            i, j = j, i
        self.id[i] = j
        self.size[j] += self.size[i]
        self.count -= 1

    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        ans = []
        for position in map(tuple, positions):
            self.add(position)
            for distance in [(0,1), (0,-1), (1,0), (-1,0)]:
                neighbor = (position[0] + distance[0], position[1] + distance[1])
                if neighbor in self.id:
                    self.union(position, neighbor)
            ans.append(self.count)
        return ans