Problem statement

https://leetcode.com/problems/number-of-islands-ii/

Solution

We can solve this problem just with dfs, but it can be too slow. So, we need to use Union Find data structure. First all our pixels located in separate sets. Then, for each new pixel, we look at its neighbors, check that pixels are in separate sets and if they are, union these two sets. We keep $x\cdot m + y$ as elements here, because we need to go from $2d$ to $1d$. How to evaluate number of islands now? When we add new pixel we increase number of island by 1 and then when we look to connections if we do union, we decrease number of islands by one.

Complexity

Time complexity of initialization step is $O(mn)$ and time complexity of each of $k$ queries is $O(T)$, complexity of one union find operation. If we use DSU with ranks $T = O(\log(mn))$, if we use with ranks and compression it is $O(A(mn))$, where $A$ is inverse Ackermann function, which is like $\leqslant 5$ for all feasible values. In the code below however we do not use any of these technique and potentially $T = O(mn)$, but in practice it works quite fast. Space complexity is $O(mn)$.

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def numIslands2(self, n, m, positions):
        q, ans, dsu = 0, [], DSU(m*n)
        grid = [[0] * m for _ in range(n)] 
        neib_list = [[0,1],[0,-1],[1,0],[-1,0]]
        
        for x, y in positions:
            if grid[x][y] == 0: 
                grid[x][y] = 1
                q += 1
                for dx, dy in neib_list:
                    index = (x+dx)*m + y+dy

                    if 0 <= x+dx < n and 0 <= y+dy < m and grid[x+dx][y+dy] == 1:
                        if dsu.find(index) != dsu.find(x*m+y):
                            dsu.union(index, x*m + y)
                            q -= 1
            
            ans.append(q)

        return ans