Number of Islands

1public int numIslands(char[][] grid) {
2    if (grid == null || grid.length == 0) {
3        return 0;
4    }
5
6    int rows = grid.length;
7    int cols = grid[0].length;
8    int count = 0;
9    int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
10
11    for (int row = 0; row < rows; row++) {
12        for (int col = 0; col < cols; col++) {
13
14            if (grid[row][col] == '1') {
15                count++;
16
17                // BFS to mark entire island
18                Queue<int[]> queue = new LinkedList<>();
19                queue.offer(new int[]{row, col});
20                grid[row][col] = 'V';  // Mark as visited
21
22                while (!queue.isEmpty()) {
23                    int[] curr = queue.poll();
24                    int currRow = curr[0], currCol = curr[1];
25
26                    // Check neighbors in S, N, E, W order
27                    for (int[] dir : directions) {
28                        int newRow = currRow + dir[0];
29                        int newCol = currCol + dir[1];
30
31                        if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
32                            if (grid[newRow][newCol] == '1') {
33                                grid[newRow][newCol] = 'V';
34                                queue.offer(new int[]{newRow, newCol});
35                            }
36                        }
37                    }
38                }
39            }
40        }
41    }
42
43    return count;
44}