Problem overview
The method sizeOfIslands receives a grid of 0s and 1s as a number[][]. A 1 is land and a 0 is water. An island is a group of land cells connected horizontally or vertically, and its size is the number of cells it contains. The method returns an array with the size of every island, in any order.
In the first example, all the land cells are linked to each other, so there is a single island and the answer is [9]. In the second example, the grid is:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
The top-left 2x2 block is an island of size 4. The lone 1 in the third row is an island of size 1. It touches the block only at a corner, and diagonal contact doesn't connect cells. The two 1s at the bottom right form an island of size 2. The method returns the sizes [4, 1, 2] in scan order, and the lesson accepts any order.
Approach: find an island, then count it while erasing it
Scan the grid cell by cell. When you reach a land cell, you have found a new island. Run a depth-first search (DFS) from there: it visits every land cell connected to the starting one, counts them, and turns each into water as it goes. When it finishes, the counter holds the size of the island, which you add to the result. Because the island is now water, the scan can't find it again.
Turning cells into water does two jobs. It prevents counting the same island twice, and it stops the recursion from going back and forth between two neighbours forever.
The counter lives in a field of the object, noOfCells, so that every recursive call can add to the same number. It is reset to 0 just before each search.
Step by step
The lesson writes the main method first, assuming a helper exists, and then writes the helpers.
- Declare
resultas an emptynumber[]. Each island's size is appended as it is found. - Loop over rows, with
ifrom 0 togrid.length. - Loop over columns, with
jfrom 0 togrid[0].length, the length of a row. - Test the cell with
if (grid[i][j]). The value 1 is truthy and 0 is falsy, and cells already erased by the search are 0. - Reset the counter with
this.noOfCells = 0, and declare the fieldnoOfCells: number;at the top of the class. - Call
this.dfs(grid, i, j)to count and erase the island. - Push
this.noOfCellsontoresult, and returnresultafter both loops. - Write
dfs. It takes the grid, a row and a column, and returnsvoid. It reports through the counter and by changing the grid. - Stop at invalid cells. If
isValidCellsays no,returnat once. That covers both cells outside the grid and water. - Count the cell with
this.noOfCells++, then set it to 0 so it is never counted again. - Visit the four neighbours. A constant list of moves
[-1, 0],[1, 0],[0, -1],[0, 1]gives up, down, left and right. Afor...ofloop with destructuring callsdfson each neighbour. - Write
isValidCell. One expression joins the row bounds, the column bounds andgrid[row][col] == 1with&&. The bounds come first so that an out-of-range cell is never read.
The solution in TypeScript
class Solution {
noOfCells: number;
isValidCell(grid: number[][], row: number, col: number): boolean {
return row >= 0 && row < grid.length &&
col >= 0 && col < grid[0].length &&
grid[row][col] == 1;
}
dfs(grid: number[][], row: number, col: number): void {
if (!this.isValidCell(grid, row, col)) {
return;
}
this.noOfCells++;
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);
}
}
sizeOfIslands(grid: number[][]): number[] {
let result: number[] = [];
for (let i = 0; i < grid.length; ++i) {
for (let j = 0; j < grid[0].length; ++j) {
if (grid[i][j]) {
this.noOfCells = 0;
this.dfs(grid, i, j);
result.push(this.noOfCells);
}
}
}
return result;
}
}
TypeScript details worth knowing:
- Declaring the field. In TypeScript, a class property must be declared before
this.noOfCellscan be used. The declarationnoOfCells: number;has no initial value, so the field isundefineduntil the first assignment. That is fine here, becausesizeOfIslandssets it to 0 before every search. Incrementing it before that would giveNaN. - Short-circuit bounds checks. In
isValidCell,&&stops at the first false operand. Readinggrid[-1]in JavaScript givesundefined, and then[col]on it would throw aTypeError, so the order of the conditions is not cosmetic. ==and===. The reference writes== 1here. For numbers both behave the same. The habit to keep is===by default.- Destructuring.
for (const [i, j] of directions)unpacks each two-element move into two names. Thoseiandjbelong todfsand are unrelated to the loop indexes insizeOfIslands. - The grid is changed in place. Arrays are passed by reference, so after the call the caller's grid is all zeros. On the second example the grid reads as four rows of five 0s afterwards. Copy the grid first if you still need it.
- Annotations are erased.
number[][]andbooleanare only for the compiler. The compiled JavaScript has no types.
Complexity
Let the grid have R rows and C columns.
Time: O(R * C). The scan visits each cell once. Each land cell is counted and erased by one dfs call, and every other call returns right away. Each cell receives at most four calls from its neighbours, so the total number of calls is bounded by a constant times the number of cells.
Space: O(R * C) in the worst case. The only extra memory is the recursion stack, apart from the result. One island that snakes through the whole grid makes the recursion as deep as the number of cells, and a very large one could raise a RangeError for exceeding the call stack. An explicit stack or a queue avoids that limit.
Edge cases and common mistakes
- No land.
[[0]]returns[], and so does an empty grid. - A single cell.
[[1]]returns[1]. - Diagonals.
[[1,0,1],[0,1,0],[1,0,1]]returns five islands of size 1. - A U-shaped island.
[[1,0,1],[1,0,1],[1,1,1]]is one island of size 7. The search follows it around the bend, so the two arms aren't counted separately. - Forgetting to reset the counter. Without
this.noOfCells = 0before each search, every size after the first would include the earlier islands. - Marking the cell after the recursive calls. Two neighbours would keep calling each other until the stack overflows.
- Rows of different lengths. The bounds use
grid[0].lengthfor every row, so the method assumes a rectangular grid. - Reusing the grid. Calling
sizeOfIslandsa second time on the same array returns[], because the first call erased the land.
Testing
- The first example grid gives
[9]. [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]gives[4, 1, 2].[[1,1],[1,1]]gives[4].[[1,0,1],[1,0,1],[1,1,1]]gives[7].[[0]]gives[].