April 22, 2020 ### 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'):

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

m = len(grid)
n = len(grid)

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

return num_islands
``````

### Evaluation: Problem description source: leetcode

Recent Posts
Categories
Archive
Tags