62. Number of Islands

You are given a map grid of m × n cells, where '1' is land and '0' is water.

An island is a group of land cells connected horizontally or vertically (diagonal neighbours do not count). Everything outside the grid is water. Return the number of islands.

Example 1

Input: grid = [["1","1","0","0","1"],["1","0","0","1","1"],["0","0","1","0","0"],["1","0","0","0","1"]]
Output: 5

Explanation: The top-left L shape, the top-right L shape, the single cell in the middle and the two bottom corners.

Example 2

Input: grid = [["1","1","1"],["1","0","1"],["1","1","1"]]
Output: 1

Explanation: A ring of land is still one island; the water in the middle does not split it.

Example 3

Input: grid = [["1","0"],["0","1"]]
Output: 2

Explanation: The two cells only touch diagonally.

Constraints

1 <= m, n <= 300
grid[i][j] is '0' or '1'

Follow-up: Land is added one cell at a time and you must report the island count after every addition. Which data structure makes that fast?

💡 Hint 1

Scan every cell. Each time you find land that you have not visited yet, you have found a new island.

💡 Hint 2

From that cell, flood-fill (DFS or BFS) to every connected land cell and mark them visited so they are not counted again.

💡 Hint 3

You can mark cells by overwriting them with '0', or keep a separate visited matrix if the input must not change.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Count connected components with a flood fill. Scan the grid; when a cell is '1', add one to the count and sink the whole island by turning every reachable land cell into '0'. The fill below uses an explicit stack instead of recursion, so a 300 × 300 all-land grid cannot overflow the call stack. Each cell is sunk at most once, so the total work is linear in the grid size.

Time O(m · n)Space O(m · n) in the worst case for the stack

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
      count++;
      grid[r][c] = '0';
      const stack = [[r, c]];
      while (stack.length) {
        const [y, x] = stack.pop();
        for (const [ny, nx] of [[y + 1, x], [y - 1, x], [y, x + 1], [y, x - 1]]) {
          if (ny >= 0 && ny < rows && nx >= 0 && nx < cols && grid[ny][nx] === '1') {
            grid[ny][nx] = '0';
            stack.push([ny, nx]);
          }
        }
      }
    }
  }
  return count;
}

class Solution {
    public int numIslands(char[][] grid) {
        int rows = grid.length, cols = grid[0].length, count = 0;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        Deque<int[]> stack = new ArrayDeque<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != '1') continue;
                count++;
                grid[r][c] = '0';
                stack.push(new int[] { r, c });
                while (!stack.isEmpty()) {
                    int[] cell = stack.pop();
                    for (int[] d : dirs) {
                        int y = cell[0] + d[0], x = cell[1] + d[1];
                        if (y >= 0 && y < rows && x >= 0 && x < cols && grid[y][x] == '1') {
                            grid[y][x] = '0';
                            stack.push(new int[] { y, x });
                        }
                    }
                }
            }
        }
        return count;
    }
}

/**
 * @param {character[][]} grid
 * @return {number}
 */
function numIslands(grid) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit