200. Number of Islands

[mah-shamim]

Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix

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

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

[topugit]

We can use Depth-First Search (DFS) to explore and count the islands in the given 2D binary grid. The approach involves traversing the grid and performing DFS to mark all connected land cells for each island.

Let's implement this solution in PHP: 200. Number of Islands

<?php
class Solution {

    /**
     * @param String[][] $grid
     * @return Integer
     */
    function numIslands($grid) {
        if (empty($grid) || empty($grid[0])) {
            return 0;
        }

        $m = count($grid);
        $n = count($grid[0]);
        $islands = 0;

        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($grid[$i][$j] == '1') {
                    $this->dfs($grid, $i, $j, $m, $n);
                    $islands++;
                }
            }
        }

        return $islands;
    }

    private function dfs(&$grid, $x, $y, $m, $n) {
        // Check if the current cell is out of bounds or water
        if ($x < 0 || $x >= $m || $y < 0 || $y >= $n || $grid[$x][$y] != '1') {
            return;
        }

        // Mark the current cell as visited
        $grid[$x][$y] = 'x';

        // Perform DFS in all four directions
        $this->dfs($grid, $x + 1, $y, $m, $n);
        $this->dfs($grid, $x - 1, $y, $m, $n);
        $this->dfs($grid, $x, $y + 1, $m, $n);
        $this->dfs($grid, $x, $y - 1, $m, $n);
    }
}

// Example usage
$solution = new Solution();

$grid1 = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
];

$grid2 = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
];

echo "Output for grid1: " . $solution->numIslands($grid1) . "\n"; // Output: 1
echo "Output for grid2: " . $solution->numIslands($grid2) . "\n"; // Output: 3
?>

Explanation:

1. Class and Method Definitions:

• class Solution defines the class that contains the methods for solving the problem.
• numIslands is the main method to count the number of islands.

2. numIslands Method:

• Parameters: Takes a 2D grid ($grid) where each cell is either '1' (land) or '0' (water).
• Validation: Checks if the grid is empty. If so, it returns 0.
• Initialization: Defines the dimensions of the grid ($m for rows and $n for columns) and initializes the island count.
• Traversal: Iterates through each cell in the grid:
  • Land Cell Check: If a cell contains '1', it starts a DFS from that cell and increments the island count.
  • DFS Call: Calls the dfs method to mark all connected land cells as visited.
• Return: Returns the total number of islands found.

3. dfs Method:

• Parameters: Takes a reference to the grid ($grid), and coordinates ($x, $y), and the dimensions of the grid ($m, $n).
• Base Case: Checks if the current cell is out of bounds or if it is not land ('1'). If so, it returns immediately.
• Marking: Marks the current land cell as visited by setting it to 'x'.
• Recursive Calls: Recursively performs DFS in all four possible directions (up, down, left, right) to visit all connected land cells.

How It Works

• Initialization: The numIslands method initializes the island count and begins iterating over each cell in the grid.
• Island Detection: Whenever a '1' is encountered, it signifies a new island. The dfs method is invoked to explore and mark the entire island, ensuring that all connected land cells are considered part of the same island.
• DFS Traversal: The dfs method ensures that each cell in an island is visited exactly once, marking it as visited and preventing it from being counted again in future DFS calls.
• Counting Islands: The main method counts each distinct DFS call initiation as one island and returns the total count.

This approach efficiently counts the number of islands by exploring each land cell and marking all connected cells, ensuring that each island is counted only once.

[mah-shamim]

Thanks to solve the "Number of Islands" problem