April 22, 2020
[LeetCode#200] Number of Islands

Description:

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.

For the above given figure, the number of islands are 3 (highlighted in 3 different colors).

 

Solution:

Start visiting the cells of the given grid in some order. If you come across any land (i.e cell with "1") increase the number of islands by 1. Now using DFS (Depth First Search) mask the land related to that island. This helps in simplifying the problem. The basic idea is to keep only single cell as "1" for each island and then count the number of "1"s.

# https://leetcode.com/problems/number-of-islands/

class Solution:
    # To mask the visited island
    def maskIsland(self, i, j, m, n, grid):
        grid[i][j] = 0
        neighbours = [(i, j - 1), (i - 1, j), (i + 1, j), (i, j + 1)]
        for neighbour in neighbours:
            i, j = neighbour
            if (not 0 <= i < m or not 0 <= j < n):
                continue
            if (grid[i][j] == '1'):
                self.maskIsland(i, j, m, n, grid)

    def numIslands(self, grid: List[List[str]]) -> int:
        if (not grid):
            return 0

        m = len(grid)
        n = len(grid[0])

        num_islands = 0
        
        # Start visiting cells of the grid in order
        for i in range(m):
            for j in range(n):
                if (grid[i][j] == '1'):
                    # Count the island if '1' is found
                    num_islands += 1
                    # Mask the land related to the found island
                    # to ease the search process
                    self.maskIsland(i, j, m, n, grid)

        return num_islands

 

Evaluation:

 

Problem description source: leetcode