CODING

Day 6: The “Number of Islands” Problem

Problem:

Given a 2d grid map of '1's (land) and '0's (water), count 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:
11110
11010
11000
00000
Output: 1

Example 2:

Input:
11000
11000
00100
00011
Output: 3

My Solution:

class Solution:
    def numIslands(self, grid):
        def colourGrid(i, j):
            if (0<=i<len(grid) and 0<=j<len(grid[i]) 
                and grid[i][j] == "1"):
                grid[i][j] ="0"
                colourGrid(i+1, j)
                colourGrid(i-1, j)
                colourGrid(i, j+1)
                colourGrid(i, j-1)
                return 1
            else :
                return 0
                
        return sum(colourGrid(i, j) for i in range(len(grid)) for j in range(len(grid[i])))

Explanation:

The objective is to count the number of islands.

We know, an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. To explore the island, we find out all lands connected to a land, by recursively searching positions in the top, bottom, left and right.

Once we land on an island (our current position is a land), to mark it as visited, we simply remove the visited island from the grid by sinking the land (mark land as water), and recursively sinking all connected lands around it.

Now that we know how to find an island, to solve this problem, at every position in the matrix, we check if its an island. If we find an island, we sink the island, and return that we have found one. Finally, we sum the number of positions at which we found islands.

That’s it! And that’s how you solve the “Number of Islands” problem.

If you are interested in solving more problems, do follow 60 Days of Coding and join me on this journey.

If you would like me to solve and explain any problems, please add them as comments, along with a link to the problem description.

See you tomorrow!

Cheers!