DFS (Recursive)

Scan every cell. When a '1' is found, it marks a new island — increment the count and use DFS to "sink" the island (mark all connected land cells as visited by setting them to '0').

public int numIslands(char[][] grid) { int count = 0; for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[0].length; c++) { if (grid[r][c] == '1') { count++; dfs(grid, r, c); // sink the entire island } } } return count; } private void dfs(char[][] grid, int r, int c) { // Bounds check and water/visited check if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return; grid[r][c] = '0'; // mark visited by sinking dfs(grid, r + 1, c); // down dfs(grid, r - 1, c); // up dfs(grid, r, c + 1); // right dfs(grid, r, c - 1); // left } This approach modifies the input grid. If that is not allowed, use a separate boolean[][] visited array.

BFS (Iterative)

Same idea but use a queue for the BFS expansion instead of recursion.

public int numIslands(char[][] grid) { int rows = grid.length, cols = grid[0].length; int count = 0; int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == '1') { count++; // BFS to sink the whole island Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{r, c}); grid[r][c] = '0'; while (!queue.isEmpty()) { int[] cell = queue.poll(); for (int[] d : dirs) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') { grid[nr][nc] = '0'; queue.offer(new int[]{nr, nc}); } } } } } } return count; }

• Time: O(m × n) — every cell is visited at most once.
• Space: O(m × n) — DFS call stack or BFS queue in the worst case (all land).