BFS same way different result (python)

Question

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

good catch , fixed

csguy
– csguy

2022-02-18 03:30:21 +00:00
Commented Feb 18, 2022 at 3:30 — csguy
– csguy, Commented Feb 18, 2022 at 3:30

Pychopath · Accepted Answer · 2022-02-18 03:31:18Z

1

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.

answered Feb 18, 2022 at 3:31

Pychopath

1,5803 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

BFS same way different result (python)

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related