Problem overview
The method numIslands receives a grid, a number[][], where 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically. The method returns how many islands the grid contains.
In the first example, every land cell touches another one side by side, so there is a single island. In the second example, the 1s in the top-left 2x2 block form one island, the lone 1 in the third row forms another, and the two 1s at the bottom right form a third, so the answer is 3. The lone 1 touches the top-left block only at a corner. Diagonal contact does not connect cells.
Approach: count, then erase the island
Scan the grid cell by cell. The first land cell you meet in a new island starts a count. The difficulty is that an island has many cells, and you must not count it again for each of them.
The fix is to erase an island as soon as it has been counted. When the scan reaches a 1, add one to the result, then 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 moves on, the rest of that island is already water, so it is never counted again. Each island adds exactly 1 to the result, at its first cell in reading order.
The DFS is a recursive method. For one cell it asks: is this cell land inside the grid? If not, stop. If it is, turn it into water, then do the same for the four neighbours: up, down, left and right.
The search changes the grid you pass in. That is fine for this lesson, but if the caller needs the original grid afterwards, copy it first.
Step by step
The lesson writes the main method first and assumes the helpers exist, then writes the helpers.
- Declare
resultwithletand set it to 0. It counts the islands found so far. - Loop over the rows with
ifrom 0 whilei < grid.length. - Loop over the columns inside it with
jwhilej < grid[0].length. All rows have the same length, so the first row's length is the column count. - Check whether
grid[i][j]is land, that is, strictly equal to 1. - Increment
resultinside theif. This is the only place the count changes. A land cell reached here was not erased by an earlier search, so it belongs to a new island. - Call
this.dfs(grid, i, j)to erase the island, still assumingdfsexists. - Return
resultafter the loops. - Write
dfs. It takes the grid, a row and a column, and returnsvoid. - Stop at invalid cells. Using a helper
this.isValidCell, return immediately if the cell is not valid. Water and off-grid neighbours both end the search in that direction. - Mark the cell as water by setting
grid[row][col]to 0 before recursing. Without this, two neighbouring cells would send the search back and forth forever. - Declare
directionsas an array of four pairs, each one a (row change, column change): up[-1, 0], down[1, 0], left[0, -1]and right[0, 1]. - Loop over the pairs with
for (const [i, j] of directions)and callthis.dfson(row + i, col + j). Theseiandjare new local names, unrelated to the loop indexes innumIslands. - Write
isValidCell. It takes the grid, a row and a column, and returns aboolean. - Return
falsewhen the cell is outside the grid, then return whethergrid[row][col]is 1. Checking the bounds first means the cell is only read when it exists.
The solution in TypeScript
class Solution {
isValidCell(grid: number[][], row: number, col: number): boolean {
if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length) {
return false;
}
return grid[row][col] === 1;
}
dfs(grid: number[][], row: number, col: number): void {
if (!this.isValidCell(grid, row, col)) {
return;
}
grid[row][col] = 0;
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [i, j] of directions) {
this.dfs(grid, row + i, col + j);
}
}
numIslands(grid: number[][]): number {
let result = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
result++;
this.dfs(grid, i, j);
}
}
}
return result;
}
}
TypeScript details worth a look:
- Arrays are objects.
dfsreceives a reference to the same grid, not a copy, so eachgrid[row][col] = 0is visible innumIslands. That is how the erasing works. - Methods call each other through
this. Inside a class,dfsandisValidCellare reached asthis.dfsandthis.isValidCell. The order in which the methods are written does not matter. - Destructuring in
for...of.const [i, j]unpacks each two-element array into two variables.constis fine here, because each iteration gets a fresh binding. - Short-circuit order. In the bounds check, the
||chain stops at the first true condition. The cell is only read after every bound has been checked, so a negative index never reachesgrid[row]. - Strict equality.
=== 1compares without converting types. With anumber[][]it matches the declared type.
Complexity
Time: O(m * n) for a grid with m rows and n columns. The scan visits each cell once. The DFS enters each land cell at most once as a valid cell, because it turns the cell into water immediately, and each entry checks four neighbours. Every cell is therefore handled a constant number of times.
Space: O(m * n) in the worst case, for the recursion stack. A grid that is entirely land makes the recursion as deep as the island is large. Everything else uses a constant amount of memory.
Edge cases and common mistakes
- Counting inside
dfs. The count belongs in the main loop, once per island. Ifdfsincremented it, every cell would count. - Not marking visited cells. Forgetting to set the cell to 0 makes the recursion go back and forth between two neighbours until the call stack overflows.
- Diagonal neighbours. Only four directions connect cells. Adding diagonals would merge the lone 1 in the second example into the top-left island and give 2 instead of 3.
- Checking bounds after reading. Reading
grid[row][col]withrowequal to-1givesundefinedfor the row, and indexing that throws aTypeError. The bounds test must come first. - An empty grid. With
[], the outer loop never runs, sogrid[0].lengthis never read, and the result is 0. - Very large islands. Recursion depth equals the island size in the worst case. A grid of 400 by 400 land cells overflowed the call stack with a
RangeErrorin a test run. For huge inputs you would switch to an explicit stack or a queue.
Testing
[[1, 1, 1, 1, 0], [1, 1, 0, 1, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]gives 1.[[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1]]gives 3.[[1, 0], [0, 1]]gives 2, because the two 1s touch only diagonally.[[0]]gives 0.