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 boolean 2D array visited of the same dimensions as grid to keep track of visited cells. Initialize all elements of visited to false.

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's a potential new island. Increment numIslands.

4. Depth-First Search (DFS): Perform a Depth-First Search (DFS) starting from the current land cell to explore the entire connected island. The DFS will mark all connected land cells as visited in the visited array.

5. Return: After iterating through all cells, return numIslands.

Explanation

The Depth-First Search (DFS) is crucial for efficiently counting islands. When we find a land cell, we use DFS to explore all connected land cells. This ensures we don't count the same island multiple times. The visited array prevents revisiting cells and ensures that we explore each connected component only once.

Code

public class Solution {
    private int rows;
    private int cols;

    public int NumIslands(char[][] grid) {
        rows = grid.Length;
        if (rows == 0) return 0;
        cols = grid[0].Length;
        bool[,] visited = new bool[rows, cols];
        int numIslands = 0;

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

    private void DFS(char[][] grid, bool[,] visited, int i, int j) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0' || visited[i, j]) {
            return;
        }
        visited[i, j] = true;
        DFS(grid, visited, i + 1, j);
        DFS(grid, visited, i - 1, j);
        DFS(grid, visited, i, j + 1);
        DFS(grid, visited, i, j - 1);
    }
}

Complexity

• Time Complexity: O(M * N), where M and N are the number of rows and columns in the grid. In the worst case, we visit each cell once.
• Space Complexity: O(M * N) in the worst case, due to the visited array. The recursive calls in DFS also add to the space complexity, but it's bounded by the depth of the recursion, which is at most the minimum of M and N.