Leetcode BFS Set insertion giving TLE (200. Number of Islands)

Question

I am trying to solve the problem: Number of Islands on Leetcode using BFS traversal When I try to add the (r,c) pair in the visited set first thing in the loop, it gives me TLE in Leetcode.

Code for the above:

def numIslands(self, grid: List[List[str]]) -> int:
        islands = 0
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def bfs(r, c):
            q = [(r,c)]
            while q:
                row, col = q.pop(0)
                visited.add((row, col))  ## This line causes TLE
                directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
                for dr, dc in directions:
                    r = row + dr
                    c = col + dc
                    if (r in range(rows) and
                        c in range(cols) and
                        grid[r][c] == "1" and
                        (r,c) not in visited):
                        q.append((r,c))

        for r in range(rows):
            for c in range(cols):
                if (r,c) not in visited and grid[r][c] == "1":
                    bfs(r,c)
                    islands += 1
        return islands

And if I add the (r,c) in the if-block in the loop, the code passes.

def numIslands(self, grid: List[List[str]]) -> int:
        islands = 0
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def bfs(r, c):
            q = [(r,c)]
            visited.add((r, c)) #Visited the current (r,c)
            while q:
                row, col = q.pop(0)
                # visited.add((row, col)) ## Commented this out
                directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
                for dr, dc in directions:
                    r = row + dr
                    c = col + dc
                    if (r in range(rows) and
                        c in range(cols) and
                        grid[r][c] == "1" and
                        (r,c) not in visited):
                        q.append((r,c))
                        visited.add((r, c)) ## visited in the if-block

        for r in range(rows):
            for c in range(cols):
                if (r,c) not in visited and grid[r][c] == "1":
                    bfs(r,c)
                    islands += 1
        return islands

I dont understand, why the 2nd version of the code is passing and is more optimized, the queue will anyway always have elements where grid[r][c] == "1" or the queue will only have land elements.

Answer 1

In the first version of the code, a cell is only marked as visited after being popped from the queue. This can result in many copies of the same cell being added to the queue before the first occurrence of it is popped. This results in many more wasted iterations. You can get this code to pass by adding if (row, col) in visited: continue in the BFS loop.

On the other hand, the second version of the code is more idiomatic and marks the cell as visited as soon as it is reached for the first time and added to the queue. This ensures that other paths to the same cell will not add useless copies of this cell to the queue.

Also note that it is slow to remove the first element of a list; you should not use lists as a replacement for an actual queue data structure. Use collections.deque instead.