1. Introduction to the Islands (Matrix Traversal) Pattern
The Islands pattern refers to a class of problems where you are given a 2D grid (matrix), and you need to find or count connected groups of certain cells (usually marked as 1, X, or some special symbol). Each group or cluster of connected cells is referred to as an island.
This concept is not limited to “water and land” problems. It generalizes to any situation where connected cells must be traversed or counted.
2. Typical Problem Statement Example
You’re given a 2D grid of '1's (land) and '0's (water).
You need to count the number of islands, where an island is formed by connecting adjacent lands horizontally or vertically.
Example:
Input: [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] Output: 3
Explanation:
- The first two rows form one island.
- The third row has an isolated second island.
- The last row has two connected
'1's forming the third island.
3. Core Concepts Behind the Pattern
To understand and apply the Islands pattern effectively, you must master three core ideas:
(a) Matrix as a Graph
Each cell in the matrix can be thought of as a node in a graph.
Each node (cell) is connected to its neighbors (up, down, left, right — or diagonals in some variations).
(b) Traversal Algorithms
We use DFS (Depth-First Search) or BFS (Breadth-First Search) to visit all the cells of one connected component (island).
Once we start from a '1', we traverse all connected ‘1’s, marking them as visited.
(c) Visited Tracking
To avoid recounting the same island multiple times, we must mark visited cells — either by:
- Changing their value (e.g.,
'1'→'0'or'1'→'#'), or - Maintaining a boolean visited[][] array.
4. Approach to Solve an Island Problem
Step 1: Iterate through the entire grid.
For each cell (i, j):
- If it’s a
'1'(land) and not visited,- Start a DFS or BFS from that cell to mark the entire connected island.
- Increment the island count by 1.
Step 2: DFS / BFS traversal
From the current cell, move to its neighbors:
- Up:
(i-1, j) - Down:
(i+1, j) - Left:
(i, j-1) - Right:
(i, j+1)
Continue until all connected '1' cells are marked visited.
5. DFS Implementation (Recursive)
Here’s a Java implementation using Depth-First Search:
public class NumberOfIslands {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++; // Found one island
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
// Base case: out of bounds or already water
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1')
return;
grid[i][j] = '0'; // Mark visited
// Explore all four directions
dfs(grid, i + 1, j); // Down
dfs(grid, i - 1, j); // Up
dfs(grid, i, j + 1); // Right
dfs(grid, i, j - 1); // Left
}
}
6. BFS Implementation (Iterative)
Alternatively, you can use Breadth-First Search with a queue:
import java.util.LinkedList;
import java.util.Queue;
public class NumberOfIslandsBFS {
private static final int[][] DIRECTIONS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
bfs(grid, i, j);
}
}
}
return count;
}
private void bfs(char[][] grid, int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = '0'; // Mark visited
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] dir : DIRECTIONS) {
int x = cell[0] + dir[0];
int y = cell[1] + dir[1];
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == '1') {
grid[x][y] = '0';
queue.offer(new int[]{x, y});
}
}
}
}
}
7. Complexity Analysis
- Time Complexity:
Each cell is visited once, and each traversal explores its four neighbors.
Therefore, time complexity = O(M × N), whereMandNare the number of rows and columns. - Space Complexity:
- DFS (recursive) → O(M × N) in worst case due to call stack.
- BFS (iterative) → O(M × N) for the queue.
8. Identifying Problems That Use the “Islands” Pattern
To identify when to apply this pattern, look for:
- A 2D grid (matrix) structure.
- A need to count or traverse groups of similar cells (e.g.,
'1','X','A', or a color). - A rule defining connectivity (4-directional or 8-directional).
- The task often involves flooding, painting, capturing regions, or component counting.
Common Examples:
- Number of Islands (LeetCode 200)
- Max Area of Island (LeetCode 695)
- Flood Fill (LeetCode 733)
- Surrounded Regions (LeetCode 130)
- Count Closed Islands (LeetCode 1254)
9. Variations of the Islands Pattern
- Diagonal Connectivity:
You may need to check 8 directions instead of 4. - Different Symbols or Values:
Instead of'1'and'0', it may be'X'and'O', or integers. - Counting Areas or Sizes:
Instead of counting islands, you might compute the area (number of cells) of the largest island. - Flood Fill / Coloring Problems:
Replace all connected cells of the same color with a new color.
10. Visualization of DFS Traversal
Imagine this grid:
1 1 0 0 1 0 0 0 1
When DFS starts from (0,0):
- It visits (0,0) → (0,1) → (1,1)
- Marks them as visited.
- Ends that island.
When DFS reaches (2,2):
- Starts a new traversal.
- Counts another island.
So total islands = 2.
11. Key Takeaways
- Core idea: Explore all connected neighbors to form one group.
- Techniques used: DFS or BFS traversal on a grid.
- When to use: Any time you need to identify or count connected components in a 2D matrix.
- Optimization tip: Modify the grid in-place to mark visited cells instead of using an extra array to save memory.