Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Number of Islands using DFS

Help me spot the error

Wrong Answer
Details
Input
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output
1
Expected
3

Using a depth first traversal to count islands

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        #Nested loop to go over our Grid
        #use depth first traversal in second loop to explore neighbors
        
        visited = set()
        count = 0
        
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if (self.explore(grid,row,col,visited)):
                    count +=1 
        return count
                
    def explore(self,grid,row,col,visited):
        #catch if we are out of bounds
        rowInbound = 0 <= row and row < len(grid)
        colInbound = 0 <= col and col < len(grid[0])
        
        if not rowInbound or not colInbound:
            return False
        
        #check if current is water
        position = grid[row][col]
        if (position == '0'):
            return False
        
        #check for visited 
        if position in visited:
            return False
        
        visited.add(position)
        
        self.explore(grid,row-1,col,visited)
        self.explore(grid,row+1,col,visited)
        self.explore(grid,row,col-1,visited)
        self.explore(grid,row,col+1,visited)
        
        #this true will symbolize that I am now exploring a new island
        
        return True     

>Solution :

The problem is that position has nothing to do with visited. position is the content of a cell, while visited should collect coordinates of a cell.

So change the relevant part to:

    if (row, col) in visited:
        return False
    
    visited.add((row, col))
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading