Number of Islands

Problem Statement

Given a 2D grid grid where '1' represents land and '0' represents water, count and return the number of islands.

An island is formed by connecting adjacent lands horizontally or vertically and is surrounded by water. You may assume water is surrounding the grid (i.e., all the edges are water).

Example 1:

Input: grid = [
    ["0","1","1","1","0"],
    ["0","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
  ]
Output: 1

Example 2:

Input: grid = [
    ["1","1","0","0","1"],
    ["1","1","0","0","1"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
  ]
Output: 4

Constraints:

  • 1 <= grid.length, grid[i].length <= 100
  • grid[i][j] is '0' or '1'.

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Hint 1

An island is a group of 1’s in which every 1 is reachable from any other 1 in that group. Can you think of an algorithm that can find the number of groups by visiting a group only once? Maybe there is a recursive way of doing it.

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse each group independently. We iterate through each cell of the grid. When we encounter a 1, we perform a DFS starting at that cell and recursively visit every other 1 that is reachable. During this process, we mark the visited 1’s as 0 to ensure we don’t revisit them, as they belong to the same group. The number of groups corresponds to the number of islands.

Solution

def num_islands_dfs(grid: List[List[str]]) -> int:
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    rows, cols = len(grid), len(grid[0])
    islands = 0


    def dfs(r, c):
        if (r < 0 or c < 0 or r >= rows or
            c >= cols or grid[r][c] == "0"
        ):
            return


        grid[r][c] = "0"
        for dr, dc in directions:
            dfs(r + dr, c + dc)


    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                dfs(r, c)
                islands += 1


    return islands

Time complexity: O(m * n) Space complexity: O(m * n)

from collections import deque


def num_islands_bfs(grid: List[List[str]]) -> int:
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    rows, cols = len(grid), len(grid[0])
    islands = 0


    def bfs(r, c):
        q = deque()
        grid[r][c] = "0"
        q.append((r, c))


        while q:
            row, col = q.popleft()
            for dr, dc in directions:
                nr, nc = dr + row, dc + col
                if (nr < 0 or nc < 0 or nr >= rows or
                    nc >= cols or grid[nr][nc] == "0"
                ):
                    continue
                q.append((nr, nc))
                grid[nr][nc] = "0"


    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                bfs(r, c)
                islands += 1


    return islands

Time complexity: O(m * n) Space complexity: O(m * n)

Disjoint Set Union

class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)


    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]


    def union(self, u, v):
        parent_u = self.find(u)
        parent_v = self.find(v)
        if parent_u == parent_v:
            return False
        if self.size[parent_u] >= self.size[parent_v]:
            self.size[parent_u] += self.size[parent_v]
            self.parent[parent_v] = parent_u
        else:
            self.size[parent_v] += self.size[parent_u]
            self.parent[parent_u] = parent_v
        return True




def num_islands_dsu(grid: List[List[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dsu = DisjointSetUnion(rows * cols)


    def index(r, c):
        return r * cols + c


    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    islands = 0


    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                islands += 1
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (nr < 0 or nc < 0 or nr >= rows or
                        nc >= cols or grid[nr][nc] == "0"
                    ):
                        continue


                    if dsu.union(index(r, c), index(nr, nc)):
                        islands -= 1


    return islands

Time complexity: O(m * n) Space complexity: O(m * n)