Number of Islands

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

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

Example 2:

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

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Solution

Approach 1: DFS (Depth-First Search)

The key insight is to iterate through each cell, and when we find unvisited land (‘1’), we perform DFS to mark all connected land cells, then increment our island count.

Implementation

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        m, n = len(grid), len(grid[0])
        count = 0

        def dfs(r, c):
            # Check bounds and if it's water or visited
            if (r < 0 or r >= m or c < 0 or c >= n or
                grid[r][c] == '0'):
                return

            # Mark as visited
            grid[r][c] = '0'

            # Visit all 4 directions
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1

        return count

Approach 2: BFS (Breadth-First Search)

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        m, n = len(grid), len(grid[0])
        count = 0

        def bfs(r, c):
            queue = deque([(r, c)])
            grid[r][c] = '0'

            while queue:
                row, col = queue.popleft()
                directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < m and 0 <= nc < n and
                        grid[nr][nc] == '1'):
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    bfs(i, j)
                    count += 1

        return count

Complexity Analysis

DFS Approach:

Time Complexity: O(m * n), where m and n are grid dimensions. We visit each cell once.
Space Complexity: O(m * n) in worst case for recursion stack (if entire grid is land).

BFS Approach:

Time Complexity: O(m * n), same as DFS.
Space Complexity: O(min(m, n)) for the queue in worst case.

Key Insights

Connected Components: This is a classic connected components problem - counting distinct groups of connected cells.
Marking Visited: We can modify the grid in-place to mark visited cells (changing ‘1’ to ‘0’), avoiding the need for a separate visited set.
DFS vs BFS: Both approaches work equally well. DFS is slightly simpler to code, BFS uses less space in worst case.
Island Discovery: Each time we find an unvisited ‘1’, we’ve discovered a new island. The DFS/BFS marks all cells in that island.
Four Directions: Islands are formed by horizontal or vertical connections only (not diagonal).