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).
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) 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
Problem description source: leetcode