Problem statement

https://binarysearch.com/problems/Number-of-Islands-Online-Version/

Solution

Classical problem for union find, we just need to carefully deal with the fact that coordinates are not restricted.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class DSU:
    def __init__(self, graph):
        self.p = {i:i for i in graph}

    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 solve(self, positions):
        G = [tuple(x) for x in positions]
        q, ans, dsu = 0, [], DSU(G)
        V = set()
        neib_list = [[0,1],[0,-1],[1,0],[-1,0]]
        
        for x, y in positions:
            if (x, y) in V: continue
            V.add((x, y))
            q += 1
            for dx, dy in neib_list:
                if (x + dx, y + dy) in V:
                    if dsu.find((x, y)) != dsu.find((x + dx, y + dy)):
                        dsu.union((x, y), (x + dx, y + dy))
                        q -= 1
            ans.append(q)

        return ans