# Python Solution with Detailed Explanation

• Solution

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.
11110
11010
11000
00000
• 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[0])
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[0]) and board[a][b] == "1":
self.dfs(a,b,board)
return
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.