DSA-093 · FOCUSED PRACTICE
Number of Islands
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 517 deterministic checks. Learner drafts are not executed.
Understand the problem
Count islands of land cells in a rectangular grid. Land is char '1', water is char '0', and land connects only through orthogonal neighbors.
- Non-null rectangular char[][] with 0–100 rows and 0–100 columns. Rows are non-null and contain only '0' or '1'. Malformed grids are outside the contract.
- Empty or zero-column grids return 0. Diagonal contact does not join islands.
- Both methods preserve every input cell. The iterative reference uses separate visited state; the recursive DFS baseline is limited to small grids because of Java recursion depth.
Examples
Input:
["110","010","001"]
Output:2The top-left component contains three cells; the bottom-right land cell is diagonally separated.
Input:
["10","01"]
Output:2The two land cells share no orthogonal edge.
Before you start
- Four-direction graph adjacency
- Visited-state ownership and component counting
Recognize the structure
The goal is connected-component count, not shortest arrival time. Start one traversal at each unvisited land cell and count the traversal starts. BFS or DFS works; the reference chooses BFS to avoid a deep recursive call chain.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 101/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
View every land cell as a vertex.
Hint 2
One traversal exhausts exactly one component.
Hint 3
Scan all cells, start only on unvisited land, and mark neighbors on discovery.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Recursive flood traversal
Scan every cell. When an unvisited land cell appears, increment the count and recursively visit its orthogonal land neighbors. For ["101"], two separate starts are needed. This is already O(RC) work, but a long connected region can exhaust the Java call stack. It also needs O(RC) visited state plus up to O(RC) recursive frames.
Improve the baseline
Make the traversal frontier explicit
Use an ArrayDeque of cell coordinates rather than recursive calls. Keep separate visited flags to preserve the input.
Count once at component discovery
Only an unvisited land cell starts a new island. Increment before exploring; all reachable land is claimed by that traversal.
Mark when enqueuing
A cell discovered by two neighbors must enter the queue only once. Set its visited flag before insertion, including the initial component cell.
Why it is correct
Initialize
No cells are visited and no components have been started; the count is zero.
Preserve traversal coverage
Every queued cell is land connected to the current starting cell. Following only orthogonal land edges cannot leave its component. Marking on discovery prevents duplicate claims, and exhausting the queue visits every reachable land cell.
Finish the scan
A new start cannot belong to a previous component, which would already be fully visited. Conversely every component has a first scanned cell, so it receives one start. Finite cells and one enqueue per land cell guarantee termination.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayDeque;
import java.util.Deque;
public final class Solution {
private static final int[][] DIRECTIONS = {{1,0},{-1,0},{0,1},{0,-1}};
public static int numIslands(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return 0;
boolean[][] visited = new boolean[grid.length][grid[0].length];
int count = 0;
Deque<int[]> queue = new ArrayDeque<>();
for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] != '1' || visited[r][c]) continue;
count++;
visited[r][c] = true;
queue.addLast(new int[]{r,c});
while (!queue.isEmpty()) {
int[] cell = queue.removeFirst();
for (int[] d : DIRECTIONS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr < 0 || nr >= grid.length || nc < 0 || nc >= grid[0].length || grid[nr][nc] != '1' || visited[nr][nc]) continue;
visited[nr][nc] = true;
queue.addLast(new int[]{nr,nc});
}
}
}
return count;
}
public static int baseline(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return 0;
boolean[][] visited = new boolean[grid.length][grid[0].length];
int count = 0;
for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1' && !visited[r][c]) { count++; dfs(grid, visited, r, c); }
return count;
}
private static void dfs(char[][] grid, boolean[][] visited, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1' || visited[r][c]) return;
visited[r][c] = true;
for (int[] d : DIRECTIONS) dfs(grid, visited, r + d[0], c + d[1]);
}
}
Read the meaningful blocks
Separate land from visited
Water never starts traversal, and visited land never starts another island.
Scan all coordinates
A single traversal cannot find disconnected components.
Check bounds before indexing
Neighbor validation precedes grid access; all four orthogonal directions are considered.
Complexity
O(RC) time: the scan visits all cells, and each land cell enters the queue once with four constant-time neighbor checks.
Visited storage and the queue each have O(RC) worst-case size. Output is one count. The recursive baseline also has O(RC) auxiliary worst-case storage and may overflow the call stack; input mutation is not used to hide visited memory.
Exact-state walkthroughs
Reveal normal and boundary traces
Separate diagonal component
Input: [[1,1,0],[0,1,0],[0,0,1]] · Result: 2
Step 1 of 8: Keep input land separate from visited flags.
No cell has been claimed and the input is unchanged.
1 = land · 0 = water · ✓ = claimed. The input land never changes.
| Variable | Value |
|---|---|
| land | [[1,1,0],[0,1,0],[0,0,1]] |
| visited | [[false,false,false],[false,false,false],[false,false,false]] |
| queue | [] |
| count | 0 |
See the affected Java block
1 import java.util.ArrayDeque; 2 import java.util.Deque; 3 4 public final class Solution { 5 private static final int[][] DIRECTIONS = {{1,0},{-1,0},{0,1},{0,-1}}; 6 public static int numIslands(char[][] grid) { 7 if (grid.length == 0 || grid[0].length == 0) return 0; 8 boolean[][] visited = new boolean[grid.length][grid[0].length]; 9 int count = 0; 10 Deque<int[]> queue = new ArrayDeque<>(); 11 for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++) { 12 if (grid[r][c] != '1' || visited[r][c]) continue; 13 count++; 14 visited[r][c] = true; 15 queue.addLast(new int[]{r,c}); 16 while (!queue.isEmpty()) { 17 int[] cell = queue.removeFirst(); 18 for (int[] d : DIRECTIONS) { 19 int nr = cell[0] + d[0], nc = cell[1] + d[1]; 20 if (nr < 0 || nr >= grid.length || nc < 0 || nc >= grid[0].length || grid[nr][nc] != '1' || visited[nr][nc]) continue; 21 visited[nr][nc] = true; 22 queue.addLast(new int[]{nr,nc}); 23 } 24 } 25 } 26 return count; 27 } 28 29 public static int baseline(char[][] grid) { 30 if (grid.length == 0 || grid[0].length == 0) return 0; 31 boolean[][] visited = new boolean[grid.length][grid[0].length]; 32 int count = 0; 33 for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++) 34 if (grid[r][c] == '1' && !visited[r][c]) { count++; dfs(grid, visited, r, c); } 35 return count; 36 } 37 private static void dfs(char[][] grid, boolean[][] visited, int r, int c) { 38 if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1' || visited[r][c]) return; 39 visited[r][c] = true; 40 for (int[] d : DIRECTIONS) dfs(grid, visited, r + d[0], c + d[1]); 41 } 42 } 43
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Keep input land separate from visited flags.
No cell has been claimed and the input is unchanged.
- land
[[1,1,0],[0,1,0],[0,0,1]]- visited
[[false,false,false],[false,false,false],[false,false,false]]- queue
[]- count
0
- Start exactly one new component.
The start was not reachable from any previously completed component.
- land
[[1,1,0],[0,1,0],[0,0,1]]- visited
[[true,false,false],[false,false,false],[false,false,false]]- queue
[[0,0]]- count
1- start
[0,0]
- Visit orthogonal neighbors and mark them on enqueue.
Every queued cell belongs to the same current component and is queued only once.
- land
[[1,1,0],[0,1,0],[0,0,1]]- visited
[[true,true,false],[false,false,false],[false,false,false]]- queue
[[0,1]]- count
1- cell
[0,0]
- Visit orthogonal neighbors and mark them on enqueue.
Every queued cell belongs to the same current component and is queued only once.
- land
[[1,1,0],[0,1,0],[0,0,1]]- visited
[[true,true,false],[false,true,false],[false,false,false]]- queue
[[1,1]]- count
1- cell
[0,1]
- Visit orthogonal neighbors and mark them on enqueue.
Every queued cell belongs to the same current component and is queued only once.
- land
[[1,1,0],[0,1,0],[0,0,1]]- visited
[[true,true,false],[false,true,false],[false,false,false]]- queue
[]- count
1- cell
[1,1]
- Start exactly one new component.
The start was not reachable from any previously completed component.
- land
[[1,1,0],[0,1,0],[0,0,1]]- visited
[[true,true,false],[false,true,false],[false,false,true]]- queue
[[2,2]]- count
2- start
[2,2]
- Visit orthogonal neighbors and mark them on enqueue.
Every queued cell belongs to the same current component and is queued only once.
- land
[[1,1,0],[0,1,0],[0,0,1]]- visited
[[true,true,false],[false,true,false],[false,false,true]]- queue
[]- count
2- cell
[2,2]
- Return the contract result.
The final state satisfies the requested output contract.
- result
2
Water only
Input: [[0,0]] · Result: 0
Step 1 of 2: Keep input land separate from visited flags.
No cell has been claimed and the input is unchanged.
1 = land · 0 = water · ✓ = claimed. The input land never changes.
| Variable | Value |
|---|---|
| land | [[0,0]] |
| visited | [[false,false]] |
| queue | [] |
| count | 0 |
See the affected Java block
1 import java.util.ArrayDeque; 2 import java.util.Deque; 3 4 public final class Solution { 5 private static final int[][] DIRECTIONS = {{1,0},{-1,0},{0,1},{0,-1}}; 6 public static int numIslands(char[][] grid) { 7 if (grid.length == 0 || grid[0].length == 0) return 0; 8 boolean[][] visited = new boolean[grid.length][grid[0].length]; 9 int count = 0; 10 Deque<int[]> queue = new ArrayDeque<>(); 11 for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++) { 12 if (grid[r][c] != '1' || visited[r][c]) continue; 13 count++; 14 visited[r][c] = true; 15 queue.addLast(new int[]{r,c}); 16 while (!queue.isEmpty()) { 17 int[] cell = queue.removeFirst(); 18 for (int[] d : DIRECTIONS) { 19 int nr = cell[0] + d[0], nc = cell[1] + d[1]; 20 if (nr < 0 || nr >= grid.length || nc < 0 || nc >= grid[0].length || grid[nr][nc] != '1' || visited[nr][nc]) continue; 21 visited[nr][nc] = true; 22 queue.addLast(new int[]{nr,nc}); 23 } 24 } 25 } 26 return count; 27 } 28 29 public static int baseline(char[][] grid) { 30 if (grid.length == 0 || grid[0].length == 0) return 0; 31 boolean[][] visited = new boolean[grid.length][grid[0].length]; 32 int count = 0; 33 for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++) 34 if (grid[r][c] == '1' && !visited[r][c]) { count++; dfs(grid, visited, r, c); } 35 return count; 36 } 37 private static void dfs(char[][] grid, boolean[][] visited, int r, int c) { 38 if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1' || visited[r][c]) return; 39 visited[r][c] = true; 40 for (int[] d : DIRECTIONS) dfs(grid, visited, r + d[0], c + d[1]); 41 } 42 } 43
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Keep input land separate from visited flags.
No cell has been claimed and the input is unchanged.
- land
[[0,0]]- visited
[[false,false]]- queue
[]- count
0
- Return the contract result.
The final state satisfies the requested output contract.
- result
0
Test the contract
Input:
[]
Output:0No rows.
Input:
[""]
Output:0No columns.
Input:
["000"]
Output:0No land.
Input:
["111","111"]
Output:1One dense component.
Common mistakes and counterexamples
Count each discovered cell
Counterexample: ["11"] has one island, not two.
Increment only when starting an unvisited component.
Include diagonals
Counterexample: ["10","01"] has two islands.
Use four directions.
Mark only after dequeue
Counterexample: A square can enqueue a shared neighbor repeatedly.
Mark before enqueuing.
Sink input land despite preservation
Counterexample: A second call on the same grid must return the same result.
Use a separate visited matrix.
Follow-ups
Return each island’s area and perimeter.
Accumulate area per visited cell; add perimeter for each edge meeting water or the grid boundary. Do not count a shared land edge as coastline.
Land is added dynamically.
Use DSU to connect a new land cell with active neighbors, decrementing the island count only when two different components merge. Duplicate additions must not create a new island.
Water can also replace land.
Ordinary DSU cannot split a component. Consider offline reverse processing, dynamic-connectivity structures, or recomputation under a bounded grid contract.