DEV Community

Cover image for 200. Number of Islands
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

1

200. Number of Islands

200. Number of Islands

Difficulty: Medium

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'.

Solution:

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
// 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
?>
Enter fullscreen mode Exit fullscreen mode

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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay