Number of Islands
Problem link: https://leetcode.com/problems/number-of-islands/
Problem Statement
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (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 all surrounded by water.
Input
A 2D character array grid.
Output
An integer representing the count of islands.
Example
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
Explanation
The grid contains three distinct groups of '1's. The first group is a 2x2 block, the second is a single cell, and the third is a horizontal pair.
Brute Force
Intuition
Iterate through every cell. For every '1', try to find all other '1's that belong to the same island using exhaustive pathfinding, but without a clear way to mark them as 'visited', this leads to infinite loops.
Approach
Check every cell and its neighbors, but without marking cells, you'd double count or loop infinitely.
Optimal Solution
Intuition
Treat the grid as an adjacency matrix. Iterate through the grid; when you hit a '1', increment your island count and use DFS (Flood Fill) to turn that entire island into '0's (water). This 'sinking' technique ensures each island is only counted once.
Approach
- Initialize
count = 0. - Loop through every cell
(r, c)in the grid. - If
grid[r][c] == '1':- Increment
count. - Trigger a recursive
dfs(r, c)to mark all connected land cells as '0' (or any visited marker).
- Increment
- In
dfs(r, c):- Check boundary conditions and if the cell is '0'.
- Set
grid[r][c] = '0'. - Recursively call DFS for Up, Down, Left, and Right.
- Return
count.
Dry Run
Grid 2x2: [[1, 1], [0, 1]]
- (0,0) is '1'. Count=1. Start DFS.
- DFS(0,0) -> grid[0,0]=0. Call DFS on (0,1) and (1,0).
- DFS(0,1) -> grid[0,1]=0. Call DFS on (1,1).
- DFS(1,1) -> grid[1,1]=0.
- Scan continues, no more '1's found. Return 1.
Code (Java)
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') {
return;
}
grid[r][c] = '0'; // Sink the island
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
}
Complexity Analysis
Time: Every cell is visited once. Space: Worst case for recursion stack is O(M*N) if the entire grid is one giant island.
Quick Revision (Brute Force)
- Iterate without marking visited (Impossible/Loops)
Quick Revision (Optimal)
- Iterate through grid
- When '1' is found, increment count and call DFS
- DFS 'sinks' the island by turning '1's into '0's
- O(M*N) Time, O(M*N) Space (stack)