Count the Separate Landmasses on a Map
Solve this ProblemYou are given a map of land (1) and water (0) cells. A landmass is a group of land cells connected through shared sides. Count how many separate landmasses the map contains.
A cell that only touches another land cell at a corner is not connected to it. The standard idea is to scan the map and flood-fill each newly found landmass once.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 12; grid[r][c] is 1 (land) or 0 (water) - ◆
Two land cells belong to the same landmass when you can go from one to the other moving up, down, left or right over land only - ◆
Diagonal neighbours are NOT connected - ◆
Return the number of landmasses
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Spread the Smallest Label Until It Stops Changing
BruteGive every land cell its own label (its position number). Then sweep the grid repeatedly: each land cell adopts the smallest label among itself and its land neighbours. When a full sweep changes nothing, all cells of one landmass carry the same label — the smallest position in it. The answer is the number of cells whose label is still their own position. Labels may need many sweeps to travel along a winding landmass: O((R·C)²).
O((R·C)²)O(R·C)1class Solution {
2 public int countLandmasses(int[][] grid) {
3 int rows = grid.length, cols = grid[0].length;
4 int[][] label = new int[rows][cols];
5 for (int r = 0; r < rows; r++) {
6 for (int c = 0; c < cols; c++) {
7 label[r][c] = grid[r][c] == 1 ? r * cols + c + 1 : 0;
8 }
9 }
10 boolean changed = true;
11 while (changed) {
12 changed = false;
13 for (int r = 0; r < rows; r++) {
14 for (int c = 0; c < cols; c++) {
15 if (label[r][c] == 0) continue;
16 if (r > 0 && label[r - 1][c] != 0 && label[r - 1][c] < label[r][c]) { label[r][c] = label[r - 1][c]; changed = true; }
17 if (r < rows - 1 && label[r + 1][c] != 0 && label[r + 1][c] < label[r][c]) { label[r][c] = label[r + 1][c]; changed = true; }
18 if (c > 0 && label[r][c - 1] != 0 && label[r][c - 1] < label[r][c]) { label[r][c] = label[r][c - 1]; changed = true; }
19 if (c < cols - 1 && label[r][c + 1] != 0 && label[r][c + 1] < label[r][c]) { label[r][c] = label[r][c + 1]; changed = true; }
20 }
21 }
22 }
23 int count = 0;
24 for (int r = 0; r < rows; r++) {
25 for (int c = 0; c < cols; c++) {
26 if (label[r][c] == r * cols + c + 1) count++;
27 }
28 }
29 return count;
30 }
31}Optimal — One Breadth-First Flood per Unvisited Land Cell
OptimalScan the grid. Whenever you find a land cell that has not been visited, you have discovered a new landmass: increase the count and flood-fill it with a breadth-first search, marking every connected land cell as visited so that it is never counted again. Each cell is visited once by the scan and at most once by a flood: O(R·C).
O(R·C)O(R·C)1class Solution {
2 public int countLandmasses(int[][] grid) {
3 int rows = grid.length, cols = grid[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 boolean[][] seen = new boolean[rows][cols];
7 int count = 0;
8 for (int r = 0; r < rows; r++) {
9 for (int c = 0; c < cols; c++) {
10 if (grid[r][c] == 1 && !seen[r][c]) {
11 count++;
12 seen[r][c] = true;
13 Deque<int[]> queue = new ArrayDeque<>();
14 queue.add(new int[]{r, c});
15 while (!queue.isEmpty()) {
16 int[] cell = queue.poll();
17 for (int d = 0; d < 4; d++) {
18 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
19 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !seen[nr][nc]) {
20 seen[nr][nc] = true;
21 queue.add(new int[]{nr, nc});
22 }
23 }
24 }
25 }
26 }
27 }
28 return count;
29 }
30}