200. Number of Islands

Problem Statement

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

https://leetcode.cn/problems/number-of-islands/

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return 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:

Input: ` grid = [[“1”,”1”,”1”,”1”,”0”],[“1”,”1”,”0”,”1”,”0”],[“1”,”1”,”0”,”0”,”0”],[“0”,”0”,”0”,”0”,”0”]] **Output:** 1`

Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] Output: 3

Solution Approach

The solution leverages the Depth First Search (DFS) to traverse through each island and mark the visited cells to count the number of unique islands in the given grid.

Algorithm

1. Initialization: Begin by checking the dimensions of the grid and initializing a count for islands to zero.
2. DFS Traversal: For every unvisited cell with ‘1’, initiate a DFS traversal. During the DFS, for each visited cell, change its value from ‘1’ to ‘0’ to mark it as visited and recursively check its adjacent cells (up, down, left, and right) if they are part of the island.
3. Counting Islands: After the completion of each DFS traversal, increment the island count. Continue this until all cells in the grid are visited, then return the count.

Implement

    class Solution:
          def numIslands(self, grid: List[List[str]]) -> int:
              def dfs(i, j):
                  grid[i][j] = 0
                  q = [(i, j)]
                  for curi, curj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                      if 0 <= curi < m and 0 <= curj < n and grid[curi][curj] == "1":
                          dfs(curi, curj)

              if len(grid) == 0:
                  return 0
              m, n = len(grid), len(grid[0])
              count = 0
              for i in range(m):
                  for j in range(n):
                      if grid[i][j] == "1":
                          dfs(i, j)
                          count += 1
              return count

      
 

    
    

Twitter  facebook  Email