🏝️200. Number of Islands

Medium | Grind 75 | January 14th Saturday, 2023

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 surrounded by water.

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 300

• grid[i][j] is '0' or '1'.

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

The problem is about counting the number of distinct islands in a grid of 1's and 0's, where an island is a group of connected 1's. We will use a Depth First Search (DFS) algorithm to traverse the grid and identify the islands.

We iterate over every cell in the grid and whenever we encounter a 1, we perform a Depth First Search (DFS) from that position and explore all its connected cells. During DFS, we mark every cell that is a 1 as '#' to indicate it has been visited and won't be processed again. This will help us identify all the distinct islands in the grid. Each group of connected 1's found during DFS represents one island. We repeat this until we have iterated over every cell in the grid.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        """
            1. traverse the grid
            2. if you find a 1, then do a DFS or BFS from it.
            3. change 1s to '#' to indicate it has been visited
            4 repeat until the whole grid is processed
        """

        def dfs(row, col, grid): 
            """
                does a dfs to find all the 1's and change it to #
                :param: 
                    row(int): row index of the current element
                    col(int): col index of the current element
                    grid(2D array): original grid 
            """

                        #right   left    up      down
            neighbors = (0,1), (0,-1), (-1,0), (1,0)
            
            # check the four neighbors for 1s
            for (r,c) in neighbors:
                new_row, new_col = r+row, c+col
                if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and grid[new_row][new_col] == "1": 
                    grid[new_row][new_col] = "#"
                    dfs(new_row, new_col, grid)
            


        islands = 0
        for i in range(len(grid)): 
            for j in range(len(grid[0])): 
                if grid[i][j] == "1":
                    # to ensure not visiting the element again during DFS
                    grid[i][j] = '#'
                    # dfs search to find all the adjacents 1's  
                    dfs(i,j, grid)

                    # searched all the adjacent 1's so increment islands by 1            
                    islands += 1
        
        return islands n

TIME AND SPACE COMPLEXITY

TIME: O(n*m) where n is the number of rows and m is the number of columns. We iterate over every cell in the grid once. In the worst case where every cell is a 1, we iterate over every cell twice, resulting in O(2*(m*n)).

SPACE: O(1) space is constant since we do not use any extra space.

* Written with help from ChatGPT *