Number of islands

Question

In the counting number of islands problem, I noticed that one of the solution from internet is as follows

def visitIslandDFS(grid,  i,  j):
    if (i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0])):
        return  # return, if it is not a valid cell
    if (grid[i][j] == '0'):
        return  # return, if it is a water cell

    grid[i][j] = '0'  # mark the cell visited by making it a water cell

    visitIslandDFS(grid, i + 1, j)  # lower cell
    visitIslandDFS(grid, i - 1, j)  # upper cell
    visitIslandDFS(grid, i, j + 1)  # right cell
    visitIslandDFS(grid, i, j - 1)  # left cell

class Solution:

    def numIslands(self, grid: List[List[str]]) -> int:
        numIsland = 0
        depth, width = len(grid), len(grid[0])
        for i in range(depth):
            for j in range(width):
                if(grid[i][j] == '1'):
                    numIsland += 1
                    visitIslandDFS(grid, i, j)
        return numIsland

My question is if we are traversing left to right and top to bottom and flagging off cells to zero, may I know the reason why we are checking left and top cells as well for checks? In other words, I am trying to understand why these two lines are needed?

visitIslandDFS(grid, i - 1, j)  # upper cell
visitIslandDFS(grid, i, j - 1)  # left cell

Answer 1

If you avoid the up and left displacements, the algorithm will only fill down and right of the seed pixel and can fail to cover whole blobs.

E.g. from the top left pixel

. x . x
x x x x

will be filled as

. o . x
x o o o

Answer 2

Imagine having an island of the form:

..X
X.X
XXX

The solution starts looking at the island in the top right cell (smallest $i$).

If you never go left or up, you would only visit the three right cells during the first DFS and count them as the first island, and later when you do a second DFS you find a second island.

However there should only be one single island here.

..1
2.1
221

Answer 3

The above two cases are redundant if one try to solve the problem by looping over all possible grids and running dfs . Another approach to solve the problem is by storing all the unvisited grids into a queue, iteratively running a dfs until the queue is empty, in this case we can't be sure about the order in which the grids are visited thus visiting all the cardinal directions are suited.