Number of Islands medium

Problem Statement

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

Steps and Explanation

The solution uses Depth-First Search (DFS) to count the number of islands. The algorithm iterates through each cell in the grid. If a cell contains '1' (land) and hasn't been visited yet, it means a new island has been found. A DFS function is then called to explore all connected land cells, marking them as visited. The count of islands is incremented for each new island found.

1. Initialization: Create a visited array of the same dimensions as the input grid to keep track of visited cells. Initialize it with all false values. Initialize a numIslands counter to 0.

2. Iteration: Iterate through each cell of the grid.

3. Island Detection: If a cell contains '1' (land) and hasn't been visited (visited[i][j] == false), it represents a new island. Increment numIslands.

4. Depth-First Search (DFS): Call a recursive DFS function to explore all connected land cells. The DFS function marks the current cell as visited and recursively calls itself for its adjacent unvisited land cells (up, down, left, right).

5. Return: After iterating through the entire grid, return numIslands.

Code (Java)

class Solution {
    public int numIslands(char[][] grid) {
        int numRows = grid.length;
        if (numRows == 0) return 0; //Handle empty grid
        int numCols = grid[0].length;
        boolean[][] visited = new boolean[numRows][numCols];
        int numIslands = 0;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    numIslands++;
                    dfs(grid, visited, i, j);
                }
            }
        }
        return numIslands;
    }

    private void dfs(char[][] grid, boolean[][] visited, int row, int col) {
        int numRows = grid.length;
        int numCols = grid[0].length;

        if (row < 0 || row >= numRows || col < 0 || col >= numCols || grid[row][col] == '0' || visited[row][col]) {
            return;
        }

        visited[row][col] = true;
        dfs(grid, visited, row + 1, col);
        dfs(grid, visited, row - 1, col);
        dfs(grid, visited, row, col + 1);
        dfs(grid, visited, row, col - 1);
    }
}

Complexity Analysis

• Time Complexity: O(M * N), where M and N are the number of rows and columns in the grid respectively. In the worst case, we visit each cell once.

• Space Complexity: O(M * N) in the worst case. This is due to the visited array, which stores the visited status of each cell. The recursive call stack of DFS can also consume space, but it's bounded by the maximum depth of the recursion which is at most M * N in the worst-case scenario of a single large island. Therefore, the space complexity is dominated by the visited array.