HomeLeetcode200. Number of Islands - Leetcode Solutions
Leetcode

200. Number of Islands – Leetcode Solutions

Declan Clarke

Description

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.

Examples:

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

Solution in Python

o solve the problem of counting the number of islands in a 2D binary grid, we can use a Depth-First Search (DFS) approach. The idea is to traverse the grid, and whenever we encounter a ‘1’ (representing land), we initiate a DFS to mark all connected ‘1’s (forming an island) as visited by changing them to ‘0’. This way, we ensure that each island is counted only once.

Steps

  1. Initialize the Number of Islands: Start by setting a counter to zero to keep track of the number of islands.
  2. Traverse the Grid: Loop through each cell in the grid.
  3. DFS on Land: If a cell contains ‘1’, it indicates the start of a new island. Increment the island counter and perform a DFS to mark all connected land cells as visited.
  4. Marking Visited Cells: During the DFS, convert each visited ‘1’ to ‘0’ to avoid counting the same island multiple times.
  5. Return the Result: After traversing the entire grid, return the island counter.
Python
from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # Helper function for depth-first search (DFS)
        def dfs(grid, i, j):
            # Check for boundaries and whether the cell is water ('0')
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
                return
            
            # Mark the cell as visited by setting it to '0'
            grid[i][j] = '0'
            
            # Perform DFS in all four directions (up, down, left, right)
            dfs(grid, i + 1, j)  # down
            dfs(grid, i - 1, j)  # up
            dfs(grid, i, j + 1)  # right
            dfs(grid, i, j - 1)  # left

        # Initialize the number of islands
        num_islands = 0

        # Traverse the grid
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # If a '1' is found, it's a new island
                if grid[i][j] == '1':
                    num_islands += 1  # Increment island count
                    dfs(grid, i, j)   # Perform DFS to mark the entire island
        
        # Return the total number of islands
        return num_islands

Explanation

  1. DFS Helper Function:
    • The dfs function is a recursive function that marks all the connected land cells (‘1’s) as visited by setting them to ‘0’. It recursively checks the four possible directions (up, down, left, right).
  2. Checking Boundaries:
    • Before performing the DFS, the function checks if the current cell is within the grid boundaries and whether it is a ‘1’. If it’s not, the DFS call returns immediately.
  3. Marking as Visited:
    • When a ‘1’ is found, it is marked as ‘0’ to prevent revisiting the same island.
  4. Traversing the Grid:
    • The main loop iterates through each cell of the grid. When a ‘1’ is found, it indicates the start of a new island. The island counter is incremented, and the DFS is initiated to mark all connected land cells.
  5. Returning the Number of Islands:
    • After the entire grid is processed, the total count of islands is returned.

This solution efficiently counts the number of islands by using DFS to traverse and mark connected components in the grid. It runs in O(m * n) time complexity, where m is the number of rows and n is the number of columns in the grid.

Solution in Javascript

JavaScript
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    // Helper function for depth-first search (DFS)
    function dfs(grid, i, j) {
        // Check for boundaries and whether the cell is water ('0')
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') {
            return;
        }
        
        // Mark the cell as visited by setting it to '0'
        grid[i][j] = '0';
        
        // Perform DFS in all four directions (up, down, left, right)
        dfs(grid, i + 1, j);  // down
        dfs(grid, i - 1, j);  // up
        dfs(grid, i, j + 1);  // right
        dfs(grid, i, j - 1);  // left
    }

    // Initialize the number of islands
    let numIslands = 0;

    // Traverse the grid
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            // If a '1' is found, it's a new island
            if (grid[i][j] === '1') {
                numIslands += 1;  // Increment island count
                dfs(grid, i, j);   // Perform DFS to mark the entire island
            }
        }
    }
    
    // Return the total number of islands
    return numIslands;
};

Solution in Java

Java
class Solution {
    public int numIslands(char[][] grid) {
        // If the grid is empty, return 0
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int numIslands = 0;  // Initialize the number of islands

        // Traverse the grid
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                // If a '1' is found, it's a new island
                if (grid[i][j] == '1') {
                    numIslands++;  // Increment the island count
                    dfs(grid, i, j);  // Perform DFS to mark the entire island
                }
            }
        }

        // Return the total number of islands
        return numIslands;
    }

    // Helper function for depth-first search (DFS)
    private void dfs(char[][] grid, int i, int j) {
        // Check for boundaries and whether the cell is water ('0')
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
            return;
        }

        // Mark the cell as visited by setting it to '0'
        grid[i][j] = '0';

        // Perform DFS in all four directions (up, down, left, right)
        dfs(grid, i + 1, j);  // down
        dfs(grid, i - 1, j);  // up
        dfs(grid, i, j + 1);  // right
        dfs(grid, i, j - 1);  // left
    }
}

Solution in C#

C#
public class Solution {
    public int NumIslands(char[][] grid) {
        // If the grid is empty, return 0
        if (grid == null || grid.Length == 0) {
            return 0;
        }

        int numIslands = 0;  // Initialize the number of islands

        // Traverse the grid
        for (int i = 0; i < grid.Length; i++) {
            for (int j = 0; j < grid[i].Length; j++) {
                // If a '1' is found, it's a new island
                if (grid[i][j] == '1') {
                    numIslands++;  // Increment the island count
                    DFS(grid, i, j);  // Perform DFS to mark the entire island
                }
            }
        }

        // Return the total number of islands
        return numIslands;
    }

    // Helper function for depth-first search (DFS)
    private void DFS(char[][] grid, int i, int j) {
        // Check for boundaries and whether the cell is water ('0')
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] == '0') {
            return;
        }

        // Mark the cell as visited by setting it to '0'
        grid[i][j] = '0';

        // Perform DFS in all four directions (up, down, left, right)
        DFS(grid, i + 1, j);  // down
        DFS(grid, i - 1, j);  // up
        DFS(grid, i, j + 1);  // right
        DFS(grid, i, j - 1);  // left
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com