Problem: https://leetcode.com/problems/number-of-islands/
Trying to figure out why calling the bfs function results in "correct" behavior according to the testcases, while just writing the plain code with no function call does not. It’s literally the same code.
class Solution:
def bfs(self, grid, queue):
while len(queue) != 0:
i, j = queue.pop(0)
if i - 1 >= 0 and grid[i - 1][j] == "1":
grid[i - 1][j] = "0"
queue.append((i - 1, j))
if i + 1 < len(grid) and grid[i + 1][j] == "1":
grid[i + 1][j] = "0"
queue.append((i + 1, j))
if j - 1 >= 0 and grid[i][j - 1] == "1":
grid[i][j - 1] = "0"
queue.append((i, j - 1))
if j + 1 < len(grid[i]) and grid[i][j + 1] == "1":
grid[i][j + 1] = "0"
queue.append((i, j + 1))
def numIslands(self, grid: List[List[str]]) -> int:
sol = 0
for i in range(0, len(grid), 1):
for j in range(0, len(grid[i]), 1):
if grid[i][j] == "1":
sol += 1
queue = [(i, j)]
grid[i][j] = "0"
# calling the function does different behavior
# self.bfs(grid, queue)
# as opposed to not calling the bfs function:
# while len(queue) != 0:
# print(queue)
# i, j = queue.pop(0)
# if i - 1 >= 0 and grid[i - 1][j] == "1":
# grid[i - 1][j] = "0"
# queue.append((i - 1, j))
# if i + 1 < len(grid) and grid[i + 1][j] == "1":
# grid[i + 1][j] = "0"
# queue.append((i + 1, j))
# if j - 1 >= 0 and grid[i][j - 1] == "1":
# grid[i][j - 1] = "0"
# queue.append((i, j - 1))
# if j + 1 < len(grid[i]) and grid[i][j + 1] == "1":
# grid[i][j + 1] = "0"
# queue.append((i, j + 1))
return sol
Testcase:
[["1","0","0","1","1","1","0","1","1","0","0","0","0","0","0","0","0","0","0","0"],["1","0","0","1","1","0","0","1","0","0","0","1","0","1","0","1","0","0","1","0"],["0","0","0","1","1","1","1","0","1","0","1","1","0","0","0","0","1","0","1","0"],["0","0","0","1","1","0","0","1","0","0","0","1","1","1","0","0","1","0","0","1"],["0","0","0","0","0","0","0","1","1","1","0","0","0","0","0","0","0","0","0","0"],["1","0","0","0","0","1","0","1","0","1","1","0","0","0","0","0","0","1","0","1"],["0","0","0","1","0","0","0","1","0","1","0","1","0","1","0","1","0","1","0","1"],["0","0","0","1","0","1","0","0","1","1","0","1","0","1","1","0","1","1","1","0"],["0","0","0","0","1","0","0","1","1","0","0","0","0","1","0","0","0","1","0","1"],["0","0","1","0","0","1","0","0","0","0","0","1","0","0","1","0","0","0","1","0"],["1","0","0","1","0","0","0","0","0","0","0","1","0","0","1","0","1","0","1","0"],["0","1","0","0","0","1","0","1","0","1","1","0","1","1","1","0","1","1","0","0"],["1","1","0","1","0","0","0","0","1","0","0","0","0","0","0","1","0","0","0","1"],["0","1","0","0","1","1","1","0","0","0","1","1","1","1","1","0","1","0","0","0"],["0","0","1","1","1","0","0","0","1","1","0","0","0","1","0","1","0","0","0","0"],["1","0","0","1","0","1","0","0","0","0","1","0","0","0","1","0","1","0","1","1"],["1","0","1","0","0","0","0","0","0","1","0","0","0","1","0","1","0","0","0","0"],["0","1","1","0","0","0","1","1","1","0","1","0","1","0","1","1","1","1","0","0"],["0","1","0","0","0","0","1","1","0","0","1","0","1","0","0","1","0","0","1","1"],["0","0","0","0","0","0","1","1","1","1","0","1","0","0","0","1","1","0","0","0"]]
calling function returns the expected solution: 58
while not calling returns: 47
>Solution :
Big picture view of your solution:
for i in range(0, len(grid), 1):
for j in range(0, len(grid[i]), 1):
run BFS
If you write the BFS code right there, it messes up the variable i from that outer loop (also j, but that doesn’t matter). If you instead call the function, that function has its own local variable i and doesn’t mess up the loop’s.