Space complexity of "Number of islands" BFS solution on Leetcode

Question

For the Leetcode question "Number of islands," I am trying to determine the SPACE complexity for the Breadth First Search solution.

from collections import deque


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        num_islands = 0
        num_row, num_col = len(grid), len(grid[0])
        for r in range(num_row):
            for c in range(num_col):
                if grid[r][c] == '1':
                    num_islands += 1
                    self.bfs(r, c, grid)
        return num_islands
                
    def bfs(
        self, 
        row: int, 
        col: int, 
        grid: List[List[str]]
    ) -> None:
        queue = deque([(row, col)])
        while queue:
            r, c = queue.popleft()
            if grid[r][c] != '1':
                continue
            grid[r][c] = 'X'
            if r+1 <= len(grid)-1 and grid[r+1][c] == '1':
                queue.append((r+1, c))
            if r-1 >= 0 and grid[r-1][c] == '1':
                queue.append((r-1, c))
            if c+1 <= len(grid[0])-1 and grid[r][c+1] == '1':
                queue.append((r, c+1))
            if c-1 >= 0 and grid[r][c-1] == '1':
                queue.append((r, c-1))

I am looking at this SO answer, but that example doesn't really elaborate on how exactly worst case BFS space complexity = O(M · N), where M = # of rows and N = number of columns. It states that the queue will have all of the leaf nodes, but how will that be? Also, how are all of the leaf nodes proportional to M · N? I think that diagram makes it hard to conceptualize.

I worked out a few examples, and I definitely see some cases where BFS space complexity > O(Max(M, N)), but can't grasp how it can be O(M·N) worst case. Can someone please explain, preferably with a visual walkthrough?

Example with space complexity = O(Min(M, N)) if you start at top-left corner, but > O(Max(M, N)) if you start in the middle:

[
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1]
]

A visual example like the one above will be easier to digest.

user_5483526 · Answer

It's not so easy to arrange, but the worst case BFS queue size for an MxM matrix is indeed in Ω(M²)

Lets say we have an MxM block, with M odd, where a BFS starting in the center of one side can reach W cells at the same time, implying a queue size of W.

It's not hard to arrange these into a 2M+3 x 2M+3 block that starts in the center of one side and reaches 4W cells at the same time, like this:

###   ###
###   ###
#S#   #S#
 #     #
 #######
 #  #  #
#S# # #S#
### # ###
### S ###

We can then repeat the procedure with these new blocks, and then repeat again, etc., as long as we like.

As these blocks get bigger and bigger, the extra 3 rows and columns take up a smaller and smaller proportion of the total. In terms of the number of repetitions of this procedure n, the length of the side M is in O(2ⁿ),

The maximum BFS queue size, of course is in Ω(4ⁿ), which is Ω(M²).

Here's what it looks like if you repeat the procedure a bunch of times. A BFS starting at the top will find all the other end points at the same level:

Space complexity of "Number of islands" BFS solution on Leetcode

1 Answers