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 rowr, columnc, 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
ArrayDequelive. ArrayDeque: Java's fast queue/stack class;addputs at the back,polltakes 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:
- Give every land cell its own number, a label (
r * C + c + 1). - Every land cell looks at its land neighbours and takes the smallest label it sees.
- Repeat whole passes over the grid until no label changes.
- 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:
- Scan the grid row by row.
- At
(0, 0)we find land: a new island,count = 1. - From that cell, visit its whole island and turn every cell into water: sink it. The scan can never count those cells again.
- The scan goes on. The next land is
(2, 2):count = 2, sink it. - 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.
- Found land:
count++, make it water, put it in the queue. - Take a cell from the queue; check its 4 neighbours.
- Every land neighbour becomes water right away and joins the queue. Sinking it when it joins means it can never be added twice.
- 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}};
- Max Area of Island (LeetCode 695): the grid is
int[][]of0and1; return the number of cells in the biggest island (0if 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).
- 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.
- 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 tocolor.
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.
- 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
- 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. - 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.
- 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
StackOverflowErroron the 400 × 400 snake). BFS with a queue, or DFS with an explicit stack (ArrayDequewithpush/pop), avoids that. - 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.
- What if you must not change the input? Copy the grid, or keep a
boolean[][] seen(practice 2). - 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.
- 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.
- 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
ArrayDequedoes not. Mark a cell when it joins the queue. - Watch the three bugs:
'1'not1, 4 directions not 8, and always mark before visiting the neighbours.
Next episode: Rotting oranges: multi-source BFS.