0% completed
Introduction to Island Pattern
On This Page
Core idea
How it works
Recognize it when
The template
Variants in this chapter
Watch out for
How this compares with nearby patterns
Key takeaways
You are given a grid of land and water. Count the separate islands.
An island is a group of land cells connected up, down, left, or right.
1 1 0 0
1 0 0 1 three islands
0 0 1 0
A grid can be treated as a graph:
- Every cell is a node.
- Each cell connects to nearby cells.
- The row and column numbers tell us where the neighbours are.
We do not need to build an adjacency list.
Scan every cell. When you find unvisited land, you have found a new island. Start a traversal and mark every connected land cell.
After the traversal, continue scanning for the next unvisited land cell.
Core idea
The Island pattern applies graph traversal to a two-dimensional grid.
An outer loop finds unvisited regions. A DFS or BFS traversal marks every cell in one region.
Starting a new traversal means that a new island has been found.
How it works
For the Number of Islands problem:
- Set the island count to zero.
- Scan every row and column.
- Skip water and visited land.
- When unvisited land is found, increase the count.
- Start DFS or BFS from that cell.
- Visit connected land above, below, left, and right.
- Mark each cell before visiting its neighbours.
- Continue scanning after the traversal finishes.
Each cell is processed at most once. For R rows and C columns, the time complexity is O(R * C).
The traversal may hold many cells from one large island. The worst-case space complexity is also O(R * C).
You can use a separate visited grid. You can also change visited land into water when input modification is allowed.
Recognize it when
The Island pattern may be useful when:
- The input is a two-dimensional grid.
- Cells connect through their positions.
- The question asks about regions, areas, groups, or shapes.
- The wording includes island, flood, surrounded, or connected cells.
- You must count or measure separate connected areas.
- You need to replace all cells in one connected region.
Do not use this basic pattern when:
- Connections are provided as node pairs. Use a normal Graph traversal.
- You need the shortest route through a maze. Use BFS and count levels.
- Each cell depends only on earlier calculated cells. Dynamic Programming may be better.
- Movement rules include costs. Use a weighted path algorithm.
The template
function countIslands(grid):
count = 0
for row from 0 to rows - 1:
for col from 0 to columns - 1:
if grid[row][col] is land:
count = count + 1
visit(grid, row, col)
return count
function visit(grid, row, col):
if row or col is outside the grid:
return
if grid[row][col] is not land:
return
grid[row][col] = water
visit(grid, row + 1, col)
visit(grid, row - 1, col)
visit(grid, row, col + 1)
visit(grid, row, col - 1)
The order is important:
- Check the boundaries.
- Check whether the cell is usable.
- Mark the cell.
- Visit its neighbours.
Mark before visiting neighbours. Otherwise, two connected cells can repeatedly call each other.
Variants in this chapter
| Variant | What changes | Problems in this chapter |
|---|---|---|
| Count regions | start one traversal for each new island | Number of Islands |
| Measure a region | return the number of cells visited | Biggest Island |
| Repaint a region | write a new value into every connected cell | Flood Fill |
| Exclude border regions | remove regions connected to the grid edge first | Number of Closed Islands |
| Record region details | calculate a shape, boundary, or other property | Problem Challenge 1, Problem Challenge 2, Problem Challenge 3 |
For closed or surrounded regions, begin at the border. Remove every region connected to it. The remaining regions are closed.
Watch out for
- Reading a cell before checking its coordinates. Check boundaries first.
- Marking after recursive calls. Mark the cell before exploring neighbours.
- Using diagonal movement without permission. Most island problems use four directions.
- Changing the grid without saying so. Use a separate visited structure if mutation is forbidden.
- Using deep recursion on a large grid. An explicit queue or stack avoids call-stack overflow.
- Counting visited land again. Only unvisited land should start a new island traversal.
How this compares with nearby patterns
| If the problem needs... | Use... |
|---|---|
| connected regions in a grid | Island pattern |
| connections provided as pairs | Graph traversal |
| the shortest unweighted route through a grid | Breadth First Search |
| connected groups without traversal details | Union Find |
The Island pattern is a graph traversal where neighbours are calculated from coordinates.
Key takeaways
- Treat every grid cell as a graph node.
- The outer loops find new islands.
- DFS or BFS visits one complete island.
- Check bounds, check the cell, then mark it before exploring.
- The time complexity is
O(R * C). - Confirm whether diagonal movement and input modification are allowed.
Now apply this pattern to Number of Islands.
zaid
· 3 years ago
title
Reading Progress
0%
On This Page
Core idea
How it works
Recognize it when
The template
Variants in this chapter
Watch out for
How this compares with nearby patterns
Key takeaways