SyntaxPilot
Courses/DSA and Coding Problems/Lesson 48
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 48 of 90

Number of islands

queued

These are the notes for DSA episode 48. A map is split into squares of land ('1') and water ('0'), and you must count the islands: groups of land squares that touch each other. Last episode we stored graphs and explored them with BFS and DFS; today the graph is hiding inside a grid. We start from a real-life problem (relief boats after monsoon floods), define every grid word, try two obvious ideas (a corner trick that gives a wrong answer on a U-shaped island, and label spreading that is correct but hits Time Limit Exceeded on a long snake-shaped island), find the key insight (the grid is a graph; sink each island as you find it), watch a recursive DFS crash with a real StackOverflowError, and finish with BFS flood fill in O(rows × cols). Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

After heavy monsoon floods, villages get cut off by water. A satellite takes a photo of the area, and the computer splits it into small squares. Each square is marked 1 for dry land or 0 for water. The relief team sends one boat to each separate island of dry land. How many boats do they need? That is: how many islands are there?

On the flood map In code
The satellite photo, cut into squares a grid: char[][] grid
One square of the photo a cell grid[r][c]
Dry land / water '1' / '0'
Walking to the next square of land moving to a 4-directional neighbour
One piece of dry land, water all around an island (a connected component)
One relief boat per island count++ once per island
Marking an island as "boat already sent" sinking it: turning its cells into '0'

Every word, from zero

  • Grid: a table of rows and columns. In Java it is a 2-D array, here char[][].
  • Cell (r, c): the square in row r, column c, both counted from 0. (0, 0) is the top-left corner.
  • char: one character, like '1'. Underneath it is a number (its character code): '1' is 49, '0' is 48.
  • 4-directional neighbours: the cells up (r-1, c), down (r+1, c), left (r, c-1) and right (r, c+1). Diagonals do not count in this problem.
  • Connected: two land cells are connected if you can walk from one to the other over land, one neighbour step at a time.
  • Island: a group of land cells that are all connected to each other, with water or the edge of the map all around.
  • Graph, vertex, edge: from episode 47. A vertex is a point (a station); an edge joins two vertices.
  • Connected component: a largest group of vertices where every vertex can reach every other one. One DFS or BFS from a vertex visits exactly its component.
  • Flood fill: start at one cell and spread to every connected cell of the same kind, changing them as you go (like the paint-bucket tool in a drawing app).
  • DFS (depth-first search): go as deep as possible along one path before trying another; here written with recursion (a method calling itself).
  • BFS (breadth-first search): visit cells in waves, nearest first, using a queue (first in, first out).
  • Call stack: the memory where Java keeps one frame for every method call that has not returned yet. It is small; too many nested calls cause a StackOverflowError.
  • Heap: the big memory area where objects such as an ArrayDeque live.
  • ArrayDeque: Java's fast queue/stack class; add puts at the back, poll takes from the front.

Problem statement

Number of Islands (LeetCode 200, Medium). Given an m × n grid grid of '1' (land) and '0' (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Example 1:

1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0

Output: 1 (all the land is one big island).

Example 2:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: 3: a 2 × 2 block, a single cell in the middle, and two cells at the bottom right.

Constraints: 1 ≤ m, n ≤ 300; every grid[i][j] is '0' or '1'.

All programs below use the same small helper that turns strings into a char[][]:

    static char[][] grid(String... rows) {
        char[][] g = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].toCharArray();
        return g;
    }

Obvious idea 1: count the top-left corners

A square block of land has exactly one top-left cell: water (or the edge) above it, and water to its left. So count the land cells with water above and to the left. One pass, no extra memory. Too good to be true?

import java.util.*;

public class Main {
    static char[][] grid(String... rows) {
        char[][] g = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].toCharArray();
        return g;
    }
    static int numIslands(char[][] g) {
        int count = 0;
        for (int r = 0; r < g.length; r++)
            for (int c = 0; c < g[0].length; c++) {
                if (g[r][c] != '1') continue;
                boolean upWater = r == 0 || g[r - 1][c] == '0';
                boolean leftWater = c == 0 || g[r][c - 1] == '0';
                if (upWater && leftWater) count++;
            }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(numIslands(grid("11110", "11010", "11000", "00000")));
        System.out.println(numIslands(grid("11000", "11000", "00100", "00011")));
        System.out.println(numIslands(grid("101", "101", "111")));
    }
}

Real output:

1
3
2

The two LeetCode examples give 1 and 3, both right. But the U-shaped island

1 0 1
1 0 1
1 1 1

is clearly one island, and the trick says 2. Both arms have a top cell with water above and to the left. The arms meet at the bottom, three rows away. Whether two cells belong to the same island can depend on cells far away, so looking only at neighbours cannot decide it.

Obvious idea 2: spread labels until nothing changes

This idea cannot be fooled:

  1. Give every land cell its own number, a label (r * C + c + 1).
  2. Every land cell looks at its land neighbours and takes the smallest label it sees.
  3. Repeat whole passes over the grid until no label changes.
  4. Each island now carries one label: count the different labels with a HashSet.
import java.util.*;

public class Main {
    static char[][] grid(String... rows) {
        char[][] g = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].toCharArray();
        return g;
    }
    static int numIslands(char[][] g) {
        int R = g.length, C = g[0].length;
        int[][] id = new int[R][C];
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) id[r][c] = g[r][c] == '1' ? r * C + c + 1 : 0;
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int r = 0; r < R; r++)
                for (int c = 0; c < C; c++) {
                    if (id[r][c] == 0) continue;
                    for (int[] k : d) {
                        int y = r + k[0], x = c + k[1];
                        if (y >= 0 && x >= 0 && y < R && x < C && id[y][x] != 0 && id[y][x] < id[r][c]) {
                            id[r][c] = id[y][x]; changed = true;
                        }
                    }
                }
        }
        Set<Integer> labels = new HashSet<>();
        for (int[] row : id) for (int v : row) if (v != 0) labels.add(v);
        return labels.size();
    }
    public static void main(String[] args) {
        System.out.println(numIslands(grid("11110", "11010", "11000", "00000")));
        System.out.println(numIslands(grid("11000", "11000", "00100", "00011")));
        System.out.println(numIslands(grid("101", "101", "111")));
    }
}

Real output:

1
3
1

Correct, including 1 for the U.

A 400 × 400 snake: Time Limit Exceeded

Now a long, snake-shaped island: full rows of land on every even row, joined at alternating ends (right end, then left end, and so on). It is one island of about 80,000 cells. The main of the program becomes:

        int n = 400;
        char[][] g = new char[n][n];
        for (int r = 0; r < n; r++) {
            Arrays.fill(g[r], '0');
            if (r % 2 == 0) Arrays.fill(g[r], '1');
            else g[r][(r / 2) % 2 == 0 ? n - 1 : 0] = '1';
        }
        long t0 = System.nanoTime();
        int k = numIslands(g);
        System.out.println(k + " island, " + (System.nanoTime() - t0) / 1000000 + " ms");

In the SyntaxPilot compiler: Time Limit Exceeded (no output; stopped after 8 s. On our machine timeout 10 stopped it after 10 s too).

Why it is slow

  • On the rows where the snake runs right to left, the smallest label has to travel against our scan (we scan left to right), and it moves only one cell per pass.
  • The snake is about 80,000 cells long, so we need tens of thousands of passes, and each pass looks at all 400 × 400 = 1,60,000 cells (1.6 lakh).
  • That is O((rows × cols)²) in the worst case: about a thousand crore (10^10) steps.
  • Better: the moment we find land, take the whole island in one go.

The key insight: the grid is a graph, so flood fill it

On the map In episode 47's words
A land cell a vertex
Two land cells touching up/down/left/right an edge (at most 4 per cell)
An island a connected component

We never build an adjacency list: the four neighbours of (r, c) are right there in the grid. And one DFS or BFS from a land cell visits exactly its island.

Flood fill, step by step on example 2:

  1. Scan the grid row by row.
  2. At (0, 0) we find land: a new island, count = 1.
  3. From that cell, visit its whole island and turn every cell into water: sink it. The scan can never count those cells again.
  4. The scan goes on. The next land is (2, 2): count = 2, sink it.
  5. Then (3, 3): count = 3, sink it together with (3, 4). Answer: 3.

Every cell is touched only a few times: once by the scan, and up to four times as somebody's neighbour.

Flood fill with recursive DFS

import java.util.*;

public class Main {
    static char[][] grid(String... rows) {
        char[][] g = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].toCharArray();
        return g;
    }
    static int numIslands(char[][] g) {
        int count = 0;
        for (int r = 0; r < g.length; r++)
            for (int c = 0; c < g[0].length; c++)
                if (g[r][c] == '1') { count++; sink(g, r, c); }
        return count;
    }
    static void sink(char[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
        g[r][c] = '0';
        sink(g, r + 1, c); sink(g, r - 1, c);
        sink(g, r, c + 1); sink(g, r, c - 1);
    }
    public static void main(String[] args) {
        System.out.println(numIslands(grid("11110", "11010", "11000", "00000")));
        System.out.println(numIslands(grid("11000", "11000", "00100", "00011")));
        System.out.println(numIslands(grid("101", "101", "111")));
    }
}

sink returns if the cell is off the grid or is not land. Otherwise it makes the cell water first (so we never come back to it) and then sinks all four neighbours. Real output:

1
3
1

Correct, short and clean.

The snake: a real StackOverflowError

The same DFS with the snake main from above. Real output (first lines):

Exception in thread "main" java.lang.StackOverflowError
    at Main.sink(Main.java:19)
    at Main.sink(Main.java:20)

The snake is 80,000 cells long, and every step along it is one more nested call to sink, waiting for the next one to return. The call stack runs out. It is the same problem as last episode's lakh-long line.

The optimal solution in Java: flood fill with BFS

The fix: no recursion, use a queue.

  1. Found land: count++, make it water, put it in the queue.
  2. Take a cell from the queue; check its 4 neighbours.
  3. Every land neighbour becomes water right away and joins the queue. Sinking it when it joins means it can never be added twice.
  4. The four directions go in a small array of row and column steps: down, up, right, left.
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

The queue is an ordinary object on the heap, which has plenty of room, unlike the call stack.

import java.util.*;

public class Main {
    static char[][] grid(String... rows) {
        char[][] g = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].toCharArray();
        return g;
    }
    static int numIslands(char[][] g) {
        int R = g.length, C = g[0].length, count = 0;
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                if (g[r][c] != '1') continue;
                count++;
                g[r][c] = '0'; q.add(new int[]{r, c});
                while (!q.isEmpty()) {
                    int[] p = q.poll();
                    for (int[] k : d) {
                        int y = p[0] + k[0], x = p[1] + k[1];
                        if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == '1') {
                            g[y][x] = '0'; q.add(new int[]{y, x});
                        }
                    }
                }
            }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(numIslands(grid("11110", "11010", "11000", "00000")));
        System.out.println(numIslands(grid("11000", "11000", "00100", "00011")));
        System.out.println(numIslands(grid("101", "101", "111")));
        System.out.println(numIslands(grid("000", "000")));
        System.out.println(numIslands(grid("111", "111")));
        System.out.println(numIslands(grid("1")));
    }
}

Real output:

1
3
1
0
1
1

The two examples (1, 3), the U (1), and the edge cases: all water 0, all land 1, a single cell 1. All correct.

The snake in milliseconds

The same BFS with the snake main. Real output:

1 island, 24 ms

One island, no crash: the BFS queue holds only a few cells at a time on a snake (it never gets long), and the whole 400 × 400 map is done in milliseconds.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

int numIslands(vector<string> g) {
    int R = g.size(), C = g[0].size(), count = 0;
    int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    queue<pair<int, int>> q;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) {
            if (g[r][c] != '1') continue;
            count++;
            g[r][c] = '0'; q.push({r, c});
            while (!q.empty()) {
                auto [pr, pc] = q.front(); q.pop();
                for (auto& k : d) {
                    int y = pr + k[0], x = pc + k[1];
                    if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == '1') {
                        g[y][x] = '0'; q.push({y, x});
                    }
                }
            }
        }
    return count;
}

int main() {
    cout << numIslands({"11110", "11010", "11000", "00000"}) << "\n";
    cout << numIslands({"11000", "11000", "00100", "00011"}) << "\n";
    cout << numIslands({"101", "101", "111"}) << "\n";
    cout << numIslands({"000", "000"}) << "\n";
    cout << numIslands({"111", "111"}) << "\n";
    cout << numIslands({"1"}) << "\n";
    int n = 400;                                   // the 400 x 400 snake
    vector<string> s(n, string(n, '0'));
    for (int r = 0; r < n; r++) {
        if (r % 2 == 0) s[r] = string(n, '1');
        else s[r][(r / 2) % 2 == 0 ? n - 1 : 0] = '1';
    }
    cout << numIslands(s) << " island on the snake\n";
}

vector<string> g is passed by value, so the function sinks its own copy and the caller's grid is untouched. auto [pr, pc] is a C++17 structured binding: it unpacks the pair. Real output (g++ -O2 -std=c++17):

1
3
1
0
1
1
1 island on the snake

The same solution in Python

from collections import deque

def num_islands(grid):
    g = [list(row) for row in grid]          # a mutable copy of the strings
    R, C, count = len(g), len(g[0]), 0
    for r in range(R):
        for c in range(C):
            if g[r][c] != "1":
                continue
            count += 1
            g[r][c] = "0"
            q = deque([(r, c)])
            while q:
                pr, pc = q.popleft()
                for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    y, x = pr + dy, pc + dx
                    if 0 <= y < R and 0 <= x < C and g[y][x] == "1":
                        g[y][x] = "0"
                        q.append((y, x))
    return count

print(num_islands(["11110", "11010", "11000", "00000"]))
print(num_islands(["11000", "11000", "00100", "00011"]))
print(num_islands(["101", "101", "111"]))
print(num_islands(["000", "000"]))
print(num_islands(["111", "111"]))
print(num_islands(["1"]))
n = 400
snake = []
for r in range(n):
    row = ["0"] * n
    if r % 2 == 0:
        row = ["1"] * n
    else:
        row[n - 1 if (r // 2) % 2 == 0 else 0] = "1"
    snake.append("".join(row))
print(num_islands(snake), "island on the snake")

Python strings cannot be changed, so the function first makes a list of lists. collections.deque is Python's fast queue: append at the back, popleft from the front. Real output:

1
3
1
0
1
1
1 island on the snake

Three real bugs

Bug 1: comparing a char with 1 instead of '1'

                if (g[r][c] != 1) continue;

Real output on the two LeetCode examples:

0
0

It even compiles. A char is a number underneath, and the character '1' has the code 49, not 1. So no cell ever looks like land and nothing is counted. Use quotes: '1'.

Bug 2: eight directions instead of four

        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        // main: numIslands(grid("10", "01"))

Real output:

1

1 instead of 2. The grid 10 / 01 has two land cells that only touch at a corner. This problem says only up, down, left and right connect land, so they are two islands. Always read which neighbours count.

Bug 3: the recursive sink without marking the cell

    static void sink(char[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
        sink(g, r + 1, c); sink(g, r - 1, c);
        sink(g, r, c + 1); sink(g, r, c - 1);
    }
    // main: numIslands(grid("11"))

The line g[r][c] = '0'; is missing. Real output (first lines), on just two cells:

Exception in thread "main" java.lang.StackOverflowError
    at Main.sink(Main.java:18)
    at Main.sink(Main.java:19)

The first cell sinks the second, the second sinks the first, back and forth forever, until the call stack is full. Mark the cell before visiting its neighbours.

Complexity

With R rows and C columns:

Approach Time Space Correct? 400 × 400 snake
Count top-left corners O(R × C) O(1) No (U shape: 2 instead of 1) n/a
Spread labels until stable O((R × C)²) O(R × C) labels Yes Time Limit Exceeded
Recursive DFS flood fill O(R × C) O(R × C) call stack Yes StackOverflowError
BFS flood fill O(R × C) O(R × C) worst-case queue, O(1) extra grid memory (in place) Yes 24 ms

Flood fill sinks every cell once and looks at each cell's four neighbours, so O(R × C) time. That is the best possible, because we must at least look at every cell. The queue can hold many cells in the worst case, so O(R × C) space; the recursive DFS needs the same amount, but in the small call stack, which is exactly why it crashed.

Common mistakes

Mistake What you see Why Fix
g[r][c] != 1 0 islands '1' is the number 49 compare with '1'
8 directions 1 instead of 2 on 10 / 01 diagonals don't connect in this problem only the 4 directions
sink without g[r][c] = '0' Exception in thread "main" java.lang.StackOverflowError two cells call each other forever set '0' before the neighbours
Recursive DFS on a long island Exception in thread "main" java.lang.StackOverflowError 80,000 nested calls BFS with a queue
Marking a cell when it is polled, not when it is added still correct, but a cell can be added to the queue several times (slower, more memory) two neighbours both see it as land mark when adding
Counting top-left corners 2 instead of 1 on the U islands are not a local property flood fill
Changing the caller's grid the grid is all '0' afterwards flood fill sinks in place copy it first, or use a boolean[][] seen (practice 2)

Mini project: the relief-boat planner

Extend the BFS so that, for every island, it prints where the boat should land (the first cell the scan found) and how many squares the island has, and estimates the people to help (here 25 per square of dry land).

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String[] map = {
            "1100000110",
            "1100000110",
            "0001000000",
            "0011100011",
            "0001000001",
            "1000000001"};
        char[][] g = new char[map.length][];
        for (int i = 0; i < map.length; i++) g[i] = map[i].toCharArray();
        int R = g.length, C = g[0].length, boats = 0, people = 0;
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                if (g[r][c] != '1') continue;
                boats++;
                int size = 0;
                g[r][c] = '0'; q.add(new int[]{r, c});
                while (!q.isEmpty()) {
                    int[] p = q.poll();
                    size++;
                    for (int[] k : d) {
                        int y = p[0] + k[0], x = p[1] + k[1];
                        if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == '1') {
                            g[y][x] = '0'; q.add(new int[]{y, x});
                        }
                    }
                }
                int need = size * 25;                  // 25 people live on each dry square
                people += need;
                System.out.println("Boat " + boats + ": land at (" + r + ", " + c + "), " + size + " squares, about " + need + " people");
            }
        System.out.println(boats + " boats, about " + people + " people to help");
    }
}

Real output:

Boat 1: land at (0, 0), 4 squares, about 100 people
Boat 2: land at (0, 7), 4 squares, about 100 people
Boat 3: land at (2, 3), 5 squares, about 125 people
Boat 4: land at (3, 8), 4 squares, about 100 people
Boat 5: land at (5, 0), 1 squares, about 25 people
5 boats, about 450 people to help

Ideas to go further: sort the islands by size so the biggest gets help first; read the map from input; add a second map of "people per square" instead of a fixed 25.

Practice

These are the episode's homework items. All four solutions were run together in one Main class with the grid helper above and

    static final int[][] D4 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static final int[][] D8 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
  1. Max Area of Island (LeetCode 695): the grid is int[][] of 0 and 1; return the number of cells in the biggest island (0 if there is no land).
Solution

The same BFS flood fill, but count the cells as they leave the queue, and keep the best.

    static int maxAreaOfIsland(int[][] g) {
        int R = g.length, C = g[0].length, best = 0;
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                if (g[r][c] != 1) continue;
                int area = 0;
                g[r][c] = 0; q.add(new int[]{r, c});
                while (!q.isEmpty()) {
                    int[] p = q.poll();
                    area++;
                    for (int[] k : D4) {
                        int y = p[0] + k[0], x = p[1] + k[1];
                        if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == 1) {
                            g[y][x] = 0; q.add(new int[]{y, x});
                        }
                    }
                }
                best = Math.max(best, area);
            }
        return best;
    }

On LeetCode's 8 × 13 example grid the real output is P1 max area: 6; on {{0, 0, 0, 0, 0, 0, 0, 0}} it is P1 all water: 0. Here the grid holds ints, so comparing with 1 is right (the opposite of bug 1). O(R × C).

  1. Count the islands without changing the grid.
Solution

Keep a separate boolean[][] seen and mark cells there instead of writing '0'. The dirs parameter lets practice 4 reuse it.

    static int countIslands(char[][] g, int[][] dirs) {
        int R = g.length, C = g[0].length, count = 0;
        boolean[][] seen = new boolean[R][C];
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                if (g[r][c] != '1' || seen[r][c]) continue;
                count++;
                seen[r][c] = true; q.add(new int[]{r, c});
                while (!q.isEmpty()) {
                    int[] p = q.poll();
                    for (int[] k : dirs) {
                        int y = p[0] + k[0], x = p[1] + k[1];
                        if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == '1' && !seen[y][x]) {
                            seen[y][x] = true; q.add(new int[]{y, x});
                        }
                    }
                }
            }
        return count;
    }

On example 2 with D4, real output:

P2 islands: 3
P2 grid after: 11000 11000 00100 00011

The grid is unchanged. The cost is O(R × C) extra memory for seen.

  1. Flood Fill (LeetCode 733): an image is an int[][] of colours. Starting at (sr, sc), recolour that pixel and every pixel connected to it (4 directions) that has the same starting colour to color.
Solution

This is exactly the "sink" step on its own, with "same old colour" instead of "land". Watch the trap: if old == color, return straight away, or the BFS would keep finding the "old" colour it just painted and loop forever.

    static int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int old = image[sr][sc];
        if (old == color) return image;
        int R = image.length, C = image[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        image[sr][sc] = color; q.add(new int[]{sr, sc});
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int[] k : D4) {
                int y = p[0] + k[0], x = p[1] + k[1];
                if (y >= 0 && x >= 0 && y < R && x < C && image[y][x] == old) {
                    image[y][x] = color; q.add(new int[]{y, x});
                }
            }
        }
        return image;
    }

floodFill({{1, 1, 1}, {1, 1, 0}, {1, 0, 1}}, 1, 1, 2) → real output P3 flood fill: [[2, 2, 2], [2, 2, 0], [2, 0, 1]]. The bottom-right 1 touches the rest only diagonally, so it keeps its colour.

  1. Number of islands when diagonals also connect land.
Solution

Here 8 directions are the rule, so bug 2 becomes the correct code: call countIslands(g, D8).

        System.out.println("P4 4 directions: " + countIslands(grid("10", "01"), D4));
        System.out.println("P4 8 directions: " + countIslands(grid("10", "01"), D8));
        System.out.println("P4 quiz grid, 4 dirs: " + countIslands(grid("1101", "0101", "1000", "1101"), D4)
                + ", 8 dirs: " + countIslands(grid("1101", "0101", "1000", "1101"), D8));

Real output:

P4 4 directions: 2
P4 8 directions: 1
P4 quiz grid, 4 dirs: 4, 8 dirs: 3

On the quiz grid, the top-left and bottom-left groups touch diagonally at (1, 1)–(2, 0), so with diagonals they become one island.

Quick quiz

How many islands are in this grid, using up, down, left and right only? 4, 3, 5 or 2?

1 1 0 1
0 1 0 1
1 0 0 0
1 1 0 1
Answer

4. The three cells at the top left; the two at the top right; the three at the bottom left (they touch the top group only diagonally, which doesn't count); and the single cell at the bottom right. The program in practice 4 confirms it: 4 with 4 directions (and 3 if diagonals counted).

Interview questions

  1. Why is a grid a graph? Each land cell is a vertex, and each pair of touching land cells (up, down, left, right) is an edge. The neighbours are computed from (r, c), so no adjacency list is needed.
  2. What does one flood fill visit? Exactly one connected component: one island. So the answer is the number of times the scan finds untouched land.
  3. DFS or BFS here? Both are O(R × C). Recursive DFS is shorter, but on a long island it can overflow the call stack (a real StackOverflowError on the 400 × 400 snake). BFS with a queue, or DFS with an explicit stack (ArrayDeque with push/pop), avoids that.
  4. Why mark a cell when you add it to the queue, not when you poll it? So it can never be added twice; marking on poll is still correct but wastes time and memory.
  5. What if you must not change the input? Copy the grid, or keep a boolean[][] seen (practice 2).
  6. What is the space complexity? O(R × C) in the worst case for the queue (or the recursion stack); the in-place version needs no extra grid.
  7. What if the map is huge and islands are added one cell at a time ("Number of Islands II", LeetCode 305)? Re-running flood fill after every addition is too slow; a union-find (disjoint set) structure merges islands as land appears.
  8. Why does the corner trick fail? Being in the same island is not a local property: the two arms of a U are joined far away from their top cells.

Glossary

Term Meaning
Grid A table of rows and columns; here a char[][] of '1' and '0'
Cell (r, c) The square in row r, column c, counted from 0
char One character; underneath a number ('1' = 49, '0' = 48)
4-directional neighbours The cells up, down, left and right of a cell (no diagonals)
Diagonal A cell that touches only at a corner, like (r+1, c+1)
Connected Reachable from each other over land, one neighbour step at a time
Island A group of connected land cells with water or the edge all around
Graph / vertex / edge Points joined by links; here land cells and the touching pairs
Adjacency list A list of neighbours for each vertex (not needed for a grid)
Connected component A largest group of vertices that can all reach each other
Label A number given to a cell to say which group it belongs to (idea 2)
HashSet A Java set that keeps each value once; used to count distinct labels
Flood fill Spreading from one cell to every connected cell of the same kind, changing them
Sink Turning every cell of an island into water so it is never counted again
DFS (depth-first search) Explore as deep as possible first; here with recursion
BFS (breadth-first search) Explore in waves, nearest first, with a queue
Recursion A method that calls itself
Call stack The memory holding one frame per unfinished method call; small
StackOverflowError Java's error when the call stack runs out (too many nested calls)
Heap The large memory area where objects such as queues live
Queue First in, first out: add at the back, take from the front
ArrayDeque / add / poll Java's queue class / put at the back / take from the front (null if empty)
deque / popleft Python's queue (collections.deque) / take from the front
Direction array d The row and column steps {1,0}, {-1,0}, {0,1}, {0,-1} for down, up, right, left
In place Changing the input itself instead of using extra memory
boolean[][] seen A separate "visited" grid, so the input stays unchanged
Edge case An unusual input: all water, all land, a single cell
O(R × C) Time that grows with the number of cells
O((R × C)²) Time that grows with the square of the number of cells
Lakh / crore Indian number words: 1 lakh = 1,00,000; 1 crore = 1,00,00,000
Time Limit Exceeded (TLE) The program was stopped for running too long (8 s in the SyntaxPilot compiler)
Multi-source BFS A BFS that starts from many cells at once (next episode)

Summary

  • A grid is a graph in disguise: land cells are vertices, touching land cells (up, down, left, right) are edges, and an island is a connected component.
  • Local tricks fail (the U shape: 2 instead of 1), and spreading labels is O((R × C)²): Time Limit Exceeded on a 400 × 400 snake.
  • Flood fill: scan the grid; on untouched land, count++ and sink the whole island, so it is never counted again. O(R × C) time.
  • Recursive DFS is correct but overflows the call stack on a long island; BFS with an ArrayDeque does not. Mark a cell when it joins the queue.
  • Watch the three bugs: '1' not 1, 4 directions not 8, and always mark before visiting the neighbours.

Next episode: Rotting oranges: multi-source BFS.