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 1:

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

Example 2

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

Just Graph Traversal.

class App:
    def __init__(self) -> None:
        self.ISLAND = "1"
        self.WATER = "0"

    def numIslands(self, grid: List[List[str]]) -> int:
        numberOfIslands = 0
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == self.ISLAND:
                    self.searchIsland(grid, row, col)
                    numberOfIslands += 1
        
        return numberOfIslands

    def searchIsland(self, grid, row, col) -> None:
        if not self.isValidCell(grid, row, col): return
        
        grid[row][col] = self.WATER
        
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nextRow, nextCol = row + dr, col + dc
            self.searchIsland(grid, nextRow, nextCol)
            
    
    def isValidCell(self, grid, row, col): 
        return not (row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0])) \
            and grid[row][col] == self.ISLAND

Time complexity: $O(m \times n \times |V| + |E|)$
Space complexity: $O(|V| + |E|)$ — for dfs