Leetcode 200. Number of Islands

Problem

Leetcode 200 - Number of Islands

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

Approach

We can use DFS to check the land that are connected and mark it as visited. If we have already visited, then we simply return.

We can increment the res whenever we have to run DFS

Here is the Python code for the solution:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = [[False] * len(grid[0]) for _ in range(len(grid))]
        res = 0

        def dfs(i, j):
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0' or visited[i][j] == True:
                return
            
            visited[i][j] = True
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
            return
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if visited[i][j] == True or grid[i][j] == '0':
                    visited[i][j] = True
                    continue
                dfs(i, j)
                res += 1
        
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n * m)$

Space Complexity: $O(n * m)$