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

1. Initialization: Create a variable numIslands to count the number of islands, initialized to 0. Also create a function dfs to perform Depth-First Search.

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

3. Island Detection: If a cell contains '1' (land) and hasn't been visited, it signifies a new island. Increment numIslands.

4. Depth-First Search (DFS): Call the dfs function to explore all connected land cells from the current cell. The dfs function marks visited cells as '0' to avoid revisiting them.

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

Explanation

The core idea is to use Depth-First Search (DFS) to explore connected components of land. When we encounter a '1', we know we've found a new island. We then use DFS to mark all connected '1's as visited ('0') to prevent double-counting. This ensures that each distinct group of connected land cells is counted only once.

Code

function numIslands(grid: string[][]): number {
    let numIslands = 0;
    const rows = grid.length;
    const cols = grid[0].length;

    const dfs = (row: number, col: number) => {
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === '0') {
            return;
        }
        grid[row][col] = '0'; // Mark as visited
        dfs(row + 1, col);
        dfs(row - 1, col);
        dfs(row, col + 1);
        dfs(row, col - 1);
    };

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                numIslands++;
                dfs(i, j);
            }
        }
    }

    return numIslands;
};

Complexity

• Time Complexity: O(M * N), where M and N are the number of rows and columns in the grid, respectively. We visit each cell at most once.
• Space Complexity: O(M * N) in the worst case, which occurs when the entire grid is filled with land. This is due to the implicit recursive call stack used by DFS. In some cases, space complexity can be less depending on the structure of the islands. If you were to implement this iteratively using a stack, the space complexity would be O(min(M,N)) in the worst case.