# Number of islands

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


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


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


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.

• The cases are not redundant. They are necessary for the problem in question. Apr 3, 2023 at 6:56