Practice › Graphs
Number of Islands
Medium · Graphs · Asked at Amazon, Google, Microsoft, Meta, Uber
In a grid of 1 (land) and 0 (water), an island is a group of land cells connected horizontally or vertically. Count the islands.
Input
First line: r c. Next r lines: c values (0 or 1) separated by spaces.
Output
The number of islands.
Constraints
- 1 ≤ r, c ≤ 300
Example 1
Input
4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1
Output
3
Example 2
Input
1 1 0
Output
0
Hints
- Each island is a connected component of land cells in a grid graph.
- Scan the grid; on an unvisited land cell, count one island and flood-fill (BFS) the whole island, marking it as water/visited.
Approach
Go through every cell. When you find a 1, count a new island and BFS from it in the four directions, turning every reached land cell into 0 so it isn't counted again. Every cell is enqueued at most once. With a 300 × 300 grid, a recursive DFS could go 90 000 calls deep, so an explicit queue is safer.
Complexity: O(r·c) time · O(r·c) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int r, c;
cin >> r >> c;
vector<vector<int>> g(r, vector<int>(c));
for (auto &row : g)
for (auto &x : row) cin >> x;
int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
int islands = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
if (g[i][j] != 1) continue;
islands++;
queue<pair<int, int>> q;
q.push({i, j});
g[i][j] = 0;
while (!q.empty()) {
auto cell = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int x = cell.first + dr[d], y = cell.second + dc[d];
if (x >= 0 && x < r && y >= 0 && y < c && g[x][y] == 1) {
g[x][y] = 0;
q.push({x, y});
}
}
}
}
cout << islands << "\n";
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
r, c = data[0], data[1]
g = [data[2 + i * c : 2 + (i + 1) * c] for i in range(r)]
islands = 0
for i in range(r):
for j in range(c):
if g[i][j] != 1:
continue
islands += 1
g[i][j] = 0
q = deque([(i, j)])
while q:
x, y = q.popleft()
for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= nx < r and 0 <= ny < c and g[nx][ny] == 1:
g[nx][ny] = 0
q.append((nx, ny))
print(islands)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int r = sc.nextInt(), c = sc.nextInt();
int[][] g = new int[r][c];
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) g[i][j] = sc.nextInt();
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
int islands = 0;
ArrayDeque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
if (g[i][j] != 1) continue;
islands++;
g[i][j] = 0;
q.add(new int[] {i, j});
while (!q.isEmpty()) {
int[] cell = q.poll();
for (int d = 0; d < 4; d++) {
int x = cell[0] + dr[d], y = cell[1] + dc[d];
if (x >= 0 && x < r && y >= 0 && y < c && g[x][y] == 1) {
g[x][y] = 0;
q.add(new int[] {x, y});
}
}
}
}
System.out.println(islands);
}
}