Python Solution with Detailed Explanation


  • 0
    G

    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
    

Log in to reply
 

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