Leetcode # 200. Number of Islands

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

Solution: Disjoint Set Union (DSU)

Time Complexity: O(len(grid) * len(grid[0]))
Space Complexity: O(len(grid) * len(grid[0]))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
    l = 2
    map = [[0 if element =="0" else 1 for element in row] for row in grid ]
    for i in range(len(map)):
      for j in range(len(map[i])):
        if map[i][j] == 1:
          if i > 0 and map[i - 1][j] != 0:
            map[i][j] = map[i - 1][j]
          elif j > 0 and map[i][j - 1] != 0:
            map[i][j] = map[i][j - 1]
          else:
            map[i][j] = l
            l += 1
    
    parent = [i for i in range(l)]
    def find(x):
      return x if parent[x] == x else find(parent[x])
      
    def union(x, y):
      x_root = find(x)
      y_root = find(y)
      parent[x_root] = y_root
      
    for i in range(len(map)):
      for j in range(len(map[i])):
        if map[i][j] > 1:
          if i > 0 and map[i - 1][j] > 1 and map[i - 1][j] != map[i][j]:
            union(map[i - 1][j], map[i][j])
          elif j > 0 and map[i][j - 1] > 1 and map[i][j - 1] != map[i][j]:
            union(map[i][j - 1], map[i][j])
           
    ans = set()
    for p in parent[2:]:
      ans.add(find(p))
    return len(ans)

Last Updated on 2023/08/16 by A1go