'Number of Islands problem on leetcode - incorrect answer on leetcode but correct locally
I am trying this solution for the number of islands problem on leetcode.
class Solution:
islands = 0
visited = []
def numIslands(self, grid: list[list[str]]) -> int:
self.islands = 0
islands = [ ]
_grid = [ row[:] for row in grid ]
for r, row in enumerate(grid):
for c, col in enumerate(row):
if grid[r][c] == "1":
islands.append( (r, c) )
for island in islands:
self.dfs(_grid, island, ignore=True)
return self.islands
def dfs(self, grid: list[list[str]], island, ignore=False):
if island in self.visited: return
row, col = island
if ignore and grid[row][col] == "1":
self.islands += 1
print("incrementing")
if grid[row][col] == "1":
if not ignore:
grid[row][col] = "0"
print((row,col), "ignore = ", ignore)
self.visited.append((row,col))
if row + 1 < len(grid):
self.dfs(grid, (row+1, col))
if col + 1 < len(grid[0]):
self.dfs(grid, (row, col+1))
if row -1 >= 0:
self.dfs(grid, (row -1,col))
if col - 1 >= 0:
self.dfs(grid, (row, col-1))
When I run it locally(m1 mac python version 3.9.10) on the test input:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
I get the correct number of islands(3), whereas, in leetcode, it says that my solution only returns 2 as the number of islands.
I don't know what maybe causing this issue, and i thought it had something to do with inplace modification of the grid but that doesn't seem to be the case either since i made a deep copy of the original
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|