March 24
Number of Islands
How to see each cell as a graph node and use DFS or BFS to consume one whole island at a time.
Graphs on a Grid Intermediate 22 min TypeScript
Given a 2D grid made of '1' (land) and '0' (water), return the number of islands.
An island is formed by land cells connected 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
What to notice before coding
- Diagonal does not connect islands.
- The problem is asking you to count connected components.
- Once you consume one whole island, it must not be counted again.
Common mistakes
- counting each land cell separately
- forgetting to mark visited before exploring neighbors
Step 1 - Stop seeing this as just a matrix
This problem gets simpler when you rename it mentally.
Instead of "a matrix of 1s and 0s", think:
- each land cell is a node
- neighbors up, down, left, and right are edges
Now you are counting connected components.
Step 2 - Write the counting rule
If you are scanning the grid and find land that has not been visited yet:
- you found a new island
- increment the answer
- consume the whole island before continuing
Step 3 - Build the baseline with visited tracking
A good baseline is:
That makes the structure of the problem very explicit.
Step 4 - Notice that the grid itself can become the visited structure
In many cases, you do not need extra storage.
You can mark processed land as water and keep going.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function numIslands(grid: string[][]): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(rows * cols)
Space: O(rows * cols)
Solution 1 - DFS with a Hash Set of visited cells
Good baseline because it makes the connected-component nature of the problem explicit.
export function numIslands(grid: string[][]): number {
const rows = grid.length
const cols = grid[0]?.length ?? 0
const visited = new Set<string>()
let islands = 0
function dfs(row: number, col: number) {
if (
row < 0 ||
row >= rows ||
col < 0 ||
col >= cols ||
grid[row][col] === '0'
) {
return
}
const key = `${row},${col}`
if (visited.has(key)) {
return
}
visited.add(key)
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] === '1' && !visited.has(`${row},${col}`)) {
islands += 1
dfs(row, col)
}
}
}
return islands
}It works well. But you can use the grid itself as the marker.
Solution 2 - DFS by turning the grid into the visited structure
Now the visited state lives inside the input itself.
export function numIslands(grid: string[][]): number {
const rows = grid.length
const cols = grid[0]?.length ?? 0
let islands = 0
function dfs(row: number, col: number) {
if (
row < 0 ||
row >= rows ||
col < 0 ||
col >= cols ||
grid[row][col] === '0'
) {
return
}
grid[row][col] = '0'
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] === '1') {
islands += 1
dfs(row, col)
}
}
}
return islands
}The strong part here is reading the problem as connected components, not the fact that it uses DFS specifically.
What to say in the interview
A strong short explanation would be:
I treat each land cell as a node in a graph on a grid. When I find land that has not been visited yet, that means a new island. Then I increment the answer and run
DFSto consume the whole connected component. That way each cell is visited at most once.
That shows that you:
- translated the format into a graph model
- separated the counting rule from the exploration rule
- explained why the answer does not double-count islands
When this pattern shows up again
The same pattern comes back when you need to:
- traverse a grid with
BFSorDFS - count connected components
- do flood fill
- treat cells as nodes and adjacency as edges
The point is not memorizing
numIslands.
The point is learning to see hidden graphs inside grids.