Islands Rising One Cell at a Time
Solve this ProblemA map starts as all water. Cells are then turned into land one at a time. After each change, report the number of islands (groups of land cells connected through shared sides).
Recounting with a flood fill after every change works but repeats a lot of work. Union-find keeps the islands as groups and updates the count locally: a new cell adds an island and every merge with a neighbouring island removes one.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 8; the map starts as all water - ◆
positions lists at most 12 cells [row, column]; the cells are turned into land one after another, in the given order (a cell may appear again; nothing changes then) - ◆
An island is a group of land cells connected through shared sides (up, down, left, right) - ◆
Return an array whose entry k is the number of islands right after the k-th cell has been turned into land
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recount All Islands After Every New Cell
BruteKeep the map and turn each position into land in turn. After every change, count the islands from scratch with a flood fill over the whole map (scan for unvisited land, count one island, flood it). Each recount costs O(R·C), so k positions cost O(k · R·C).
O(k · R·C)O(R·C)1class Solution {
2 private int countIslands(boolean[][] land) {
3 int rows = land.length, cols = land[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 islands = 0;
8 for (int r = 0; r < rows; r++) {
9 for (int c = 0; c < cols; c++) {
10 if (!land[r][c] || seen[r][c]) continue;
11 islands++;
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 && land[nr][nc] && !seen[nr][nc]) {
20 seen[nr][nc] = true;
21 queue.add(new int[]{nr, nc});
22 }
23 }
24 }
25 }
26 }
27 return islands;
28 }
29
30 public int[] islandCounts(int rows, int cols, int[][] positions) {
31 boolean[][] land = new boolean[rows][cols];
32 int[] answers = new int[positions.length];
33 for (int k = 0; k < positions.length; k++) {
34 land[positions[k][0]][positions[k][1]] = true;
35 answers[k] = countIslands(land);
36 }
37 return answers;
38 }
39}Optimal — Union-Find: Update the Count When a Cell Is Added
OptimalKeep a union-find structure over the cells and a running island counter. When a new land cell appears (and it was not land already), it starts as a new island: counter + 1. Then look at its four neighbours: for each one that is land and is in a DIFFERENT island (different root), merge the two islands and reduce the counter by 1. The counter after each step is the answer for that step. Nothing is recounted, so every step costs almost constant time.
O(k · α(R·C))O(R·C)1class Solution {
2 private int find(int[] parent, int x) {
3 while (parent[x] != x) {
4 parent[x] = parent[parent[x]];
5 x = parent[x];
6 }
7 return x;
8 }
9
10 public int[] islandCounts(int rows, int cols, int[][] positions) {
11 int[] parent = new int[rows * cols];
12 boolean[] isLand = new boolean[rows * cols];
13 for (int i = 0; i < parent.length; i++) parent[i] = i;
14 int[] dr = {1, -1, 0, 0};
15 int[] dc = {0, 0, 1, -1};
16 int islands = 0;
17 int[] answers = new int[positions.length];
18 for (int k = 0; k < positions.length; k++) {
19 int r = positions[k][0], c = positions[k][1];
20 int id = r * cols + c;
21 if (!isLand[id]) {
22 isLand[id] = true;
23 islands++;
24 for (int d = 0; d < 4; d++) {
25 int nr = r + dr[d], nc = c + dc[d];
26 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || !isLand[nr * cols + nc]) continue;
27 int a = find(parent, id), b = find(parent, nr * cols + nc);
28 if (a != b) {
29 parent[a] = b;
30 islands--;
31 }
32 }
33 }
34 answers[k] = islands;
35 }
36 return answers;
37 }
38}