< Back




200. Number of Islands

We're asked to determine the number of islands in a 2D matrix of "1"s and "0"s. "1"s represent
land, and islands are adjacent "1"s in the directions up, down, left, and right. This question
essentially asks us to find the connected components for the nodes represented by "1"s in this 2D
matrix. Nodes are connected if adjacent nodes are "1"s as well.

To solve this connectivity problem, we use Union-Find again. We maintain a parent and rank array
in the Union-Find class, doing a little extra work to create a hash map that we can index into with
our custom hashing function:

  i * m + j

where i and j are the row and column indices, and m is the number of columns in the 2D matrix.

When evaluating each node in the 2D matrix, we check to see if the current i, j matrix location
contains a "1". If so, we mark the location as seen by changing the value to "0". We then check all
adjacent locations to see if they're valid nodes containing a "1". If these adjacent locations are
connected to the current node, we merge their sets together.

Each time we execute union_set, we decrement the number of islands by 1. This is because we're
merging connected components together, and the number of connected components is the number of
islands.

The solution is as follows:


  from collections import defaultdict

  class UnionFind:
      def __init__(self, grid: List[List[str]]) -> None:
          self.count = 0
          n, m = len(grid), len(grid[0])
          self.parent, self.rank = [0 for _ in range(n * m)], [0 for _ in range(n * m)]

          for i in range(n):
              for j in range(m):
                  if grid[i][j] == "1":
                      self.parent[i * m + j] = i * m + j
                      self.count += 1
                  self.rank[i * m + j] = 0

      def find(self, x: int) -> int:
          if self.parent[x] != x:
              self.parent[x] = self.find(self.parent[x])
          return self.parent[x]

      def union_set(self, x: int, y: int) -> None:
          xset, yset = self.find(x), self.find(y)

          if xset != yset:
              if self.rank[xset] < self.rank[yset]:
                  self.parent[xset] = yset
              elif self.rank[yset] < self.rank[xset]:
                  self.parent[yset] = xset
              else:
                  self.parent[yset] = xset
                  self.rank[xset] += 1

              self.count -= 1

      def get_count(self) -> int:
          return self.count


  class Solution:
      def numIslands(self, grid: List[List[str]]) -> int:
          n, m = len(grid), len(grid[0])
          dsu = UnionFind(grid)

          for i in range(n):
              for j in range(m):
                  if grid[i][j] == "1":
                      grid[i][j] = "0"
                      if i - 1 > -1 and grid[i - 1][j] == "1":
                          dsu.union_set(i * m + j, (i - 1) * m + j)
                      if i + 1 < n and grid[i + 1][j] == "1":
                          dsu.union_set(i * m + j, (i + 1) * m + j)
                      if j - 1 > -1 and grid[i][j - 1] == "1":
                          dsu.union_set(i * m + j, i * m + (j - 1))
                      if j + 1 < m and grid[i][j + 1] == "1":
                          dsu.union_set(i * m + j, i * m + (j + 1))

          return dsu.get_count()


_ Time Complexity:

  O(n * m) - We iterate over all values in the 2D matrix.

_ Space Complexity:

  O(n * m) - We maintain the parent and rank arrays.