Number of Islands - Python Solution

1. Introduction

"Number of Islands" is a classic problem in computer science, often used to teach concepts of graph traversal and depth-first search (DFS). The problem involves identifying distinct islands in a grid, where an island is formed by adjacent '1's (land) and surrounded by '0's (water). This problem is essential for understanding how to navigate and process grid-based data structures.

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), the objective is to return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

2. Solution Steps

1. Initialize a count of islands to 0.

2. Iterate over each cell of the grid.

3. When a cell with '1' (land) is found, increment the island count and initiate a DFS to mark all adjacent lands.

4. In DFS, mark the current land as visited (e.g., set to '0') and recursively call DFS for all adjacent lands (up, down, left, right).

5. Continue the process until all cells in the grid have been checked.

6. Return the total count of islands.

3. Code Program

def numIslands(grid):
    if not grid:
        return 0

    def dfs(i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1

    return count

# Example Usage
print(numIslands([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]))
print(numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]))

Output:

1
3

Explanation:

1. Depth-First Search (DFS): DFS is used to traverse and mark all the lands that are part of the same island.

2. Island Counting: Each time an unvisited land ('1') is found, the island count is incremented and DFS is initiated from that cell.

3. Marking Visited: During DFS, each visited land cell is marked as '0' to avoid revisiting it.

4. Adjacent Land Exploration: DFS explores all adjacent lands (up, down, left, right) that are part of the same island.

5. Comprehensive Exploration: The entire grid is explored, and each group of connected lands is counted as an island.

6. Total Islands: The function returns the total number of islands found in the grid.


Comments