Find the no. of Islands
Problem Statement
Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is a group of connected '1's (connected horizontally or vertically). The grid is surrounded by water.
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
Noob-Friendly Explanation
Imagine looking at a map from above. You see land (1) and water (0). An island is a group of land cells connected up, down, left, or right (not diagonally). You want to count how many separate islands there are.
Think of it like counting puddles after rain, but in reverse — you're counting the dry land groups. Every time you find a land cell you haven't explored, that's a new island! Then you explore all connected land cells (the whole island) so you don't count it again.
Approach 1: Brute Force (BFS)
Intuition
Iterate through every cell. When you find an unvisited land cell, increment the island count and use BFS to visit all connected land cells (marking them as visited).
Algorithm
- Iterate through each cell in the grid.
- If it's a '1' and not visited, increment count.
- Use BFS to visit all connected '1' cells.
- Mark visited cells to avoid double counting.
import java.util.LinkedList;
import java.util.Queue;
public class IslandsBFS {
public static int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int count = 0;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
count++;
// BFS to visit entire island
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{i, j});
visited[i][j] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int d = 0; d < 4; d++) {
int newRow = cell[0] + dx[d];
int newCol = cell[1] + dy[d];
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
&& grid[newRow][newCol] == '1' && !visited[newRow][newCol]) {
visited[newRow][newCol] = true;
queue.add(new int[]{newRow, newCol});
}
}
}
}
}
}
return count;
}
public static void main(String[] args) {
char[][] grid = {
{'1','1','0','0','0'},
{'1','1','0','0','0'},
{'0','0','1','0','0'},
{'0','0','0','1','1'}
};
System.out.println(numIslands(grid)); // 3
}
}Complexity Analysis
- Time Complexity: O(M × N) — each cell is visited at most once.
- Space Complexity: O(M × N) — for the visited array and queue.
Approach 2: Optimal (DFS — In-place Modification)
Intuition
Instead of using a separate visited array, modify the grid in-place. When we visit a land cell, change it to '0' (water) so we don't visit it again. This saves the extra visited array.
Algorithm
- Iterate through each cell.
- When a '1' is found, increment count and call DFS.
- DFS sinks the island: change current cell to '0', then recurse on all 4 neighbors.
public class IslandsDFS {
public static 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++;
sinkIsland(grid, i, j, rows, cols);
}
}
}
return count;
}
static void sinkIsland(char[][] grid, int row, int col, int rows, int cols) {
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
return;
}
grid[row][col] = '0'; // sink this cell
sinkIsland(grid, row - 1, col, rows, cols); // up
sinkIsland(grid, row + 1, col, rows, cols); // down
sinkIsland(grid, row, col - 1, rows, cols); // left
sinkIsland(grid, row, col + 1, rows, cols); // right
}
public static void main(String[] args) {
char[][] grid = {
{'1','1','0','0','0'},
{'1','1','0','0','0'},
{'0','0','1','0','0'},
{'0','0','0','1','1'}
};
System.out.println(numIslands(grid)); // 3
}
}Complexity Analysis
- Time Complexity: O(M × N) — each cell is visited at most once.
- Space Complexity: O(M × N) — for the recursion stack in the worst case (when entire grid is land).