Problem overview
The method numIslands(self, grid) receives a grid, a list of lists, where 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically, and the method returns how many islands there are. Diagonal contact does not connect cells.
In the first example the 1s are all linked through side-by-side neighbours, so there is one island. In the second example the top-left 2x2 block is one island, the lone 1 in the third row is another, and the two 1s at the bottom right are a third. The answer is 3.
Approach: count the island, then erase it
Scan every cell. The first time the scan meets a land cell, it has found a new island. The problem is that the island has many cells, and each of them looks like land, so the scan would count the same island again and again.
The fix is to erase an island as soon as it is counted. When the scan reaches a 1, add one to the result and run a depth-first search (DFS) from that cell. The search visits every land cell connected to it and sets each one to 0. When the scan continues, the rest of that island is water, so it is never counted a second time. Each island adds exactly one to the result.
The DFS is a recursive function. For one cell it asks whether the cell is land inside the grid. If not, it stops. If so, it turns the cell into water, then repeats the same question for the four neighbours: up, down, left and right.
A brute-force alternative that keeps a separate "visited" set would also work, but it uses extra memory. Changing the grid in place costs no extra space beyond the recursion stack, at the price of destroying the input.
Step by step
- Declare
result = 0. It counts islands found so far. - Loop over the row indexes with
for i in range(len(grid)). - Loop over the column indexes with
for j in range(len(grid[0])). Every row has the same length, so the first row tells you the number of columns. - Test the cell with
if grid[i][j]:. In Python, 1 counts as true and 0 as false. - Add one to
resultinside theif. This is the only place where the count changes. A land cell reached here was not erased by an earlier search, so it starts a new island. - Call
self.dfs(grid, i, j)to erase the island, and returnresultafter the loops. - Write
dfs, takingself,grid,rowandcol. Lists are passed as the same object, so the cells it changes are changed in the caller's grid too. - Stop at invalid cells. Ask a helper,
isValidCell, whether the cell is on the grid and is land. If not,return. Water and off-grid neighbours both end the search in that direction. - Mark the cell as water by setting
grid[row][col] = 0before recursing. Without that, two neighbours would send the search back and forth forever. - Describe the four moves as pairs of (row change, column change) in
directions. - Recurse on each neighbour with
for i, j in directions, unpacking each pair and callingdfson(row + i, col + j). - Write
isValidCell. It returns whetherrow >= 0 and col >= 0 and grid[row][col] == 1inside atry, and anexcept IndexErrorreturnsFalse.
The solution in Python
class Solution:
def isValidCell(self, grid, row, col):
try:
return row >= 0 and col >= 0 and grid[row][col] == 1
except IndexError:
return False
def dfs(self, grid, row, col):
if not self.isValidCell(grid, row, col):
return
grid[row][col] = 0
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
for i, j in directions:
self.dfs(grid, row + i, col + j)
def numIslands(self, grid: List[List[int]]) -> int:
result = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]:
result += 1
self.dfs(grid, i, j)
return result
The Python details that matter here:
- Negative indexes do not fail. In most languages
grid[-1]is an error. In Python it is the last row. So a neighbour above row 0 would silently read the bottom row, and a neighbour left of column 0 would read the last column. Therow >= 0 and col >= 0checks prevent that, and sinceandshort-circuits,grid[row][col]is never read when either is negative. - Indexes past the end raise
IndexError. Theexceptturns that intoFalse. A more common style is an explicit test such as0 <= row < len(grid) and 0 <= col < len(grid[0]), which avoids exceptions altogether. - The cells are integers. The check is
== 1. A grid built from the strings"1"and"0"would not work:"0"is a non-empty string and therefore true, and"1" == 1is false. - The grid is modified. After
numIslandsreturns, every cell is 0. Make a copy first (for example[row[:] for row in grid]) if the original must survive. for i, j in directionsunpacks each two-element list. Theseiandjare local todfsand are unrelated to the loop variables innumIslands.
Complexity
- Time: O(m * n) for a grid with
mrows andncolumns. The scan visits every cell once. Each land cell is turned into water the first time DFS reaches it, so DFS does a constant amount of work per cell overall, plus one rejected call per neighbour. - Space: O(m * n) in the worst case, for the recursion stack. A grid that is entirely land, explored along a long winding path, can reach a depth equal to the number of cells. Python's default limit is 1000 nested calls, so a very large connected island raises
RecursionError: maximum recursion depth exceeded. For example, a 100 by 100 grid of all 1s does that. An iterative DFS with an explicit stack, or a breadth-first search with a queue, avoids the limit.
Edge cases and common mistakes
- All water. The answer is 0, because
resultnever changes. - All land. The answer is 1, and the whole grid is erased by the first search.
- Diagonal neighbours.
[[1,0],[0,1]]has two islands, since the four moves exclude diagonals. A checkerboard such as[[1,0,1],[0,1,0],[1,0,1]]has five. - Forgetting to mark visited cells. The recursion never ends, and Python stops it with
RecursionError. - Marking after the recursive calls instead of before. Each neighbour's call reaches the starting cell again while it is still land, so the recursion never ends.
- Dropping the
row >= 0andcol >= 0checks. The search then wraps around to the opposite edge and can count or erase the wrong cells. - Counting inside
dfs. The count must go up once per island, in the main loop, not once per cell.
Testing
The first example grid, with rows [1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0] and [0,0,0,0,0], gives 1. The second, with rows [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0] and [0,0,0,1,1], gives 3. A single cell [[1]] gives 1 and [[0]] gives 0.
