Simple checkboard for island Time complexity is O(n)


  • 0
    A
    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if not grid:
                return 0
            
            count = 0
            check = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
    
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] =='1' and not check[i][j]:
                        count += 1
                        self.search(grid,check,i,j)
       
            return count 
            
        def search(self,grid,check,i,j):
            
            if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]=='1' and not check[i][j]:
                check[i][j] = True
                self.search(grid,check,i-1,j)
                self.search(grid,check,i+1,j)        
                self.search(grid,check,i,j-1)
                self.search(grid,check,i,j+1)
              
              
    

Log in to reply
 

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