MediumGraphs

Number of Islands

Q: Why copy the rows with toCharArray() instead of changing grid?

A Kotlin String cannot be changed in place: grid[r][c] = '0' does not compile, since String has a get operator but no set. toCharArray() returns a fresh CharArray per row, so sinking it leaves the caller's array exactly as it was. The union-find version needs no copy at all because it only reads grid[r][c].

Q: Is ArrayDeque here java.util.ArrayDeque?

No. Without an import, ArrayDeque resolves to kotlin.collections.ArrayDeque, the standard library's own resizable circular buffer, with addLast, removeFirst and isNotEmpty(). java.util.ArrayDeque works the same way with add and poll. Both are amortised O(1) at each end; MutableList.removeAt(0) would shift every element instead.

Q: What does ra = rb.also { rb = ra } do?

It swaps two vars in one line. also evaluates rb as the result, runs the block (which sets rb to the old ra), and then the assignment stores the old rb in ra. A val t = ra; ra = rb; rb = t is the longer equivalent.

Q: How do I make diagonal neighbours count as connected?

Add intArrayOf(1, 1), intArrayOf(1, -1), intArrayOf(-1, 1) and intArrayOf(-1, -1) to steps; the loop needs no other change. Corner contact then joins cells, so arrayOf("101", "010", "101") becomes 1 island instead of 5.

You get a map as an array of strings, one string per row and all of the same length. Each character is a cell: '1' is land and '0' is water. Two land cells belong to the same island when they share a side (above, below, left or right); cells that touch only at a corner are separate. Everything beyond the edges of the map is water.

Return how many islands the map has, as an integer. An empty array, or a map with no land at all, has 0 islands. Strings can't be changed in place, so mark the cells you have visited on your own copy of the rows or in a separate structure, and leave the caller's array as it was.

Examples

Input

grid = ["11000", "11010", "00011", "00000"]

Output2WhyThe 2 x 2 block in the top left is one island; the three cells on the right, joined top to bottom and then left to right, are the other.

Input

grid = ["101", "010", "101"]

Output5WhyEvery land cell touches the others only at corners, so each of the five is an island of its own.

Constraints

Rows: 0 ≤ grid.length ≤ 60
Columns: 1 ≤ grid[r].length ≤ 60
Cells: grid[r][c] is '0' or '1'
Shape: Every row has the same length.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Walk every cell. When you hit land, count a new island and call sink on it, which turns that cell into water and calls itself on the four neighbours. By the time it returns, the whole island is water, so the scan never counts it again. Strings can't be changed in place, so the function first copies the rows into lists; the caller's grid is left alone. The catch is the call stack: one long island can make the recursion as deep as its cell count, and Python stops at 1,000 frames by default.

def num_islands(grid: list[str]) -> int:
    cells = [list(row) for row in grid]  # a copy to sink; grid stays as it was

    def sink(r: int, c: int) -> None:
        if 0 <= r < len(cells) and 0 <= c < len(cells[r]) and cells[r][c] == "1":
            cells[r][c] = "0"  # visited: turn the land into water
            sink(r + 1, c)
            sink(r - 1, c)
            sink(r, c + 1)
            sink(r, c - 1)

    count = 0
    for r in range(len(cells)):
        for c in range(len(cells[r])):
            if cells[r][c] == "1":
                count += 1
                sink(r, c)
    return count

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

A disjoint-set structure gives every cell a parent, and a cell's root names its island. Count every land cell as a new island, then join it with the land directly above and to its left, the two neighbours the scan has already passed. Every join of two different roots takes one island off the count. Path halving in find and hanging the smaller tree under the bigger keep the trees almost flat. This version only reads the grid, so nothing is copied or sunk.

def num_islands(grid: list[str]) -> int:
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    parent = list(range(rows * cols))  # cell (r, c) is node r * cols + c
    size = [1] * (rows * cols)

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1":
                continue
            count += 1  # every land cell starts as its own island
            for nr, nc in ((r - 1, c), (r, c - 1)):  # neighbours already scanned
                if nr >= 0 and nc >= 0 and grid[nr][nc] == "1":
                    a, b = find(r * cols + c), find(nr * cols + nc)
                    if a != b:
                        if size[a] < size[b]:
                            a, b = b, a
                        parent[b] = a  # hang the smaller tree under the bigger
                        size[a] += size[b]
                        count -= 1  # two islands became one
    return count

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

This is the DFS idea with the recursion swapped for a queue. When the scan finds land, count it, sink it and put it in a deque. Then pop cells from the front, and sink and queue any land neighbour. Sinking a cell when it is queued, not when it is popped, stops the same cell from being queued twice. Because the loop keeps its own queue instead of using Python's call stack, island size never runs into the recursion limit, and the queue holds only the edge of the flood, which on most maps is far smaller than the grid.

from collections import deque


def num_islands(grid: list[str]) -> int:
    cells = [list(row) for row in grid]  # a copy to sink; grid stays as it was
    rows = len(cells)
    cols = len(cells[0]) if rows else 0
    count = 0
    for r in range(rows):
        for c in range(cols):
            if cells[r][c] != "1":
                continue
            count += 1
            cells[r][c] = "0"  # sink on enqueue so no cell is queued twice
            queue = deque([(r, c)])
            while queue:
                cr, cc = queue.popleft()
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and cells[nr][nc] == "1":
                        cells[nr][nc] = "0"
                        queue.append((nr, nc))
    return count

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

A nested loop visits every position. On land, it bumps the counter and hands the position to sink, an arrow function that writes '0' over the cell and then calls itself for the four sides. Bounds checks come almost for free in JavaScript: cells[-1] and any index past the end read as undefined, so cells[r]?.[c] !== '1' rejects a cell off the map and one that is already water in a single test. The rows are spread into character arrays first, because assigning to a string index does nothing. The weak spot is depth: one island can drive the recursion as deep as its cell count, and V8 gives up somewhere between 8,000 and 9,000 frames of this function.

function numIslands(grid) {
  const cells = grid.map((row) => [...row]); // a writable copy; the caller's strings stay intact

  const sink = (r, c) => {
    if (cells[r]?.[c] !== '1') return; // off the map or already water
    cells[r][c] = '0';
    sink(r + 1, c);
    sink(r - 1, c);
    sink(r, c + 1);
    sink(r, c - 1);
  };

  let count = 0;
  for (let r = 0; r < cells.length; r++) {
    for (let c = 0; c < cells[r].length; c++) {
      if (cells[r][c] === '1') {
        count++;
        sink(r, c);
      }
    }
  }
  return count;
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

Number the cells r * cols + c and store a disjoint-set forest in two Int32Arrays: parent and size. Typed arrays fit well here, since they hold fixed-width integers, start zeroed and never turn sparse. Each land cell raises the count by one; it is then joined to the land directly above and to its left, which are the only neighbours the scan has already reached. A join between two different roots means two islands were really one, so the count drops. find halves paths as it climbs, and the smaller tree always goes under the larger, which keeps lookups close to constant. The grid is only read, never copied.

function numIslands(grid) {
  const rows = grid.length;
  const cols = rows ? grid[0].length : 0;
  const parent = Int32Array.from({ length: rows * cols }, (_, i) => i); // cell (r, c) is r * cols + c
  const size = new Int32Array(rows * cols).fill(1);

  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  };

  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
      count++; // a new land cell is an island until a merge says otherwise
      const here = r * cols + c;
      // only the cell above and the cell to the left have been scanned so far
      for (const [nr, nc] of [
        [r - 1, c],
        [r, c - 1],
      ]) {
        if (nr < 0 || nc < 0 || grid[nr][nc] !== '1') continue;
        let a = find(here);
        let b = find(nr * cols + nc);
        if (a === b) continue;
        if (size[a] < size[b]) [a, b] = [b, a];
        parent[b] = a; // the smaller tree goes under the larger root
        size[a] += size[b];
        count--; // two islands joined into one
      }
    }
  }
  return count;
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

JavaScript has no built-in deque, and queue.shift() is specified to slide every remaining element down one slot. A cheap substitute is to keep pushing onto a normal array and walk it with a head index instead of removing anything. When the scan finds land, it counts it, writes '0' and seeds the queue; the inner loop then reads cells in order and queues any land neighbour, marking it as it goes in. Marking at enqueue time is what keeps a cell from landing in the queue twice. The pending work sits in heap memory, not on the call stack, so a large island cannot overflow anything.

function numIslands(grid) {
  const cells = grid.map((row) => [...row]); // a writable copy; the caller's strings stay intact
  const rows = cells.length;
  const cols = rows ? cells[0].length : 0;
  const steps = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (cells[r][c] !== '1') continue;
      count++;
      cells[r][c] = '0'; // mark when queued, so no cell enters the queue twice
      const queue = [[r, c]];
      // a read index instead of shift(), which would move every element each time
      for (let head = 0; head < queue.length; head++) {
        const [cr, cc] = queue[head];
        for (const [dr, dc] of steps) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && cells[nr][nc] === '1') {
            cells[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Strings are immutable, so first copy the rows into a string[][] of single characters with [...row]. A nested loop then scans every cell; on land it counts a new island and calls sink, which returns on anything off the map or already water, writes '0' and recurses into the four sides. The inner function closes over the copy, so it needs no extra parameters, and the caller's grid is never touched. Depth grows with the size of the biggest island, which is the one weakness of this version.

function numIslands(grid: string[]): number {
  const cells: string[][] = grid.map((row) => [...row]); // writable copy; grid stays as it was
  const rows = cells.length;
  const cols = rows ? cells[0].length : 0;

  function sink(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols || cells[r][c] !== '1') return;
    cells[r][c] = '0'; // visited
    sink(r + 1, c);
    sink(r - 1, c);
    sink(r, c + 1);
    sink(r, c - 1);
  }

  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (cells[r][c] === '1') {
        count++;
        sink(r, c);
      }
    }
  }
  return count;
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

Give each cell the number r * cols + c and keep a disjoint-set forest in two Int32Arrays, parent and size. Every land cell adds one to the count, then tries to join the land above it and to its left, the two neighbours the scan has already seen. union returns true only when it merges two different roots, and each real merge takes one off the count. find is a loop with path halving and the smaller tree goes under the larger, so nothing recurses and the grid is only read.

function numIslands(grid: string[]): number {
  const rows = grid.length;
  const cols = rows ? grid[0].length : 0;
  const parent = new Int32Array(rows * cols); // cell (r, c) is node r * cols + c
  const size = new Int32Array(rows * cols).fill(1);
  for (let i = 0; i < parent.length; i++) parent[i] = i;

  function find(x: number): number {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  }

  function union(a: number, b: number): boolean {
    let ra = find(a);
    let rb = find(b);
    if (ra === rb) return false;
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra; // the smaller tree goes under the larger root
    size[ra] += size[rb];
    return true;
  }

  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
      count++; // a new island until a merge says otherwise
      const cell = r * cols + c;
      if (r > 0 && grid[r - 1][c] === '1' && union(cell, cell - cols)) count--;
      if (c > 0 && grid[r][c - 1] === '1' && union(cell, cell - 1)) count--;
    }
  }
  return count;
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

Track visits in a Uint8Array of rows * cols flags instead of copying the rows, and hold the pending cells in a plain number[] of cell indices. A head index walks the queue forward, because shift() would move every remaining element on each call. A cell is marked the moment it is queued, so none enters the queue twice, and the work lives on the heap rather than the call stack, so a huge island is no problem.

function numIslands(grid: string[]): number {
  const rows = grid.length;
  const cols = rows ? grid[0].length : 0;
  const seen = new Uint8Array(rows * cols); // 1 once a cell has been queued
  const steps: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let count = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1' || seen[r * cols + c]) continue;
      count++;
      seen[r * cols + c] = 1; // mark on enqueue
      const queue: number[] = [r * cols + c];
      for (let head = 0; head < queue.length; head++) {
        const cr = Math.floor(queue[head] / cols);
        const cc = queue[head] % cols;
        for (const [dr, dc] of steps) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          const next = nr * cols + nc;
          if (grid[nr][nc] === '1' && !seen[next]) {
            seen[next] = 1;
            queue.push(next);
          }
        }
      }
    }
  }
  return count;
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Loop over rows and columns, and at each land char increment the count and call the static helper sink. The helper returns straight away for a position that is out of bounds or not land; otherwise it writes '0' and calls itself for the cells below, above, right and left. Once that first call returns, the entire island has become water. Java strings are immutable, so the method first builds a char[][] from toCharArray(), which hands back a new array for each row, and sinks that instead of the input. Depth is the trouble: each sink frame lives on a thread stack whose size is fixed when the thread starts, and a solid 100 x 100 island ends in StackOverflowError on this engine.

import java.util.*;

public class Main {
    static int numIslands(String[] grid) {
        char[][] cells = new char[grid.length][]; // a copy to sink; grid stays as it was
        for (int r = 0; r < grid.length; r++) {
            cells[r] = grid[r].toCharArray();
        }
        int count = 0;
        for (int r = 0; r < cells.length; r++) {
            for (int c = 0; c < cells[r].length; c++) {
                if (cells[r][c] == '1') {
                    count++;
                    sink(cells, r, c);
                }
            }
        }
        return count;
    }

    // Turns the land at (r, c) and every land cell connected to it into water.
    static void sink(char[][] cells, int r, int c) {
        if (r < 0 || r >= cells.length || c < 0 || c >= cells[r].length || cells[r][c] != '1') {
            return;
        }
        cells[r][c] = '0'; // visited: turn the land into water
        sink(cells, r + 1, c);
        sink(cells, r - 1, c);
        sink(cells, r, c + 1);
        sink(cells, r, c - 1);
    }
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

This version reads the input through charAt and writes only to two int[] arrays. Cell (r, c) becomes index r * cols + c; parent links each index toward a root, and two cells are on one island exactly when they reach the same root. Each land cell first adds one to the count. The cells above and to the left were scanned earlier, so the method tries union with each of them, and because union returns true only when it joins two different trees, the call sits inside the if condition and the count falls by one per real merge. find is a while loop with path halving and the smaller tree always goes under the larger, so stack depth stays flat however big the island.

import java.util.*;

public class Main {
    static int numIslands(String[] grid) {
        int rows = grid.length;
        int cols = rows > 0 ? grid[0].length() : 0;
        int[] parent = new int[rows * cols]; // cell (r, c) is node r * cols + c
        int[] size = new int[rows * cols];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r].charAt(c) != '1') {
                    continue;
                }
                count++; // every land cell starts as its own island
                int cell = r * cols + c;
                // join with the two neighbours the scan has already passed
                if (r > 0 && grid[r - 1].charAt(c) == '1' && union(parent, size, cell, cell - cols)) {
                    count--; // two islands became one
                }
                if (c > 0 && grid[r].charAt(c - 1) == '1' && union(parent, size, cell, cell - 1)) {
                    count--;
                }
            }
        }
        return count;
    }

    static int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    // Joins the trees of a and b; returns false if they already had the same root.
    static boolean union(int[] parent, int[] size, int a, int b) {
        int ra = find(parent, a);
        int rb = find(parent, b);
        if (ra == rb) {
            return false;
        }
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra; // hang the smaller tree under the bigger
        size[ra] += size[rb];
        return true;
    }
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

Replace the recursion with a queue and the stack problem disappears. On finding land, count it, set it to '0' and add an int[] holding its row and column to an ArrayDeque. While the deque has entries, poll the head and try the four offsets in the shared STEPS table; any neighbour that is still land is sunk and added immediately, so it can never be queued a second time. One deque serves every island, since it is empty again whenever an island is finished, and all pending cells sit on the heap rather than in frames.

import java.util.*;

public class Main {
    static final int[][] STEPS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    static int numIslands(String[] grid) {
        char[][] cells = new char[grid.length][]; // a copy to sink; grid stays as it was
        for (int r = 0; r < grid.length; r++) {
            cells[r] = grid[r].toCharArray();
        }
        int rows = cells.length;
        int cols = rows > 0 ? cells[0].length : 0;
        var queue = new ArrayDeque<int[]>(); // {row, col} pairs, reused for every island
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (cells[r][c] != '1') {
                    continue;
                }
                count++;
                cells[r][c] = '0'; // sink on enqueue so no cell is queued twice
                queue.add(new int[] {r, c});
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] step : STEPS) {
                        int nr = cell[0] + step[0];
                        int nc = cell[1] + step[1];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && cells[nr][nc] == '1') {
                            cells[nr][nc] = '0';
                            queue.add(new int[] {nr, nc});
                        }
                    }
                }
            }
        }
        return count;
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

The scan goes row by row. A land byte bumps the counter and hands its position to sink, which overwrites the byte with '0' and recurses up, down, left and right; any call that lands off the map or on water returns at once. When the first call unwinds, the island is gone and cannot be counted again. A Go string cannot be modified, so numIslands converts each row with []byte(row), which allocates a fresh writable slice, and the caller's data is never touched. Depth is where Go parts ways with Python and Java: a goroutine stack grows as calls pile up, so a deep flood only fails at the per-goroutine maximum, 1 GB by default on 64-bit platforms.

package main

// sink turns the land at (r, c) and every land cell connected to it into water.
func sink(cells [][]byte, r, c int) {
	if r < 0 || r >= len(cells) || c < 0 || c >= len(cells[r]) || cells[r][c] != '1' {
		return
	}
	cells[r][c] = '0' // visited: turn the land into water
	sink(cells, r+1, c)
	sink(cells, r-1, c)
	sink(cells, r, c+1)
	sink(cells, r, c-1)
}

func numIslands(grid []string) int {
	cells := make([][]byte, len(grid)) // a copy to sink; grid stays as it was
	for r, row := range grid {
		cells[r] = []byte(row)
	}
	count := 0
	for r := range cells {
		for c := range cells[r] {
			if cells[r][c] == '1' {
				count++
				sink(cells, r, c)
			}
		}
	}
	return count
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

Here no cell is ever erased. Each cell owns a slot in a parent slice, numbered r*cols + c, and the slot you reach by following parents is the island's representative. The scan adds one to the count for every land byte, then tries to merge it with the cell above and the cell to its left, the only neighbours already visited; a merge that really joins two separate trees subtracts one again. find is a closure over parent that halves the path as it climbs, and union by size keeps the trees shallow. Since grid[r][c] reads a byte straight out of the string, the input is never copied.

package main

func numIslands(grid []string) int {
	rows := len(grid)
	cols := 0
	if rows > 0 {
		cols = len(grid[0])
	}
	parent := make([]int, rows*cols) // cell (r, c) is node r*cols + c
	size := make([]int, rows*cols)
	for i := range parent {
		parent[i] = i
		size[i] = 1
	}
	find := func(x int) int {
		for parent[x] != x {
			parent[x] = parent[parent[x]] // path halving
			x = parent[x]
		}
		return x
	}

	count := 0
	for r := range rows {
		for c := range cols {
			if grid[r][c] != '1' {
				continue
			}
			count++                                              // every land cell starts as its own island
			for _, n := range [][2]int{{r - 1, c}, {r, c - 1}} { // neighbours already scanned
				nr, nc := n[0], n[1]
				if nr < 0 || nc < 0 || grid[nr][nc] != '1' {
					continue
				}
				a, b := find(r*cols+c), find(nr*cols+nc)
				if a == b {
					continue
				}
				if size[a] < size[b] {
					a, b = b, a
				}
				parent[b] = a // hang the smaller tree under the bigger
				size[a] += size[b]
				count-- // two islands became one
			}
		}
	}
	return count
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

Same scan, same sinking, but a loop drives the flood. The first land byte of an island is sunk and becomes the whole frontier. Each pass empties next with next[:0], appends every land neighbour of the frontier while sinking it on the spot, then swaps the two variables in one tuple assignment. Marking a cell as it is appended means no cell enters a ring twice. Coordinates are [2]int arrays, plain values stored inline in the slice, and because truncating to length zero keeps the capacity, later islands reuse the backing arrays the first one grew.

package main

func numIslands(grid []string) int {
	cells := make([][]byte, len(grid)) // a copy to sink; grid stays as it was
	for r, row := range grid {
		cells[r] = []byte(row)
	}
	rows := len(cells)
	cols := 0
	if rows > 0 {
		cols = len(cells[0])
	}
	count := 0
	var frontier, next [][2]int // two buffers, reused for every island
	for r := range rows {
		for c := range cols {
			if cells[r][c] != '1' {
				continue
			}
			count++
			cells[r][c] = '0' // sink on enqueue so no cell is queued twice
			frontier = append(frontier[:0], [2]int{r, c})
			for len(frontier) > 0 {
				next = next[:0]
				for _, p := range frontier {
					for _, n := range [][2]int{{p[0] + 1, p[1]}, {p[0] - 1, p[1]}, {p[0], p[1] + 1}, {p[0], p[1] - 1}} {
						nr, nc := n[0], n[1]
						if nr >= 0 && nr < rows && nc >= 0 && nc < cols && cells[nr][nc] == '1' {
							cells[nr][nc] = '0'
							next = append(next, n)
						}
					}
				}
				frontier, next = next, frontier // the next ring becomes the frontier
			}
		}
	}
	return count
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Scan the rows and columns; every '1' the scan meets is a new island, so count it and hand it to Sink. The helper returns at once for a position outside the map or one that is not land, otherwise it writes '0' and calls itself for the four neighbours, so by the time the first call returns the whole island is water and the scan cannot count it again. A C# string is immutable, so the method first turns each row into a fresh char[] with ToCharArray() and sinks that jagged copy; the caller's array is never touched. The cost is depth: each Sink frame sits on the thread's fixed-size stack, and one big solid island recurses once per cell.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int NumIslands(string[] grid)
    {
        var cells = new char[grid.Length][]; // a copy to sink; grid stays as it was
        for (int r = 0; r < grid.Length; r++)
        {
            cells[r] = grid[r].ToCharArray();
        }
        int count = 0;
        for (int r = 0; r < cells.Length; r++)
        {
            for (int c = 0; c < cells[r].Length; c++)
            {
                if (cells[r][c] == '1')
                {
                    count++;
                    Sink(cells, r, c);
                }
            }
        }
        return count;
    }

    // Turns the land at (r, c) and every land cell connected to it into water.
    static void Sink(char[][] cells, int r, int c)
    {
        if (r < 0 || r >= cells.Length || c < 0 || c >= cells[r].Length || cells[r][c] != '1')
        {
            return;
        }
        cells[r][c] = '0'; // visited: turn the land into water
        Sink(cells, r + 1, c);
        Sink(cells, r - 1, c);
        Sink(cells, r, c + 1);
        Sink(cells, r, c - 1);
    }
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

This version only reads the grid, through the string indexer, and writes to two int[] arrays. Cell (r, c) becomes node r * cols + c; parent points each node toward a root, and two cells share an island exactly when Find gives them the same root. Each land cell adds one to the count, then the method tries Union with the cell above and the cell to its left, the two neighbours the scan has already passed. Union returns true only when it joins two different trees, so the call sits inside the if and the count drops by one per real merge. Find is a while loop with path halving, and the smaller tree always hangs under the bigger, so there is no recursion to run out of.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int NumIslands(string[] grid)
    {
        int rows = grid.Length;
        int cols = rows > 0 ? grid[0].Length : 0;
        var parent = new int[rows * cols]; // cell (r, c) is node r * cols + c
        var size = new int[rows * cols];
        for (int i = 0; i < parent.Length; i++)
        {
            parent[i] = i;
            size[i] = 1;
        }
        int count = 0;
        for (int r = 0; r < rows; r++)
        {
            for (int c = 0; c < cols; c++)
            {
                if (grid[r][c] != '1')
                {
                    continue;
                }
                count++; // every land cell starts as its own island
                int cell = r * cols + c;
                // join with the two neighbours the scan has already passed
                if (r > 0 && grid[r - 1][c] == '1' && Union(parent, size, cell, cell - cols))
                {
                    count--; // two islands became one
                }
                if (c > 0 && grid[r][c - 1] == '1' && Union(parent, size, cell, cell - 1))
                {
                    count--;
                }
            }
        }
        return count;
    }

    static int Find(int[] parent, int x)
    {
        while (parent[x] != x)
        {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    // Joins the trees of a and b; returns false if they already had the same root.
    static bool Union(int[] parent, int[] size, int a, int b)
    {
        int ra = Find(parent, a);
        int rb = Find(parent, b);
        if (ra == rb)
        {
            return false;
        }
        if (size[ra] < size[rb])
        {
            (ra, rb) = (rb, ra);
        }
        parent[rb] = ra; // hang the smaller tree under the bigger
        size[ra] += size[rb];
        return true;
    }
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

Swap the recursion for a queue and the depth problem is gone. When the scan finds land, count it, set it to '0' and Enqueue its row and column as a (int, int) tuple. While the queue has entries, Dequeue the front cell and try the four offsets in the static Steps table; a neighbour that is still land is sunk and queued on the spot, so no cell can ever be queued twice. One Queue serves every island because it is empty again when an island is done, and the pending cells live on the heap as plain value tuples rather than in stack frames or boxed objects.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    static readonly (int, int)[] Steps = { (1, 0), (-1, 0), (0, 1), (0, -1) };

    public static int NumIslands(string[] grid)
    {
        var cells = new char[grid.Length][]; // a copy to sink; grid stays as it was
        for (int r = 0; r < grid.Length; r++)
        {
            cells[r] = grid[r].ToCharArray();
        }
        int rows = cells.Length;
        int cols = rows > 0 ? cells[0].Length : 0;
        var queue = new Queue<(int, int)>(); // (row, col) pairs, reused for every island
        int count = 0;
        for (int r = 0; r < rows; r++)
        {
            for (int c = 0; c < cols; c++)
            {
                if (cells[r][c] != '1')
                {
                    continue;
                }
                count++;
                cells[r][c] = '0'; // sink on enqueue so no cell is queued twice
                queue.Enqueue((r, c));
                while (queue.Count > 0)
                {
                    var (cr, cc) = queue.Dequeue();
                    foreach (var (dr, dc) in Steps)
                    {
                        int nr = cr + dr;
                        int nc = cc + dc;
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && cells[nr][nc] == '1')
                        {
                            cells[nr][nc] = '0';
                            queue.Enqueue((nr, nc));
                        }
                    }
                }
            }
        }
        return count;
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Copy the grid into a local vector<string>, since std::string is mutable and sinking the caller's rows would change data they still own. A nested loop finds each land cell, counts it and calls the private member sink, which takes the copy by reference, returns on anything off the map or already water, writes '0' and recurses into the four sides. The recursion depth is the size of the largest island, which fits the default stack easily at this bound.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int numIslands(vector<string>& grid) {
        vector<string> cells = grid; // a copy to sink; the caller's grid stays as it was
        int count = 0;
        for (int r = 0; r < (int)cells.size(); r++) {
            for (int c = 0; c < (int)cells[r].size(); c++) {
                if (cells[r][c] == '1') {
                    count++;
                    sink(cells, r, c);
                }
            }
        }
        return count;
    }

private:
    void sink(vector<string>& cells, int r, int c) {
        if (r < 0 || r >= (int)cells.size() || c < 0 || c >= (int)cells[r].size() || cells[r][c] != '1') return;
        cells[r][c] = '0'; // visited
        sink(cells, r + 1, c);
        sink(cells, r - 1, c);
        sink(cells, r, c + 1);
        sink(cells, r, c - 1);
    }
};

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

Number cell (r, c) as r * cols + c and keep the disjoint-set forest in two vector<int> members, filled with iota from <numeric>. Each land cell adds one island, then merges with the land above and to the left, the neighbours the scan has already passed; unite returns true only for a real merge, and each one takes an island away. find halves paths in a loop and the smaller tree hangs under the larger, so the grid is only read and nothing recurses.

#include <algorithm>
#include <numeric>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int numIslands(vector<string>& grid) {
        int rows = grid.size();
        int cols = rows ? grid[0].size() : 0;
        parent.assign(rows * cols, 0);
        iota(parent.begin(), parent.end(), 0); // every cell its own root
        size.assign(rows * cols, 1);
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != '1') continue;
                count++; // a new island until a merge says otherwise
                int cell = r * cols + c;
                if (r > 0 && grid[r - 1][c] == '1' && unite(cell, cell - cols)) count--;
                if (c > 0 && grid[r][c - 1] == '1' && unite(cell, cell - 1)) count--;
            }
        }
        return count;
    }

private:
    vector<int> parent, size;

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) swap(ra, rb);
        parent[rb] = ra; // the smaller tree goes under the larger root
        size[ra] += size[rb];
        return true;
    }
};

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

Keep a vector<vector<bool>> of visited flags and leave the grid alone. On an unvisited land cell, count it, mark it and push it onto a std::queue<pair<int, int>>; then pop cells off the front and push every land neighbour not yet seen, marking it as it goes in so no cell is queued twice. Structured bindings (auto [r, c] = q.front()) unpack each pair, and the pending cells sit on the heap, so island size never threatens the stack.

#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int numIslands(vector<string>& grid) {
        int rows = grid.size();
        int cols = rows ? grid[0].size() : 0;
        vector<vector<bool>> seen(rows, vector<bool>(cols, false));
        const int dr[] = {1, -1, 0, 0};
        const int dc[] = {0, 0, 1, -1};
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != '1' || seen[r][c]) continue;
                count++;
                seen[r][c] = true; // mark on enqueue
                queue<pair<int, int>> q;
                q.push({r, c});
                while (!q.empty()) {
                    auto [cr, cc] = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int nr = cr + dr[k], nc = cc + dc[k];
                        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                        if (grid[nr][nc] == '1' && !seen[nr][nc]) {
                            seen[nr][nc] = true;
                            q.push({nr, nc});
                        }
                    }
                }
            }
        }
        return count;
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Read the width with strlen(grid[0]) (every row is the same length) after returning 0 for an empty map, then calloc one bool per cell as the visited array, so the caller's strings are never written. The scan counts each unvisited land cell and calls the static helper sink, which stops at the edges, at water and at visited cells, marks the cell and recurses into its four sides. The flags are freed before returning.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static void sink(char** grid, bool* seen, int rows, int cols, int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] != '1' || seen[r * cols + c]) return;
    seen[r * cols + c] = true; // visited
    sink(grid, seen, rows, cols, r + 1, c);
    sink(grid, seen, rows, cols, r - 1, c);
    sink(grid, seen, rows, cols, r, c + 1);
    sink(grid, seen, rows, cols, r, c - 1);
}

int numIslands(char** grid, int gridSize) {
    if (gridSize == 0) return 0;
    int rows = gridSize;
    int cols = (int)strlen(grid[0]); // every row has the same length
    bool* seen = calloc((size_t)rows * cols + 1, sizeof *seen);
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1' && !seen[r * cols + c]) {
                count++;
                sink(grid, seen, rows, cols, r, c);
            }
        }
    }
    free(seen);
    return count;
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

Two malloc'ed int arrays, parent and size, hold a disjoint-set forest over the cell numbers r * cols + c. Each land cell adds one island, then tries to merge with the land above and to its left; unite returns true only when two different roots join, and each such merge takes one off the count. find is a loop with path halving and the smaller tree goes under the larger, so the grid is only read and nothing recurses. Both arrays are freed at the end.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int find(int* parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // path halving
        x = parent[x];
    }
    return x;
}

static bool unite(int* parent, int* size, int a, int b) {
    int ra = find(parent, a);
    int rb = find(parent, b);
    if (ra == rb) return false;
    if (size[ra] < size[rb]) {
        int t = ra;
        ra = rb;
        rb = t;
    }
    parent[rb] = ra; // the smaller tree goes under the larger root
    size[ra] += size[rb];
    return true;
}

int numIslands(char** grid, int gridSize) {
    if (gridSize == 0) return 0;
    int rows = gridSize;
    int cols = (int)strlen(grid[0]);
    int n = rows * cols;
    int* parent = malloc(((size_t)n + 1) * sizeof *parent);
    int* size = malloc(((size_t)n + 1) * sizeof *size);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != '1') continue;
            count++; // a new island until a merge says otherwise
            int cell = r * cols + c;
            if (r > 0 && grid[r - 1][c] == '1' && unite(parent, size, cell, cell - cols)) count--;
            if (c > 0 && grid[r][c - 1] == '1' && unite(parent, size, cell, cell - 1)) count--;
        }
    }
    free(parent);
    free(size);
    return count;
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

Replace the recursion with a queue: one malloc'ed int array of rows * cols cell indices, read from a head and written at a tail. A cell is marked in the visited array when it is enqueued, so each cell enters the queue at most once and the array can never overflow. Every island reuses the same buffer, starting again at index 0, and the index splits back into row and column with / and %. Both buffers are freed before returning.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int numIslands(char** grid, int gridSize) {
    if (gridSize == 0) return 0;
    int rows = gridSize;
    int cols = (int)strlen(grid[0]);
    int n = rows * cols;
    bool* seen = calloc((size_t)n + 1, sizeof *seen);
    int* queue = malloc(((size_t)n + 1) * sizeof *queue); // cell indices r * cols + c
    static const int dr[] = {1, -1, 0, 0};
    static const int dc[] = {0, 0, 1, -1};
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != '1' || seen[r * cols + c]) continue;
            count++;
            int head = 0, tail = 0;
            seen[r * cols + c] = true; // mark on enqueue
            queue[tail++] = r * cols + c;
            while (head < tail) {
                int cell = queue[head++];
                int cr = cell / cols, cc = cell % cols;
                for (int k = 0; k < 4; k++) {
                    int nr = cr + dr[k], nc = cc + dc[k];
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                    int next = nr * cols + nc;
                    if (grid[nr][nc] == '1' && !seen[next]) {
                        seen[next] = true;
                        queue[tail++] = next;
                    }
                }
            }
        }
    }
    free(seen);
    free(queue);
    return count;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Kotlin strings are immutable, so Array(grid.size) { grid[it].toCharArray() } builds an Array<CharArray> to sink. The scan counts every '1' it meets and calls sink, which returns for a cell off the map or not land, writes '0', and recurses into the four neighbours. When the first call returns the whole island is water and the scan cannot count it again. The recursion is as deep as the island is big, 625 frames for the solid 25 x 25 case, well inside the JVM's default stack.

class Solution {
    fun numIslands(grid: Array<String>): Int {
        val cells = Array(grid.size) { grid[it].toCharArray() } // a copy to sink; grid stays as it was
        var count = 0
        for (r in cells.indices) {
            for (c in cells[r].indices) {
                if (cells[r][c] == '1') {
                    count++
                    sink(cells, r, c)
                }
            }
        }
        return count
    }

    // Turns the land at (r, c) and every land cell connected to it into water.
    private fun sink(cells: Array<CharArray>, r: Int, c: Int) {
        if (r !in cells.indices || c !in cells[r].indices || cells[r][c] != '1') return
        cells[r][c] = '0'
        sink(cells, r + 1, c)
        sink(cells, r - 1, c)
        sink(cells, r, c + 1)
        sink(cells, r, c - 1)
    }
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

This version only reads grid and keeps its state in two IntArrays: cell (r, c) is node r * cols + c, and parent links each node toward the root of its island. Every land cell adds one to the count, then joins the cells above and to its left; union is a local function that returns true only for a real merge, so the count drops once per merge. find is a while loop with path halving and the smaller tree goes under the larger, so nothing recurses.

class Solution {
    fun numIslands(grid: Array<String>): Int {
        val rows = grid.size
        val cols = if (rows > 0) grid[0].length else 0
        val parent = IntArray(rows * cols) { it } // cell (r, c) is node r * cols + c
        val size = IntArray(rows * cols) { 1 }

        fun find(start: Int): Int {
            var x = start
            while (parent[x] != x) {
                parent[x] = parent[parent[x]] // path halving
                x = parent[x]
            }
            return x
        }

        // Joins the trees of a and b; false if they already had the same root.
        fun union(a: Int, b: Int): Boolean {
            var ra = find(a)
            var rb = find(b)
            if (ra == rb) return false
            if (size[ra] < size[rb]) ra = rb.also { rb = ra }
            parent[rb] = ra // hang the smaller tree under the bigger
            size[ra] += size[rb]
            return true
        }

        var count = 0
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] != '1') continue
                count++ // every land cell starts as its own island
                val cell = r * cols + c
                // join with the two neighbours the scan has already passed
                if (r > 0 && grid[r - 1][c] == '1' && union(cell, cell - cols)) count--
                if (c > 0 && grid[r][c - 1] == '1' && union(cell, cell - 1)) count--
            }
        }
        return count
    }
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

The same flood without recursion: Kotlin's own ArrayDeque<Int> holds the cells still to visit, each packed as r * cols + c so no pair object is created. A land cell is sunk when it is added, never when it is removed, so no cell enters the queue twice. The four offsets come from an array of IntArrays that the loop destructures as (dr, dc). One queue serves every island, and the pending cells live on the heap, so a map of any size stays off the call stack.

class Solution {
    fun numIslands(grid: Array<String>): Int {
        val cells = Array(grid.size) { grid[it].toCharArray() } // a copy to sink; grid stays as it was
        val rows = cells.size
        val cols = if (rows > 0) cells[0].size else 0
        val steps = arrayOf(intArrayOf(1, 0), intArrayOf(-1, 0), intArrayOf(0, 1), intArrayOf(0, -1))
        val queue = ArrayDeque<Int>() // r * cols + c, reused for every island
        var count = 0
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (cells[r][c] != '1') continue
                count++
                cells[r][c] = '0' // sink on enqueue so no cell is queued twice
                queue.addLast(r * cols + c)
                while (queue.isNotEmpty()) {
                    val cell = queue.removeFirst()
                    val cr = cell / cols
                    val cc = cell % cols
                    for ((dr, dc) in steps) {
                        val nr = cr + dr
                        val nc = cc + dc
                        if (nr in 0 until rows && nc in 0 until cols && cells[nr][nc] == '1') {
                            cells[nr][nc] = '0'
                            queue.addLast(nr * cols + nc)
                        }
                    }
                }
            }
        }
        return count
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

A String cannot be indexed by position, so each row becomes a byte vector with as_bytes().to_vec(), giving a mutable Vec<Vec<u8>> to sink. The scan counts each b'1' and calls sink, which takes the grid as &mut, writes b'0' and recurses into each neighbour that exists. Indices are usize, which cannot go below zero, so the bounds are checked before each call (r > 0) rather than after.

impl Solution {
    pub fn num_islands(grid: Vec<String>) -> i32 {
        // a byte copy of every row to sink; grid stays as it was
        let mut cells: Vec<Vec<u8>> = grid.iter().map(|row| row.as_bytes().to_vec()).collect();
        let mut count = 0;
        for r in 0..cells.len() {
            for c in 0..cells[r].len() {
                if cells[r][c] == b'1' {
                    count += 1;
                    Self::sink(&mut cells, r, c);
                }
            }
        }
        count
    }

    // Turns the land at (r, c) and every land cell connected to it into water.
    fn sink(cells: &mut Vec<Vec<u8>>, r: usize, c: usize) {
        if cells[r][c] != b'1' {
            return;
        }
        cells[r][c] = b'0';
        if r + 1 < cells.len() {
            Self::sink(cells, r + 1, c);
        }
        if r > 0 {
            Self::sink(cells, r - 1, c);
        }
        if c + 1 < cells[r].len() {
            Self::sink(cells, r, c + 1);
        }
        if c > 0 {
            Self::sink(cells, r, c - 1);
        }
    }
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

This version borrows each row with as_bytes() and never copies the map. Cell (r, c) is node r * cols + c in a parent: Vec<usize>, and two cells share an island exactly when they reach the same root. Each land cell adds one to the count and joins the cells above and to its left; union returns true only for a real merge, so the count drops once per merge. find loops with path halving and std::mem::swap keeps the smaller tree under the larger.

impl Solution {
    pub fn num_islands(grid: Vec<String>) -> i32 {
        let rows = grid.len();
        let cols = grid.first().map_or(0, |row| row.len());
        let mut parent: Vec<usize> = (0..rows * cols).collect(); // cell (r, c) is node r * cols + c
        let mut size = vec![1usize; rows * cols];
        let mut count = 0;
        for r in 0..rows {
            let row = grid[r].as_bytes();
            for c in 0..cols {
                if row[c] != b'1' {
                    continue;
                }
                count += 1; // every land cell starts as its own island
                let cell = r * cols + c;
                // join with the two neighbours the scan has already passed
                if r > 0 && grid[r - 1].as_bytes()[c] == b'1' && Self::union(&mut parent, &mut size, cell, cell - cols) {
                    count -= 1; // two islands became one
                }
                if c > 0 && row[c - 1] == b'1' && Self::union(&mut parent, &mut size, cell, cell - 1) {
                    count -= 1;
                }
            }
        }
        count
    }

    fn find(parent: &mut [usize], mut x: usize) -> usize {
        while parent[x] != x {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        x
    }

    // Joins the trees of a and b; returns false if they already had the same root.
    fn union(parent: &mut [usize], size: &mut [usize], a: usize, b: usize) -> bool {
        let mut ra = Self::find(parent, a);
        let mut rb = Self::find(parent, b);
        if ra == rb {
            return false;
        }
        if size[ra] < size[rb] {
            std::mem::swap(&mut ra, &mut rb);
        }
        parent[rb] = ra; // hang the smaller tree under the bigger
        size[ra] += size[rb];
        true
    }
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

The flood without recursion: a VecDeque<(usize, usize)> holds the cells still to visit and while let Some((r, c)) = queue.pop_front() drains it. A cell is sunk when it is pushed, so it is never queued twice. For the neighbour above and to the left, wrapping_sub(1) turns row or column 0 into usize::MAX, which the single nr < rows && nc < cols check rejects, so there is no subtraction that could panic.

use std::collections::VecDeque;

impl Solution {
    pub fn num_islands(grid: Vec<String>) -> i32 {
        // a byte copy of every row to sink; grid stays as it was
        let mut cells: Vec<Vec<u8>> = grid.iter().map(|row| row.as_bytes().to_vec()).collect();
        let rows = cells.len();
        let cols = cells.first().map_or(0, |row| row.len());
        let mut queue: VecDeque<(usize, usize)> = VecDeque::new(); // reused for every island
        let mut count = 0;
        for r in 0..rows {
            for c in 0..cols {
                if cells[r][c] != b'1' {
                    continue;
                }
                count += 1;
                cells[r][c] = b'0'; // sink on push so no cell is queued twice
                queue.push_back((r, c));
                while let Some((cr, cc)) = queue.pop_front() {
                    // at row or column 0, wrapping_sub gives usize::MAX, which the bounds check rejects
                    for (nr, nc) in [(cr + 1, cc), (cr.wrapping_sub(1), cc), (cr, cc + 1), (cr, cc.wrapping_sub(1))] {
                        if nr < rows && nc < cols && cells[nr][nc] == b'1' {
                            cells[nr][nc] = b'0';
                            queue.push_back((nr, nc));
                        }
                    }
                }
            }
        }
        count
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

A Swift String has no integer subscript, so grid.map { Array($0) } turns every row into a [Character] and gives a [[Character]] to sink. The scan counts each "1" and calls sink, which takes the grid as inout, returns through a guard for a cell off the map or not land, writes "0" and recurses into the four neighbours. The copy is the solver's own, so the caller's strings never change.

class Solution {
    func numIslands(_ grid: [String]) -> Int {
        var cells = grid.map { Array($0) } // [[Character]], a copy to sink; grid stays as it was
        var count = 0
        for r in 0..<cells.count {
            for c in 0..<cells[r].count {
                if cells[r][c] == "1" {
                    count += 1
                    sink(&cells, r, c)
                }
            }
        }
        return count
    }

    // Turns the land at (r, c) and every land cell connected to it into water.
    private func sink(_ cells: inout [[Character]], _ r: Int, _ c: Int) {
        guard r >= 0, r < cells.count, c >= 0, c < cells[r].count, cells[r][c] == "1" else { return }
        cells[r][c] = "0"
        sink(&cells, r + 1, c)
        sink(&cells, r - 1, c)
        sink(&cells, r, c + 1)
        sink(&cells, r, c - 1)
    }
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

Cell (r, c) becomes node r * cols + c in a parent array, and two cells share an island exactly when they reach the same root. find and union are nested functions that capture parent and size, so no array is passed around. Each land cell adds one to the count and joins the cells above and to its left; union returns true only for a real merge, so the count drops once per merge. Path halving and swap(&ra, &rb) by size keep the trees flat.

class Solution {
    func numIslands(_ grid: [String]) -> Int {
        let cells = grid.map { Array($0) } // read-only [[Character]]: String has no integer subscript
        let rows = cells.count
        let cols = rows > 0 ? cells[0].count : 0
        var parent = Array(0..<(rows * cols)) // cell (r, c) is node r * cols + c
        var size = [Int](repeating: 1, count: rows * cols)

        func find(_ start: Int) -> Int {
            var x = start
            while parent[x] != x {
                parent[x] = parent[parent[x]] // path halving
                x = parent[x]
            }
            return x
        }

        // Joins the trees of a and b; false if they already had the same root.
        func union(_ a: Int, _ b: Int) -> Bool {
            var ra = find(a)
            var rb = find(b)
            if ra == rb { return false }
            if size[ra] < size[rb] { swap(&ra, &rb) }
            parent[rb] = ra // hang the smaller tree under the bigger
            size[ra] += size[rb]
            return true
        }

        var count = 0
        for r in 0..<rows {
            for c in 0..<cols where cells[r][c] == "1" {
                count += 1 // every land cell starts as its own island
                let cell = r * cols + c
                // join with the two neighbours the scan has already passed
                if r > 0 && cells[r - 1][c] == "1" && union(cell, cell - cols) { count -= 1 }
                if c > 0 && cells[r][c - 1] == "1" && union(cell, cell - 1) { count -= 1 }
            }
        }
        return count
    }
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

The standard library has no deque, so the queue is a plain array of (Int, Int) tuples read through a head index: append adds at the back and head += 1 takes from the front in O(1), where removeFirst() would shift the whole array. A cell is sunk when it is appended, so it is never queued twice, and removeAll(keepingCapacity: true) reuses the storage for the next island.

class Solution {
    func numIslands(_ grid: [String]) -> Int {
        var cells = grid.map { Array($0) } // [[Character]], a copy to sink; grid stays as it was
        let rows = cells.count
        let cols = rows > 0 ? cells[0].count : 0
        let steps = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        var queue: [(Int, Int)] = []
        var count = 0
        for r in 0..<rows {
            for c in 0..<cols where cells[r][c] == "1" {
                count += 1
                cells[r][c] = "0" // sink on append so no cell is queued twice
                queue.removeAll(keepingCapacity: true)
                queue.append((r, c))
                var head = 0
                while head < queue.count {
                    let (cr, cc) = queue[head]
                    head += 1
                    for (dr, dc) in steps {
                        let nr = cr + dr
                        let nc = cc + dc
                        if nr >= 0 && nr < rows && nc >= 0 && nc < cols && cells[nr][nc] == "1" {
                            cells[nr][nc] = "0"
                            queue.append((nr, nc))
                        }
                    }
                }
            }
        }
        return count
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

array_map('str_split', $grid) turns every row into an array of one-character strings, a grid of the solver's own to sink. The scan counts each '1' and calls $this->sink, which takes the grid by reference (array &$cells), writes '0' and recurses into the four neighbours. A neighbour off the map is simply a missing key, so $cells[$r][$c] ?? '0' reads it as water without a bounds check or a warning.

<?php

class Solution {
    /**
     * @param string[] $grid
     * @return int
     */
    function numIslands(array $grid): int {
        $cells = array_map('str_split', $grid); // one-character strings, a copy to sink
        $count = 0;
        $rows = count($cells);
        for ($r = 0; $r < $rows; $r++) {
            $cols = count($cells[$r]);
            for ($c = 0; $c < $cols; $c++) {
                if ($cells[$r][$c] === '1') {
                    $count++;
                    $this->sink($cells, $r, $c);
                }
            }
        }
        return $count;
    }

    // Turns the land at ($r, $c) and every land cell connected to it into water.
    private function sink(array &$cells, int $r, int $c): void {
        if (($cells[$r][$c] ?? '0') !== '1') {
            return; // off the map or not land
        }
        $cells[$r][$c] = '0';
        $this->sink($cells, $r + 1, $c);
        $this->sink($cells, $r - 1, $c);
        $this->sink($cells, $r, $c + 1);
        $this->sink($cells, $r, $c - 1);
    }
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

This version reads the rows with string offsets ($grid[$r][$c]) and writes only to two integer arrays. Cell ($r, $c) is node $r * $cols + $c; $parent links each node toward the root of its island. Each land cell adds one to the count and joins the cells above and to its left; union returns true only for a real merge, so the count drops once per merge. Both arrays go to the helpers by reference, so PHP's copy-on-write never duplicates them.

<?php

class Solution {
    /**
     * @param string[] $grid
     * @return int
     */
    function numIslands(array $grid): int {
        $rows = count($grid);
        $cols = $rows > 0 ? strlen($grid[0]) : 0;
        // cell ($r, $c) is node $r * $cols + $c; one spare node keeps range() valid for an empty map
        $parent = range(0, $rows * $cols);
        $size = array_fill(0, $rows * $cols + 1, 1);
        $count = 0;
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($grid[$r][$c] !== '1') {
                    continue;
                }
                $count++; // every land cell starts as its own island
                $cell = $r * $cols + $c;
                // join with the two neighbours the scan has already passed
                if ($r > 0 && $grid[$r - 1][$c] === '1' && $this->union($parent, $size, $cell, $cell - $cols)) {
                    $count--; // two islands became one
                }
                if ($c > 0 && $grid[$r][$c - 1] === '1' && $this->union($parent, $size, $cell, $cell - 1)) {
                    $count--;
                }
            }
        }
        return $count;
    }

    private function find(array &$parent, int $x): int {
        while ($parent[$x] !== $x) {
            $parent[$x] = $parent[$parent[$x]]; // path halving
            $x = $parent[$x];
        }
        return $x;
    }

    // Joins the trees of $a and $b; returns false if they already had the same root.
    private function union(array &$parent, array &$size, int $a, int $b): bool {
        $ra = $this->find($parent, $a);
        $rb = $this->find($parent, $b);
        if ($ra === $rb) {
            return false;
        }
        if ($size[$ra] < $size[$rb]) {
            [$ra, $rb] = [$rb, $ra];
        }
        $parent[$rb] = $ra; // hang the smaller tree under the bigger
        $size[$ra] += $size[$rb];
        return true;
    }
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

The flood without recursion: an SplQueue holds [$r, $c] pairs still to visit, with enqueue at the back and dequeue at the front, both O(1). A cell is sunk when it is enqueued, so it is never queued twice. array_shift on a plain array would renumber every key on each call and turn the search quadratic.

<?php

class Solution {
    /**
     * @param string[] $grid
     * @return int
     */
    function numIslands(array $grid): int {
        $cells = array_map('str_split', $grid); // one-character strings, a copy to sink
        $rows = count($cells);
        $cols = $rows > 0 ? count($cells[0]) : 0;
        $steps = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        $queue = new SplQueue(); // reused for every island
        $count = 0;
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($cells[$r][$c] !== '1') {
                    continue;
                }
                $count++;
                $cells[$r][$c] = '0'; // sink on enqueue so no cell is queued twice
                $queue->enqueue([$r, $c]);
                while (!$queue->isEmpty()) {
                    [$cr, $cc] = $queue->dequeue();
                    foreach ($steps as [$dr, $dc]) {
                        $nr = $cr + $dr;
                        $nc = $cc + $dc;
                        if ($nr >= 0 && $nr < $rows && $nc >= 0 && $nc < $cols && $cells[$nr][$nc] === '1') {
                            $cells[$nr][$nc] = '0';
                            $queue->enqueue([$nr, $nc]);
                        }
                    }
                }
            }
        }
        return $count;
    }
}

3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

grid.map(&:chars) turns every row into an array of one-character strings, a grid of the solver's own to sink. The scan counts each '1' and calls sink, which returns for a cell off the map or not land, writes '0' and recurses into the four neighbours. The bounds check matters more than usual: Ruby reads cells[-1] as the last row instead of failing, so a negative index has to be rejected explicitly.

# @param {String[]} grid
# @return {Integer}
def num_islands(grid)
  cells = grid.map(&:chars) # one-character strings, a copy to sink
  count = 0
  cells.each_index do |r|
    cells[r].each_index do |c|
      next unless cells[r][c] == '1'

      count += 1
      sink(cells, r, c)
    end
  end
  count
end

# Turns the land at (r, c) and every land cell connected to it into water.
def sink(cells, r, c)
  return if r.negative? || c.negative? || r >= cells.length || c >= cells[r].length
  return unless cells[r][c] == '1'

  cells[r][c] = '0'
  sink(cells, r + 1, c)
  sink(cells, r - 1, c)
  sink(cells, r, c + 1)
  sink(cells, r, c - 1)
end

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

This version only reads grid. Cell (r, c) is node r * cols + c in a parent array built with Array.new(n) { |i| i }, and two cells share an island exactly when they reach the same root. Each land cell adds one to the count and joins the cells above and to its left; unite returns true only for a real merge, so the count drops once per merge. find_root loops with path halving and the smaller tree goes under the larger, so nothing recurses.

# @param {String[]} grid
# @return {Integer}
def num_islands(grid)
  rows = grid.length
  cols = rows.positive? ? grid[0].length : 0
  parent = Array.new(rows * cols) { |i| i } # cell (r, c) is node r * cols + c
  size = Array.new(rows * cols, 1)
  count = 0
  rows.times do |r|
    cols.times do |c|
      next unless grid[r][c] == '1'

      count += 1 # every land cell starts as its own island
      cell = r * cols + c
      # join with the two neighbours the scan has already passed
      count -= 1 if r.positive? && grid[r - 1][c] == '1' && unite(parent, size, cell, cell - cols)
      count -= 1 if c.positive? && grid[r][c - 1] == '1' && unite(parent, size, cell, cell - 1)
    end
  end
  count
end

def find_root(parent, x)
  while parent[x] != x
    parent[x] = parent[parent[x]] # path halving
    x = parent[x]
  end
  x
end

# Joins the trees of a and b; returns false if they already had the same root.
def unite(parent, size, a, b)
  ra = find_root(parent, a)
  rb = find_root(parent, b)
  return false if ra == rb

  ra, rb = rb, ra if size[ra] < size[rb]
  parent[rb] = ra # hang the smaller tree under the bigger
  size[ra] += size[rb]
  true
end

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

The flood without recursion: an Array serves as the queue, with push at the back and shift at the front. A cell is sunk when it is pushed, so it is never queued twice. Multiple assignment unpacks each [r, c] pair, and STEPS.each do |dr, dc| splats the offsets the same way.

STEPS = [[1, 0], [-1, 0], [0, 1], [0, -1]].freeze

# @param {String[]} grid
# @return {Integer}
def num_islands(grid)
  cells = grid.map(&:chars) # one-character strings, a copy to sink
  rows = cells.length
  cols = rows.positive? ? cells[0].length : 0
  count = 0
  rows.times do |r|
    cols.times do |c|
      next unless cells[r][c] == '1'

      count += 1
      cells[r][c] = '0' # sink on push so no cell is queued twice
      queue = [[r, c]]
      until queue.empty?
        cr, cc = queue.shift
        STEPS.each do |dr, dc|
          nr = cr + dr
          nc = cc + dc
          next unless nr.between?(0, rows - 1) && nc.between?(0, cols - 1) && cells[nr][nc] == '1'

          cells[nr][nc] = '0'
          queue.push([nr, nc])
        end
      end
    end
  end
  count
end

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Dart strings are immutable, so a collection-for, [for (final row in grid) row.split('')], builds a List<List<String>> of one-character strings to sink. The scan counts each '1' and calls the private _sink, which returns for a cell off the map or not land, writes '0' and recurses into the four neighbours. When the first call returns, the whole island is water and the scan cannot count it again.

class Solution {
  int numIslands(List<String> grid) {
    // one-character strings, a copy to sink; grid stays as it was
    final cells = [for (final row in grid) row.split('')];
    var count = 0;
    for (var r = 0; r < cells.length; r++) {
      for (var c = 0; c < cells[r].length; c++) {
        if (cells[r][c] == '1') {
          count++;
          _sink(cells, r, c);
        }
      }
    }
    return count;
  }

  // Turns the land at (r, c) and every land cell connected to it into water.
  void _sink(List<List<String>> cells, int r, int c) {
    if (r < 0 || r >= cells.length || c < 0 || c >= cells[r].length || cells[r][c] != '1') return;
    cells[r][c] = '0';
    _sink(cells, r + 1, c);
    _sink(cells, r - 1, c);
    _sink(cells, r, c + 1);
    _sink(cells, r, c - 1);
  }
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

This version only reads grid (grid[r][c] returns a one-character string) and keeps its state in two lists. Cell (r, c) is node r * cols + c in List<int>.generate(n, (i) => i), and two cells share an island exactly when they reach the same root. Each land cell adds one to the count and joins the cells above and to its left; _union returns true only for a real merge, so the count drops once per merge. Path halving and union by size keep every _find short.

class Solution {
  int numIslands(List<String> grid) {
    final rows = grid.length;
    final cols = rows > 0 ? grid[0].length : 0;
    final parent = List<int>.generate(rows * cols, (i) => i); // cell (r, c) is node r * cols + c
    final size = List<int>.filled(rows * cols, 1);
    var count = 0;
    for (var r = 0; r < rows; r++) {
      for (var c = 0; c < cols; c++) {
        if (grid[r][c] != '1') continue;
        count++; // every land cell starts as its own island
        final cell = r * cols + c;
        // join with the two neighbours the scan has already passed
        if (r > 0 && grid[r - 1][c] == '1' && _union(parent, size, cell, cell - cols)) count--;
        if (c > 0 && grid[r][c - 1] == '1' && _union(parent, size, cell, cell - 1)) count--;
      }
    }
    return count;
  }

  int _find(List<int> parent, int x) {
    while (parent[x] != x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  }

  // Joins the trees of a and b; returns false if they already had the same root.
  bool _union(List<int> parent, List<int> size, int a, int b) {
    var ra = _find(parent, a);
    var rb = _find(parent, b);
    if (ra == rb) return false;
    if (size[ra] < size[rb]) (ra, rb) = (rb, ra);
    parent[rb] = ra; // hang the smaller tree under the bigger
    size[ra] += size[rb];
    return true;
  }
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

The flood without recursion: a Queue<(int, int)> from dart:collection holds record pairs, with add at the back and removeFirst at the front, both O(1). A cell is sunk when it is added, so it is never queued twice. Dart 3 patterns unpack each record directly, final (cr, cc) = queue.removeFirst(), and the same goes for the offsets in for (final (dr, dc) in _steps).

import 'dart:collection';

class Solution {
  static const _steps = [(1, 0), (-1, 0), (0, 1), (0, -1)];

  int numIslands(List<String> grid) {
    // one-character strings, a copy to sink; grid stays as it was
    final cells = [for (final row in grid) row.split('')];
    final rows = cells.length;
    final cols = rows > 0 ? cells[0].length : 0;
    final queue = Queue<(int, int)>(); // reused for every island
    var count = 0;
    for (var r = 0; r < rows; r++) {
      for (var c = 0; c < cols; c++) {
        if (cells[r][c] != '1') continue;
        count++;
        cells[r][c] = '0'; // sink on add so no cell is queued twice
        queue.add((r, c));
        while (queue.isNotEmpty) {
          final (cr, cc) = queue.removeFirst();
          for (final (dr, dc) in _steps) {
            final nr = cr + dr;
            final nc = cc + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && cells[nr][nc] == '1') {
              cells[nr][nc] = '0';
              queue.add((nr, nc));
            }
          }
        }
      }
    }
    return count;
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Recursive DFS: sink each island you find

O(m·n) time · O(m·n) call stack space

Scala strings are Java strings and cannot change, so grid.map(_.toCharArray) builds an Array[Array[Char]] to sink. The scan counts each '1' and calls sink, which does nothing for a cell off the map or not land and otherwise writes '0' and recurses into the four neighbours. The guard is an if around the body rather than an early return, so the method stays a single expression of type Unit.

object Solution {
  def numIslands(grid: Array[String]): Int = {
    val cells = grid.map(_.toCharArray) // a copy to sink; grid stays as it was
    var count = 0
    for (r <- cells.indices; c <- cells(r).indices) {
      if (cells(r)(c) == '1') {
        count += 1
        sink(cells, r, c)
      }
    }
    count
  }

  // Turns the land at (r, c) and every land cell connected to it into water.
  private def sink(cells: Array[Array[Char]], r: Int, c: Int): Unit = {
    if (r >= 0 && r < cells.length && c >= 0 && c < cells(r).length && cells(r)(c) == '1') {
      cells(r)(c) = '0'
      sink(cells, r + 1, c)
      sink(cells, r - 1, c)
      sink(cells, r, c + 1)
      sink(cells, r, c - 1)
    }
  }
}

2 · Union-find: merge neighbouring land cells

O(m·n) time · O(m·n) space

This version only reads grid(r)(c), which is charAt on the row. Cell (r, c) is node r * cols + c in Array.tabulate(n)(identity), and two cells share an island exactly when they reach the same root. Each land cell adds one to the count and joins the cells above and to its left; union returns true only for a real merge, so the count drops once per merge. find is a while loop with path halving, so nothing recurses and no non-local return is needed.

object Solution {
  def numIslands(grid: Array[String]): Int = {
    val rows = grid.length
    val cols = if (rows > 0) grid(0).length else 0
    val parent = Array.tabulate(rows * cols)(identity) // cell (r, c) is node r * cols + c
    val size = Array.fill(rows * cols)(1)

    def find(start: Int): Int = {
      var x = start
      while (parent(x) != x) {
        parent(x) = parent(parent(x)) // path halving
        x = parent(x)
      }
      x
    }

    // Joins the trees of a and b; false if they already had the same root.
    def union(a: Int, b: Int): Boolean = {
      val ra = find(a)
      val rb = find(b)
      if (ra == rb) false
      else {
        val (big, small) = if (size(ra) >= size(rb)) (ra, rb) else (rb, ra)
        parent(small) = big // hang the smaller tree under the bigger
        size(big) += size(small)
        true
      }
    }

    var count = 0
    for (r <- 0 until rows; c <- 0 until cols if grid(r)(c) == '1') {
      count += 1 // every land cell starts as its own island
      val cell = r * cols + c
      // join with the two neighbours the scan has already passed
      if (r > 0 && grid(r - 1)(c) == '1' && union(cell, cell - cols)) count -= 1
      if (c > 0 && grid(r)(c - 1) == '1' && union(cell, cell - 1)) count -= 1
    }
    count
  }
}

3 · Iterative BFS with a queue

O(m·n) time · O(m·n), queue small space

recommended

The flood without recursion: a mutable.Queue[(Int, Int)] holds the cells still to visit, with enqueue at the back and dequeue at the front. A cell is sunk when it is enqueued, so it is never queued twice. The tuple patterns val (cr, cc) = queue.dequeue() and for ((dr, dc) <- Steps) unpack the pairs, and the pending cells live on the heap instead of the call stack.

import scala.collection.mutable

object Solution {
  private val Steps = Array((1, 0), (-1, 0), (0, 1), (0, -1))

  def numIslands(grid: Array[String]): Int = {
    val cells = grid.map(_.toCharArray) // a copy to sink; grid stays as it was
    val rows = cells.length
    val cols = if (rows > 0) cells(0).length else 0
    val queue = mutable.Queue.empty[(Int, Int)] // reused for every island
    var count = 0
    for (r <- 0 until rows; c <- 0 until cols if cells(r)(c) == '1') {
      count += 1
      cells(r)(c) = '0' // sink on enqueue so no cell is queued twice
      queue.enqueue((r, c))
      while (queue.nonEmpty) {
        val (cr, cc) = queue.dequeue()
        for ((dr, dc) <- Steps) {
          val nr = cr + dr
          val nc = cc + dc
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && cells(nr)(nc) == '1') {
            cells(nr)(nc) = '0'
            queue.enqueue((nr, nc))
          }
        }
      }
    }
    count
  }
}

FAQ for JavaScript

Why does my solution return 0 when the grid holds numbers?

Strict equality never converts types, so 1 === '1' is false and every cell looks like water. Passing [[1, 1, 0, 0, 0], [1, 1, 0, 1, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0]] to the BFS above gives 0. Either compare with 1 and write 0 when sinking, or convert the rows first with grid.map((row) => row.join('')), after which the same map gives 2. Avoid switching to == just to make it pass; fix the data type instead.

Why not use queue.shift() for the BFS?

The specification defines shift() as moving every later element down by one index, which is O(length) per call. V8 can sometimes avoid that copy, but you cannot count on it for large arrays. A head index that only moves forward gives a guaranteed O(1) dequeue, and the array is thrown away once the island is done.

How large an island can the recursive DFS handle in Node?

On the engine behind this page, the sink function above survives somewhere between 8,000 and 9,000 nested calls: a single row of 8,000 land cells works and one of 9,000 throws RangeError: Maximum call stack size exceeded, as does a solid 100 x 100 block. The limit depends on frame size and on the stack size Node was started with, so treat any figure as approximate and switch to the BFS or to an explicit stack array when input size is not under your control.

What changes if diagonal neighbours also join islands?

Add the four corner moves [1, 1], [1, -1], [-1, 1] and [-1, -1] to the steps array in the BFS. Nothing else needs to change, and ['101', '010', '101'] then gives 1 instead of 5, because every corner cell touches the centre.

How do I get the size of the biggest island instead of the count?

In the BFS, queue.length after the inner loop finishes is exactly the number of cells in that island, since every cell is pushed once and never removed. Collect those lengths and take Math.max(0, ...sizes); for ['11000', '11010', '00011', '00000'] the sizes are [ 4, 3 ] and the answer is 4. Keep the 0 in the call: Math.max() with no arguments returns -Infinity for a map with no land.

FAQ for Java

Can I keep the recursive DFS by giving it more stack?

Partly. Run it on your own thread through the four-argument constructor, new Thread(null, task, "dfs", 64L << 20), which requests a 64 MB stack; on this site's engine a 200 x 200 grid then returns 1 instead of failing. Raising -Xss does the same for every thread. Neither is a real fix: the Thread documentation allows the JVM to ignore the requested size, and a larger map breaks again. Catching StackOverflowError is no fix either, because it is an Error thrown mid-flood with the grid half sunk. The BFS, or a DFS that uses push and pop on its own ArrayDeque, has no depth to run out of.

Why use ArrayDeque here instead of LinkedList or Stack?

ArrayDeque keeps its elements in a growable circular array, so add and poll are amortised O(1) without the extra node object a LinkedList creates per entry, and its own documentation says it is likely faster than LinkedList as a queue. Stack is a legacy subclass of the synchronized Vector and pops from the top, which would turn the search depth-first. The one gotcha is that ArrayDeque throws on null elements, which cannot happen when every element is a fresh int[].

How do I make diagonal neighbours count as connected?

Give STEPS four more rows, {1, 1}, {1, -1}, {-1, 1} and {-1, -1}; the loop and its bounds check need no other change. Corner contact then joins cells, so {"101", "010", "101"} collapses from 5 islands into 1, while {"11000", "11010", "00011", "00000"} still has 2.

How do I get the area of the largest island?

Keep an int size per island: set it to 0 before the while loop, increment it after every poll, and once the deque is empty update best = Math.max(best, size). Each cell of an island is polled exactly once, so size ends up as its area. The first example gives 4, since its islands have 4 and 3 cells; a 200 x 200 all-land grid gives 40000, and an empty array leaves best at 0.

What changes if the grid is an int[][] instead of a String[]?

Test for 1 instead of '1' and sink by writing 0. toCharArray() exists only on String, so copy each row with grid[r].clone(), which for an int[] copies all the values. Do not stop at grid.clone(): that duplicates only the outer array, the rows inside are still the caller's, and sinking would erase their map. The four-row example as an int[][] still returns 2, and Arrays.toString(grid[0]) prints [1, 1, 0, 0, 0] afterwards.

FAQ for Go

Will a deep recursive sink crash a Go program?

Not at the sizes on this page. The runtime enlarges each goroutine stack as needed, so a 200 x 200 all-land grid recurses 40,000 calls deep and returns 1. The limit is a per-goroutine maximum, 1 GB by default on 64-bit systems, and debug.SetMaxStack(1 << 20) from runtime/debug lowers it: the same grid then aborts with runtime: goroutine stack exceeds 1048576-byte limit followed by fatal error: stack overflow. That is a fatal error, not a panic, so a deferred recover will not save it. The two-slice BFS never depends on that limit.

Why does the BFS swap two slices instead of popping from the front of one?

Go has no built-in queue type. A single slice popped with q = q[1:] also works, but the space before the new start is never written again, so the slice has to reallocate as it slides forward. Keeping frontier and next apart, truncating with [:0] and swapping with frontier, next = next, frontier recycles two backing arrays for every ring and every island, and it keeps each BFS level separate, which helps if you later want the distance from the starting cell. container/list is another option, but it allocates an element per push and stores values as any.

How do I treat diagonal neighbours as connected too?

Grow the neighbour literal in the BFS from four [2]int entries to eight by adding {p[0] + 1, p[1] + 1}, {p[0] + 1, p[1] - 1}, {p[0] - 1, p[1] + 1} and {p[0] - 1, p[1] - 1}. The bounds check already covers the new offsets. Under that rule the corners and centre of []string{"101", "010", "101"} all link up, so the answer drops from 5 to 1.

How would I return the area of the biggest island instead of the count?

Keep a size that starts at 1 when the scan sinks the first byte of an island and grows by one for every append onto next. When the inner for len(frontier) > 0 loop ends, update best = max(best, size) with the built-in max (Go 1.21 and later). The first example has islands of 4 and 3 cells, so it gives 4, and a 200 x 200 block gives 40000.

What changes if the grid arrives as a [][]int?

Compare against 1 rather than the byte '1', and sink by storing 0. The copy step changes too: []byte(row) only converts strings, so clone each inner slice with slices.Clone(row). Writing cells[r] = row instead would share the caller's backing array, and sinking would wipe their map. With [][]int{{1, 1, 0, 0, 0}, {1, 1, 0, 1, 0}, {0, 0, 0, 1, 1}, {0, 0, 0, 0, 0}} the count is still 2 and the input rows come back unchanged.

FAQ for C#

Can I give the recursive DFS a bigger stack instead of rewriting it?

Yes, up to a point. new Thread(() => Run(grid), 64 * 1024 * 1024).Start() asks for a 64 MB stack for that thread, which carries a far deeper flood than the default; Join it to get the result back. It only moves the limit, though: a bigger map overflows again, and a StackOverflowException cannot be caught in .NET, it ends the process with the grid half sunk. The BFS, or a DFS that pushes and pops on its own Stack<(int, int)>, has no depth to run out of.

Why Queue<(int, int)> rather than Queue<int[]>?

A value tuple is a struct, so queue.Enqueue((r, c)) stores two ints inline in the queue's array with no allocation, while new int[] { r, c } allocates one small array per cell and leaves the garbage collector to clear up thousands of them on a big map. Deconstruction with var (cr, cc) = queue.Dequeue() reads just like the array version.

How do I count islands without copying the grid?

Track visited cells on the side. A bool[,] seen = new bool[rows, cols] is the cheapest: test !seen[nr, nc] next to the == '1' check and set it when you enqueue. A HashSet<(int, int)> does the same with Add returning false for a repeat, at the price of hashing. The union-find version above never copies anything, since it only reads the rows through the string indexer.

How do I make diagonal neighbours count as connected?

Add four more entries to Steps: (1, 1), (1, -1), (-1, 1) and (-1, -1). The loop and its bounds check need no change. Corner contact then joins cells, so new[] { "101", "010", "101" } collapses from 5 islands into 1, while the first example still has 2.

How do I get the area of the largest island?

Keep an int area per island: set it to 0 before the while loop, increment it after every Dequeue, and once the queue is empty do best = Math.Max(best, area). Each cell is dequeued exactly once, so area ends up as the island's cell count. The first example gives 4, its islands having 4 and 3 cells, and an empty array leaves best at 0.

FAQ for Kotlin

Why copy the rows with toCharArray() instead of changing grid?

A Kotlin String cannot be changed in place: grid[r][c] = '0' does not compile, since String has a get operator but no set. toCharArray() returns a fresh CharArray per row, so sinking it leaves the caller's array exactly as it was. The union-find version needs no copy at all because it only reads grid[r][c].

Is ArrayDeque here java.util.ArrayDeque?

No. Without an import, ArrayDeque resolves to kotlin.collections.ArrayDeque, the standard library's own resizable circular buffer, with addLast, removeFirst and isNotEmpty(). java.util.ArrayDeque works the same way with add and poll. Both are amortised O(1) at each end; MutableList.removeAt(0) would shift every element instead.

Can the recursive sink overflow the stack?

Each land cell of an island adds one frame, so the depth is the island's size. The cases here stay within a 60 x 60 map and the deepest flood is 625 frames, which the default JVM stack takes easily. On a solid map of tens of thousands of cells the recursion can throw StackOverflowError; the BFS or union-find version has no depth to run out of.

What does ra = rb.also { rb = ra } do?

It swaps two vars in one line. also evaluates rb as the result, runs the block (which sets rb to the old ra), and then the assignment stores the old rb in ra. A val t = ra; ra = rb; rb = t is the longer equivalent.

How do I make diagonal neighbours count as connected?

Add intArrayOf(1, 1), intArrayOf(1, -1), intArrayOf(-1, 1) and intArrayOf(-1, -1) to steps; the loop needs no other change. Corner contact then joins cells, so arrayOf("101", "010", "101") becomes 1 island instead of 5.

Keep going

Kth Largest Element in an Array25 / 40 · Heap · Medium

num_islands.kt

Kotlin 2.4

Not run yet

+ 8 hidden

Input

grid = ["11000", "11010", "00011", "00000"]

Expected

The 2 x 2 block in the top left is one island; the three cells on the right, joined top to bottom and then left to right, are the other.