Number of Islands

DFS

Problem

Given an m x n 2d grid 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.

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 300

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

For 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

Thought Process

• DFS is a good approach since we are dealing with connected components as well as neighboring cells and switching/marking the visited components

• Our DFS cycle will break once we are out of bounds or come across a element that is not a '1'

• We are utilizing DFS to change/mark the visited cells and recurssing on its neighboring cells

Solution

#Time: O(m*n) since we are traversing the whole matrix
#Space: O(m*n) for the recursion stack b/c worst case if we have all 1's
#then it's like s snak pattern in terms of stack calls

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    count+=1
                    self.dfsearch(grid,i,j)
                else:
                    continue
        return count
                    
        
    def dfsearch(self, grid, i, j):
        if i < 0 or i >= len(grid) or j >= len(grid[0]) or j < 0 or grid[i][j] != '1':
            return
        
        grid[i][j] = '0'
        
        self.dfsearch(grid,i+1,j)
        self.dfsearch(grid,i-1,j)
        self.dfsearch(grid,i,j-1)
        self.dfsearch(grid,i,j+1)
        

Time Complexity

• Time: O(m*n) since we are traversing the whole matrix

• Space: O(m*n) for the recursion stack b/c worst case if we have all 1's then it's like a snake pattern in terms of stack calls