How to Solve the Number of Islands Problem in Python?

Estimated read time 2 min read

The Number of Islands problem is a classic algorithmic problem that asks you to count the number of disconnected “islands” in a grid of 1’s and 0’s. Here is an example of how to solve this problem in Python using a Depth-First Search (DFS) algorithm:

def numIslands(grid):
    if not grid:
        return 0
    
    def dfs(grid, 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(grid, i+1, j)
        dfs(grid, i-1, j)
        dfs(grid, i, j+1)
        dfs(grid, i, j-1)
    
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(grid, i, j)
                count += 1
    return count

In this solution, we use a nested function dfs to perform a Depth-First Search algorithm on the input grid. The function takes the grid and two indices i and j as input. It first checks if the indices are out of bounds or if the current element is ‘0’. If either of these conditions is true, the function returns without doing anything.

If the current element is ‘1’, the function marks the current element as visited by changing it to ‘0’. Then, it recursively calls itself with each adjacent element in the grid, continuing the DFS until all connected elements have been marked as visited.

In the main function, we iterate through each element in the grid and call dfs on each ‘1’ element we find. Each time we start a new DFS, we increment the count variable, which keeps track of the total number of disconnected islands we have found.

To use this function, simply call numIslands(grid) with the appropriate input grid grid. The function will return the number of disconnected islands in the grid.

You May Also Like

More From Author

+ There are no comments

Add yours

Leave a Reply