1. Number of Islands

Description

Number of Islands

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'.

Approach

• we will start wherever we have one then we need to check in all directions
• Time complexity: O(m∗n)O(m∗n)
• Space complexity: O(m∗n)O(m∗n)

class Solution {
    private int[][] dir = new int[][] {{1,0},{0,1},{-1,0},{0,-1}};
    public int numIslands(char[][] grid) {
        int row = grid.length, col = grid[0].length;
        int island = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    island++;
                    dfs(grid,i,j);
                }
            }
        }
        return island;
    }
    public void dfs(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0')
            return;
 
        grid[row][col] = '0';
        for (int[] n: dir) {
            dfs(grid,row+n[0],col+n[1]);
        }    
    }
}

Primary Approach: DFS (“Sink the Island”) ($O(M\times N)$ Time, $O(M\times N)$ Space)

Intuition

Finding connected islands is equivalent to finding the number of connected components in an undirected grid graph:

1. Iterate through every cell in the grid.
2. When a land cell '1' is encountered, increment the island count and trigger a Depth-First Search (DFS) to visit all connected land cells horizontally and vertically.
3. During DFS, “sink” each visited land cell by changing '1' to '0'. Modifying the grid directly serves as an in-place visited tracker without requiring extra memory.

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
 
        int numIslands = 0;
        int m = grid.length;
        int n = grid[0].length;
 
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1') {
                    numIslands++;
                    dfs(grid, r, c);
                }
            }
        }
 
        return numIslands;
    }
 
    private void dfs(char[][] grid, int r, int c) {
        // Boundary check & land check
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') {
            return;
        }
 
        // Sink the land cell to mark it as visited
        grid[r][c] = '0';
 
        // Traverse 4-directionally
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}
 

Complexity

• Time Complexity: $O(M\times N)$ — Every cell is visited a constant number of times (at most once when triggering DFS and during neighboring checks).
• Space Complexity: $O(M\times N)$ — In the worst-case scenario (a grid filled entirely with land '1'), the call stack depth reaches $M\times N$.

---

Alternative Approach: BFS Level-Order Traversal ($O(M\times N)$ Time, $O(\min (M,N))$ Space)

Intuition

Traverse connected component lands using an explicit Queue:

1. Scan the grid. Upon finding '1', increment numIslands.
2. Push the cell coordinate into a Queue and mark it '0' immediately.
3. While the queue is non-empty, poll cells and inspect their 4-directional neighbors. Enqueue any neighboring '1' and instantly flip it to '0' to prevent duplicate enqueueing.

import java.util.ArrayDeque;
import java.util.Queue;
 
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
 
        int numIslands = 0;
        int m = grid.length;
        int n = grid[0].length;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1') {
                    numIslands++;
                    grid[r][c] = '0'; // Sink immediately on enqueue
                    Queue<int[]> queue = new ArrayDeque<>();
                    queue.add(new int[]{r, c});
 
                    while (!queue.isEmpty()) {
                        int[] curr = queue.poll();
 
                        for (int[] dir : directions) {
                            int nr = curr[0] + dir[0];
                            int nc = curr[1] + dir[1];
 
                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
                                grid[nr][nc] = '0'; // Sink before adding to avoid TLE/Memory limits
                                queue.add(new int[]{nr, nc});
                            }
                        }
                    }
                }
            }
        }
 
        return numIslands;
    }
}
 

Complexity

• Time Complexity: $O(M\times N)$ — Each cell enters and leaves the queue at most once.
• Space Complexity: $O(\min (M,N))$ — The max queue length is bounded by the diagonal length of the grid.

---

Key Interview Discussion Points

• Crucial BFS Bug to Avoid: Always flip grid[nr][nc] = '0' before pushing into the queue. Flipping upon popping leads to duplicate queue entries, causing severe memory overload / Memory Limit Exceeded (MLE).
• char[][] vs int[][] Trap: Notice that LeetCode inputs elements as characters ('1' and '0') rather than integers (1 and 0). Comparing grid[r][c] == 1 instead of '1' is a common mistake.

---

Easy Memory Rule

“Find '1' $\to$ Increment count $\to$ Sink connected land ('1' -> '0') via DFS/BFS to prevent duplicate counts!”