Number of Islands

MediumGraph DFS BFS Matrix

A sailing app plans routes through an archipelago using a gridded chart, grid, of m × n cells: '1' marks land and '0' marks open sea. Land cells that touch horizontally or vertically belong to the same island, while cells that only meet at a corner are not connected. Everything beyond the edge of the chart is sea.

Return the number of separate islands on the chart.

Example 1

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

Explanation: An L-shaped island on the left, a one-cell island in the top-right corner, a two-cell island in row 2 and a one-cell island in the bottom row.

Example 2

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

Explanation: The right-hand column joins the top and bottom rows into a single island.

Example 3

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

Explanation: The four land cells only meet at corners, so each one is an island of its own.

Constraints

The chart has between 1 and 300 rows and between 1 and 300 columns.
Every cell is the character '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