Medium Matrices
Number of Islands
Receives a rectangular grid of integers, 0 for water and 1 for land, and returns how many islands it contains. An island is a maximal group of land cells connected horizontally or vertically, surrounded by water (the grid's four edges are treated as bordered by water). It scans the grid in row-major order and, whenever it finds an unvisited land cell, counts a new island and floods outward from it with a depth-first search that marks every land cell reachable through its four orthogonal neighbors as visited, so the outer scan never counts the same island twice. Returns the total number of islands found; an all-water grid returns 0.
Visualization
- Input
- Result
Algorithm code
// Number of Islands — a single pure function. Receives an integer grid where
// each cell is 0 (water) or 1 (land) and returns how many islands it contains.
// An island is a maximal group of land cells connected horizontally or
// vertically; the grid's four edges are assumed to be surrounded by water.
/**
* @param {number[][]} grid - rows x cols grid of 0s (water) and 1s (land)
* @returns {number} number of islands in the grid
*/
export function numIslands(grid) {
const rows = grid.length;
const cols = rows > 0 ? grid[0].length : 0;
if (rows === 0 || cols === 0) {
return 0;
}
const visited = grid.map((row) => row.map(() => false));
let islandCount = 0;
function flood(row, col) {
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return;
}
if (visited[row][col] || grid[row][col] !== 1) {
return;
}
visited[row][col] = true;
flood(row + 1, col);
flood(row - 1, col);
flood(row, col + 1);
flood(row, col - 1);
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] === 1 && !visited[row][col]) {
islandCount += 1;
flood(row, col);
}
}
}
return islandCount;
}FUNCTION numIslands(grid):
rows ← length(grid)
cols ← rows > 0 ? length(grid[0]) : 0
IF rows = 0 OR cols = 0:
RETURN 0
visited ← rows x cols grid of false
islandCount ← 0
FUNCTION flood(row, col):
IF row < 0 OR row >= rows OR col < 0 OR col >= cols:
RETURN
IF visited[row][col] OR grid[row][col] ≠ 1:
RETURN
visited[row][col] ← true
flood(row + 1, col)
flood(row - 1, col)
flood(row, col + 1)
flood(row, col - 1)
FOR row FROM 0 TO rows - 1:
FOR col FROM 0 TO cols - 1:
IF grid[row][col] = 1 AND NOT visited[row][col]:
islandCount ← islandCount + 1
flood(row, col)
RETURN islandCount