Number of Islands (LC 200)

Pattern: Grid graph — DFS/BFS flood fill (connected components)
Difficulty: Medium
Key Concept: Each '1' cell is land; 4-directionally connected '1' cells form one island — count connected components by sinking visited land to avoid recounting.

Problem Statement

Given an m x n grid char[][] grid where '1' is land and '0' is water, count how many islands exist. An island is surrounded by water; you may assume all four edges are water.

Input: char[][] grid
Output: int — number of islands.

Example:

Output: 1.

1. Algorithm & Pseudocode

Brute force

For every pair of land cells, determine if they are in the same component (Union-Find or repeated BFS), then count components — overkill without careful merging.

Simpler brute: for each '1', BFS/DFS to collect component, mark visited in a separate boolean[][] (same as optimal but often taught first without mutating input).

Optimal

Linear scan + flood fill

count = 0
for each cell (r,c):
  if grid[r][c] == '1':
    count++
    dfs(r,c)   // or bfs: mark entire component as visited

dfs(r,c):
  if out of bounds or grid[r][c] != '1': return
  grid[r][c] = '0'   // sink visited (or use boolean[][])
  dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)

2. Step-by-Step Analysis (Beginner-Friendly)

The grid is an implicit graph: each land cell has up to 4 neighbors.
Without marking, you revisit cells forever in cycles.
Mutating '1'→'0' saves O(mn) extra memory; use a visited matrix if the input must stay read-only.
Each cell is entered as part of one DFS from its component’s first discovered cell, so total work is O(mn).

3. The Dry Run

Grid:

1 1 0
1 0 1
0 1 1

Step	Scan position	Action	count
1	(0,0) is `1`	DFS sinks (0,0),(0,1),(1,0)	1
2	(0,2) `0`	skip	1
3	(1,2) `1`	DFS sinks (1,2),(2,2),(2,1)	2
—	rest `0`	—	2

Two islands.

4. Java Solution

Brute Force

Separate visited matrix (does not mutate grid)

class SolutionBrute {
    private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        int ans = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1' && !vis[r][c]) {
                    ans++;
                    dfs(grid, vis, r, c);
                }
            }
        }
        return ans;
    }

    private void dfs(char[][] g, boolean[][] vis, int r, int c) {
        if (r < 0 || r >= g.length || c < 0 || c >= g[0].length) return;
        if (vis[r][c] || g[r][c] != '1') return;
        vis[r][c] = true;
        for (int[] d : DIRS) dfs(g, vis, r + d[0], c + d[1]);
    }
}

Time: O(mn), Space: O(mn) for vis + O(mn) stack worst case.

Optimal

In-place sinking

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int ans = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1') {
                    ans++;
                    sink(grid, r, c);
                }
            }
        }
        return ans;
    }

    private void sink(char[][] g, int r, int c) {
        if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != '1') return;
        g[r][c] = '0';
        sink(g, r + 1, c);
        sink(g, r - 1, c);
        sink(g, r, c + 1);
        sink(g, r, c - 1);
    }
}

BFS (iterative, good for deep recursion concerns):

import java.util.*;

class SolutionBFS {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int ans = 0;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != '1') continue;
                ans++;
                grid[r][c] = '0';
                q.add(new int[]{r, c});
                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {
                        int nr = cur[0] + d[0], nc = cur[1] + d[1];
                        if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                        if (grid[nr][nc] != '1') continue;
                        grid[nr][nc] = '0';
                        q.add(new int[]{nr, nc});
                    }
                }
            }
        }
        return ans;
    }
}

Time: O(mn), Space: O(mn) recursion stack or queue worst case; in-place O(1) extra if excluding stack.

5. The “Java vs. Others” Edge

char[][] comparisons use == '1' (primitives, fast).
Do not use Stack — ArrayDeque for BFS.
For read-only inputs, clone the grid or use boolean[][] to respect immutability.

6. Complexity Summary

Approach	Time	Space	Notes
Brute + `vis[][]`	O(mn)	O(mn) aux	Preserves original grid
Optimal in-place sink	O(mn)	O(1) extra + stack	Mutates input
BFS queue	O(mn)	O(min(mn)) queue typical	Avoids deep recursion

ASCII: Islands on grid

Before:          After DFS from first 1 in each island:

1 1 0 0          0 0 0 0
1 1 0 0    =>    0 0 0 0
0 0 1 0          0 0 0 0   (single cell island sunk)
0 0 0 1          0 0 0 0

Two separate components at bottom-right in a larger grid would be counted separately
when scan hits each unvisited '1'.