Number of Islands II

num_islands_ii.py

"""
Description:
A 2d grid map of m rows and n columns is initially filled with water. We may perform
an addLand operation which turns the water at position (row, col) into a land. Given
a list of positions to operate, count the number of islands after each addLand
operation. An island is surrounded by water and is formed by connecting adjacent lands
horizontally or vertically. You may assume all four edges of the grid are all
surrounded by water.

Example:
Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]

0 0 0    1 0 0    1 1 0    1 1 0    1 1 0
0 0 0 -> 0 0 0 -> 0 0 0 -> 0 0 1 -> 0 0 1
0 0 0    0 0 0    0 0 0    0 0 0    0 1 0
           1        1        2        3
"""

def numIslands2(m, n, positions):
    """
    :type m: int
    :type n: int
    :type positions: List[List[int]]
    :rtype: List[int]
    """
    parent, result = {}, [0]
    for r, c in positions:
        neighbors = set()
        for pos in ((r-1,c),(r,c-1),(r,c+1),(r+1,c)):
            if pos in parent:
                ppos = parent[pos]
                while ppos != parent[ppos]:
                    parent[ppos] = parent[parent[parent[ppos]]]
                    ppos = parent[ppos]
                neighbors.add(ppos)
        if len(neighbors) == 0:
            parent[(r, c)] = (r, c)
            result.append(result[-1] + 1)
        else:
            cur = neighbors.pop()
            for pos in neighbors:
                parent[pos] = cur
            parent[(r, c)] = cur
            result.append(result[-1] - len(neighbors))
    return result[1:]