Number of Islands https://leetcode.com/problems/number-of-islands/
DFS to find Connected Components: O(V + E)
- One confusing thing about this question is to understand what is really being asked? All the 1s in the example below make up an island.
- Once you understand what is being asked, the question is a lot simpler. Just run DFS to find connected components.
- During DFS, mark as 0 to indicate visited status. This makes sure that we do not use any additional space.
class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ try: M, N = len(grid), len(grid) except: return 0 num_islands = 0 for i in range(M): for j in range(N): if grid[i][j] == "1": self.dfs(i,j,grid) num_islands += 1 return num_islands def dfs(self, i, j, board): board[i][j] = 0 # Mark as 0 to indicate visited status for a,b in ((i+1,j), (i-1,j), (i,j+1), (i,j-1)): if 0<=a<len(board) and 0<=b<len(board) and board[a][b] == "1": self.dfs(a,b,board) return