Build the Biggest Island With One Extra Cell
Solve this ProblemYou are given a map of land (1) and water (0). You may turn at most one water cell into land. What is the size of the largest island you can get?
Turning a water cell into land merges every island that touches it. If the islands are labelled and their sizes are known in advance, the result for one water cell is 1 plus the sizes of the different neighbouring islands, so no repeated flood fills are needed.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 8; grid[r][c] is 1 (land) or 0 (water) - ◆
An island is a group of land cells connected through shared sides (up, down, left, right) - ◆
You may change at most one water cell into land - ◆
Return the size (number of cells) of the largest island that can be obtained
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Turning Every Water Cell Into Land
BruteFirst compute the largest island of the map as it is (this matters when there is no water). Then for every water cell in turn: turn it into land, find the largest island of the whole map with a flood fill, remember the maximum, and turn it back into water. There are up to R·C water cells and each check costs O(R·C).
O((R·C)²)O(R·C)1class Solution {
2 private int largest(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 best = 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]) continue;
11 int size = 0;
12 Deque<int[]> queue = new ArrayDeque<>();
13 seen[r][c] = true;
14 queue.add(new int[]{r, c});
15 while (!queue.isEmpty()) {
16 int[] cell = queue.poll();
17 size++;
18 for (int d = 0; d < 4; d++) {
19 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
20 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !seen[nr][nc]) {
21 seen[nr][nc] = true;
22 queue.add(new int[]{nr, nc});
23 }
24 }
25 }
26 best = Math.max(best, size);
27 }
28 }
29 return best;
30 }
31
32 public int biggestIsland(int[][] grid) {
33 int rows = grid.length, cols = grid[0].length;
34 int best = largest(grid);
35 for (int r = 0; r < rows; r++) {
36 for (int c = 0; c < cols; c++) {
37 if (grid[r][c] == 0) {
38 grid[r][c] = 1;
39 best = Math.max(best, largest(grid));
40 grid[r][c] = 0;
41 }
42 }
43 }
44 return best;
45 }
46}Optimal — Label the Islands Once, Then Try Each Water Cell
OptimalFlood-fill the map once, giving every island an identification number and recording its size. Then for every water cell, look at its four neighbours: the island obtained by turning this cell into land has size 1 plus the sizes of the DIFFERENT islands among the neighbours (an island touching the cell on two sides must be counted once). The answer is the largest such total, or the largest existing island if there is no water. Every cell is looked at a constant number of times.
O(R·C)O(R·C)1class Solution {
2 public int biggestIsland(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 int[][] label = new int[rows][cols];
7 int[] size = new int[rows * cols + 2];
8 int islands = 0;
9 int best = 0;
10 for (int r = 0; r < rows; r++) {
11 for (int c = 0; c < cols; c++) {
12 if (grid[r][c] != 1 || label[r][c] != 0) continue;
13 islands++;
14 label[r][c] = islands;
15 Deque<int[]> queue = new ArrayDeque<>();
16 queue.add(new int[]{r, c});
17 while (!queue.isEmpty()) {
18 int[] cell = queue.poll();
19 size[islands]++;
20 for (int d = 0; d < 4; d++) {
21 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
22 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && label[nr][nc] == 0) {
23 label[nr][nc] = islands;
24 queue.add(new int[]{nr, nc});
25 }
26 }
27 }
28 best = Math.max(best, size[islands]);
29 }
30 }
31 for (int r = 0; r < rows; r++) {
32 for (int c = 0; c < cols; c++) {
33 if (grid[r][c] != 0) continue;
34 int total = 1;
35 int[] counted = new int[4];
36 for (int d = 0; d < 4; d++) {
37 int nr = r + dr[d], nc = c + dc[d];
38 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || label[nr][nc] == 0) continue;
39 int id = label[nr][nc];
40 boolean already = false;
41 for (int t = 0; t < d; t++) {
42 if (counted[t] == id) already = true;
43 }
44 counted[d] = id;
45 if (!already) total += size[id];
46 }
47 best = Math.max(best, total);
48 }
49 }
50 return best;
51 }
52}