Making a Large Island
Description
You are given an n × n binary matrix grid where each cell contains either 0 (water) or 1 (land). A group of 1s that are connected horizontally or vertically (4-directionally) forms an island.
You are allowed to change at most one 0 to 1.
Return the size of the largest island in the grid after applying this operation.
Key observations:
- You may choose not to flip any
0at all — the answer is simply the largest existing island. - Flipping a
0that sits between two (or more) separate islands can act as a bridge, merging them into one larger island. - The same island might be adjacent to the flipped cell from multiple directions (e.g., an L-shaped island wrapping around it). You must count each unique island only once.
- If the grid is already entirely
1s, no flip is possible and the answer isn × n.
Examples
Example 1
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation:
The grid has two islands: {(0,0)} of size 1 and {(1,1)} of size 1. They sit on opposite corners of the 2×2 grid.
We can flip either of the two 0 cells:
- Flip (0,1) to 1 → grid becomes [[1,1],[0,1]]. Cells (0,0), (0,1), (1,1) are all connected. Island size = 3.
- Flip (1,0) to 1 → grid becomes [[1,0],[1,1]]. Cells (0,0), (1,0), (1,1) are all connected. Island size = 3.
Both choices produce an island of size 3. The answer is 3.
Example 2
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation:
Three cells are already land: {(0,0), (0,1), (1,0)} form one island of size 3. Cell (1,1) is the only water cell.
Flipping (1,1) to 1 extends the existing island to all 4 cells. Island size = 4. The answer is 4.
Example 3
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation:
All cells are already 1. There is no 0 to flip. The entire grid is one island of size 4. The answer is 4.
Constraints
- n == grid.length
- n == grid[i].length
- 1 ≤ n ≤ 500
- grid[i][j] is either 0 or 1
Editorial
Brute Force
Intuition
The most direct approach: try every possible flip and measure the result.
For each cell that is 0, temporarily change it to 1, then scan the entire grid using BFS to find every island and record the size of the largest one. After recording, flip the cell back to 0 and move on to the next candidate.
Imagine you are a city planner deciding where to build a bridge. For each possible location you build the bridge, then send a surveyor to measure every landmass on the entire map from scratch. Once measured, you demolish the bridge and try the next location. Accurate — but extraordinarily wasteful.
The key problem is that each candidate flip triggers a complete rescan of the grid, even though only one cell changed.
Step-by-Step Explanation
Let us trace Example 1: grid = [[1,0],[0,1]], n = 2.
Step 1: Original grid:
1 0
0 1
We scan for 0 cells. Found two candidates: (0,1) and (1,0). We will try flipping each one and measure the result.
Step 2: Flip (0,1) to 1. Grid becomes:
1 1
0 1
Step 3: Full BFS scan of the grid. Start at (0,0) — land, unvisited. BFS explores (0,0) → neighbor (0,1) is land → explores → neighbor (1,1) is land → explores. Connected component = {(0,0), (0,1), (1,1)}, size = 3. Cell (1,0) is water. Largest island = 3.
Step 4: Record max_area = 3. Restore (0,1) back to 0.
Step 5: Flip (1,0) to 1. Grid becomes:
1 0
1 1
Step 6: Full BFS scan again — all 4 cells re-examined from scratch. BFS from (0,0): (0,0) → (1,0) is land → (1,1) is land. Component = {(0,0), (1,0), (1,1)}, size = 3. Cell (0,1) is water. Largest island = 3.
Step 7: max_area = max(3, 3) = 3. Restore (1,0) back to 0.
Step 8: All candidates tried. Final answer = 3. We performed 2 full grid scans, each inspecting all 4 cells — 8 total cell visits for a tiny 2×2 grid.
Brute Force — Flip Each 0 and Rescan the Entire Grid — Watch how the brute force flips each water cell to land, then performs a complete BFS scan of the entire grid to find the largest island. Every flip triggers a full rescan.
Algorithm
- Initialize
max_area = 0and a flaghas_zero = false. - For each cell
(i, j)in the grid:
a. Ifgrid[i][j] == 0:- Set
has_zero = true. - Temporarily set
grid[i][j] = 1. - Create a fresh
visitedmatrix of size n × n. - Scan every cell in the grid. For each unvisited land cell, run BFS to find its connected component size. Track the largest component found.
- Update
max_area = max(max_area, largest_component). - Restore
grid[i][j] = 0.
- Set
- If
has_zerois false (entire grid is 1s), returnn × n. - Return
max_area.
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
int maxArea = 0;
bool hasZero = false;
int dirs[5] = {-1, 0, 1, 0, -1};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
hasZero = true;
grid[i][j] = 1; // flip
// Full BFS to find largest island
vector<vector<bool>> visited(n, vector<bool>(n, false));
int best = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1 && !visited[r][c]) {
int size = 0;
queue<pair<int,int>> q;
q.push({r, c});
visited[r][c] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
size++;
for (int d = 0; d < 4; d++) {
int nx = x + dirs[d];
int ny = y + dirs[d + 1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n
&& grid[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
best = max(best, size);
}
}
}
maxArea = max(maxArea, best);
grid[i][j] = 0; // restore
}
}
}
return hasZero ? maxArea : n * n;
}
};from collections import deque
class Solution:
def largestIsland(self, grid: list[list[int]]) -> int:
n = len(grid)
max_area = 0
has_zero = False
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
has_zero = True
grid[i][j] = 1 # flip
# Full BFS to find the largest island
visited = [[False] * n for _ in range(n)]
best = 0
for r in range(n):
for c in range(n):
if grid[r][c] == 1 and not visited[r][c]:
size = 0
queue = deque([(r, c)])
visited[r][c] = True
while queue:
x, y = queue.popleft()
size += 1
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx, ny = x + dx, y + dy
if (0 <= nx < n and 0 <= ny < n
and grid[nx][ny] == 1
and not visited[nx][ny]):
visited[nx][ny] = True
queue.append((nx, ny))
best = max(best, size)
max_area = max(max_area, best)
grid[i][j] = 0 # restore
return max_area if has_zero else n * nimport java.util.*;
class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length;
int maxArea = 0;
boolean hasZero = false;
int[] dirs = {-1, 0, 1, 0, -1};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
hasZero = true;
grid[i][j] = 1; // flip
boolean[][] visited = new boolean[n][n];
int best = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1 && !visited[r][c]) {
int size = 0;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{r, c});
visited[r][c] = true;
while (!q.isEmpty()) {
int[] cell = q.poll();
size++;
for (int d = 0; d < 4; d++) {
int nx = cell[0] + dirs[d];
int ny = cell[1] + dirs[d + 1];
if (nx >= 0 && nx < n && ny >= 0 && ny < n
&& grid[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
best = Math.max(best, size);
}
}
}
maxArea = Math.max(maxArea, best);
grid[i][j] = 0; // restore
}
}
}
return hasZero ? maxArea : n * n;
}
}Complexity Analysis
Time Complexity: O(n⁴)
The grid has n² cells. In the worst case, roughly half are 0s, giving O(n²) candidates. For each candidate, we perform a full BFS over the entire n² grid. Total: O(n² × n²) = O(n⁴).
With n = 500: 500⁴ = 6.25 × 10¹⁰ operations. At ~10⁸ operations per second, that is over 600 seconds — well beyond any reasonable time limit.
Space Complexity: O(n²)
The visited matrix requires O(n²) space. The BFS queue can hold at most O(n²) cells in the worst case. The grid itself takes O(n²). Overall: O(n²).
Why This Approach Is Not Efficient
The brute force rescans the entire grid after every single flip. Think about what information we actually need when we flip a 0 to 1:
- Which islands are adjacent to this cell? (at most 4 neighbors)
- What are the sizes of those islands?
- Are any of those neighbors from the same island? (to avoid double-counting)
None of this information changes between different flip candidates — the islands themselves never change. Yet the brute force recomputes all island boundaries from scratch every time.
Key insight: If we could pre-compute every island's identity and size in a single pass, then evaluating each flip candidate would take O(1) instead of O(n²).
Here is the plan:
- Phase 1 (Label): Run DFS/BFS once over the entire grid. Assign each island a unique ID and record its size in a lookup table. This is O(n²) total.
- Phase 2 (Query): For each
0cell, look at its 4 neighbors, collect the unique island IDs among them, sum their pre-computed sizes, and add 1. Each query is O(1).
Total: O(n²) + O(n²) = O(n²) — a dramatic improvement from O(n⁴).
The critical detail is using a set to collect adjacent island IDs. Without it, an L-shaped island that touches the 0 cell from two directions would be counted twice, producing an incorrect (inflated) answer.
Optimal Approach - Island Labeling with Merge Query
Intuition
Think of it like a real-estate survey before construction:
Phase 1 — The Survey: Walk the entire map once. Every time you step onto unexplored land, mark every cell of that landmass with a unique color (island ID) and record the total area. After one full traversal you have a color-coded map and a table of areas.
Phase 2 — The What-If Analysis: For each water cell, ask: "If I built land here, which colored regions would I connect?" Just check the four neighbors. If the left neighbor is blue (island 3, area 12) and the bottom neighbor is green (island 7, area 5), the merged island would have area 12 + 5 + 1 = 18. This lookup is instant because sizes are pre-computed.
The tricky part: a water cell's neighbors might include the same island from multiple directions. For example, imagine a U-shaped island — the water cell at the bottom of the U has the same island touching it from both sides. Using a set of island IDs ensures each island is counted exactly once.
Edge cases:
- No zeros in the grid: The entire grid is already one island of size n². Return n².
- All zeros: The best we can do is flip one cell to get an island of size 1.
- One zero surrounded by one large island from all sides: The answer is (island size) + 1.
Step-by-Step Explanation
Let us trace Example 1: grid = [[1,0],[0,1]], n = 2.
Step 1: Initialize label grid (all zeros) and an empty island_size map. Set current_id = 0.
Step 2 (Phase 1 — Labeling): Scan (0,0): land and unlabeled. Increment current_id to 1. DFS from (0,0):
- Visit (0,0), assign label 1. Check neighbors: (0,1) = water, (1,0) = water. DFS complete.
- island_size[1] = 1.
Step 3: Continue scan. (0,1) = water, skip. (1,0) = water, skip. (1,1) = land and unlabeled. Increment current_id to 2. DFS from (1,1):
- Visit (1,1), assign label 2. Check neighbors: (0,1) = water, (1,0) = water. DFS complete.
- island_size[2] = 1.
Step 4: Labeling done.
- Label grid: [[1, 0], [0, 2]]
- island_size = {1: 1, 2: 1}
- Existing max island = max(1, 1) = 1
Step 5 (Phase 2 — Query): Check each 0 cell.
- Cell (0,1): left = (0,0) → island 1; down = (1,1) → island 2; up = OOB; right = OOB.
- Unique adjacent islands = {1, 2}.
- Potential size = island_size[1] + island_size[2] + 1 = 1 + 1 + 1 = 3.
Step 6: Check cell (1,0): up = (0,0) → island 1; right = (1,1) → island 2; down = OOB; left = OOB.
- Unique adjacent islands = {1, 2}.
- Potential size = 1 + 1 + 1 = 3.
Step 7: max_area = max(existing=1, flip(0,1)=3, flip(1,0)=3) = 3. Final answer = 3.
Total work: O(n²) for labeling + O(n²) for queries = O(n²). We never rescanned the full grid — just looked up pre-computed sizes in O(1) per query.
Optimal — Label Islands Then Query Each Zero Cell — Watch Phase 1 label each island with a unique ID and compute sizes. Then Phase 2 checks each water cell, looks up adjacent island sizes instantly, and computes the potential merged size.
Algorithm
- Initialize a label grid
island_id[n][n](all zeros) and a mapisland_size. - Set
current_id = 0. - Phase 1 — Label islands:
For each cell(i, j)wheregrid[i][j] == 1andisland_id[i][j] == 0:
a. Incrementcurrent_id.
b. Run iterative DFS from(i, j). For each cell visited:- Set
island_id[r][c] = current_id. - Increment
island_size[current_id].
- Set
- Compute
max_area = max(island_size.values())(handles the all-1s case). - Phase 2 — Query each zero cell:
For each cell(i, j)wheregrid[i][j] == 0:
a. Create an empty setadjacent.
b. For each of the 4 neighbors(ni, nj)that are within bounds:- If
island_id[ni][nj] > 0, add it toadjacent.
c. Computetotal = 1 + sum(island_size[id] for id in adjacent).
d. Updatemax_area = max(max_area, total).
- If
- Return
max_area.
Code
#include <vector>
#include <stack>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> islandId(n, vector<int>(n, 0));
unordered_map<int, int> islandSize;
int currentId = 0;
int dirs[5] = {-1, 0, 1, 0, -1};
// Phase 1: Label each island with a unique ID
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && islandId[i][j] == 0) {
currentId++;
int sz = 0;
stack<pair<int,int>> stk;
stk.push({i, j});
islandId[i][j] = currentId;
while (!stk.empty()) {
auto [r, c] = stk.top(); stk.pop();
sz++;
for (int d = 0; d < 4; d++) {
int nr = r + dirs[d], nc = c + dirs[d + 1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& grid[nr][nc] == 1 && islandId[nr][nc] == 0) {
islandId[nr][nc] = currentId;
stk.push({nr, nc});
}
}
}
islandSize[currentId] = sz;
}
}
}
int maxArea = 0;
for (auto& [id, sz] : islandSize) maxArea = max(maxArea, sz);
// Phase 2: Try flipping each 0 cell
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
unordered_set<int> adj;
for (int d = 0; d < 4; d++) {
int nr = i + dirs[d], nc = j + dirs[d + 1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& islandId[nr][nc] > 0) {
adj.insert(islandId[nr][nc]);
}
}
int total = 1;
for (int id : adj) total += islandSize[id];
maxArea = max(maxArea, total);
}
}
}
return maxArea;
}
};class Solution:
def largestIsland(self, grid: list[list[int]]) -> int:
n = len(grid)
island_id = [[0] * n for _ in range(n)]
island_size: dict[int, int] = {}
current_id = 0
# Phase 1: Label each island with a unique ID
for i in range(n):
for j in range(n):
if grid[i][j] == 1 and island_id[i][j] == 0:
current_id += 1
size = 0
stack = [(i, j)]
island_id[i][j] = current_id
while stack:
r, c = stack.pop()
size += 1
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if (0 <= nr < n and 0 <= nc < n
and grid[nr][nc] == 1
and island_id[nr][nc] == 0):
island_id[nr][nc] = current_id
stack.append((nr, nc))
island_size[current_id] = size
max_area = max(island_size.values()) if island_size else 0
# Phase 2: Try flipping each 0 cell
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
adjacent = set()
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = i + dr, j + dc
if (0 <= nr < n and 0 <= nc < n
and island_id[nr][nc] > 0):
adjacent.add(island_id[nr][nc])
total = 1 + sum(island_size[aid] for aid in adjacent)
max_area = max(max_area, total)
return max_areaimport java.util.*;
class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length;
int[][] islandId = new int[n][n];
Map<Integer, Integer> islandSize = new HashMap<>();
int currentId = 0;
int[] dirs = {-1, 0, 1, 0, -1};
// Phase 1: Label each island with a unique ID
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && islandId[i][j] == 0) {
currentId++;
int size = 0;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{i, j});
islandId[i][j] = currentId;
while (!stack.isEmpty()) {
int[] cell = stack.pop();
size++;
for (int d = 0; d < 4; d++) {
int nr = cell[0] + dirs[d];
int nc = cell[1] + dirs[d + 1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& grid[nr][nc] == 1 && islandId[nr][nc] == 0) {
islandId[nr][nc] = currentId;
stack.push(new int[]{nr, nc});
}
}
}
islandSize.put(currentId, size);
}
}
}
int maxArea = islandSize.isEmpty() ? 0
: Collections.max(islandSize.values());
// Phase 2: Try flipping each 0 cell
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
Set<Integer> adjacent = new HashSet<>();
for (int d = 0; d < 4; d++) {
int nr = i + dirs[d], nc = j + dirs[d + 1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& islandId[nr][nc] > 0) {
adjacent.add(islandId[nr][nc]);
}
}
int total = 1;
for (int id : adjacent) total += islandSize.get(id);
maxArea = Math.max(maxArea, total);
}
}
}
return maxArea;
}
}Complexity Analysis
Time Complexity: O(n²)
Phase 1 (labeling): We iterate over all n² cells. Each cell is visited by DFS at most once (once labeled, it is never revisited). Total DFS work across all islands = O(n²).
Phase 2 (querying): We iterate over all n² cells. For each 0 cell, we check exactly 4 neighbors — O(1) per cell. Building the set and summing sizes is O(1) since the set has at most 4 elements.
Overall: O(n²) + O(n²) = O(n²).
With n = 500, this is 2 × 250,000 = 500,000 operations — nearly instant.
Space Complexity: O(n²)
The label grid island_id requires O(n²). The island_size map stores at most O(n²) entries (one per island, and there can be up to n²/2 islands in a checkerboard pattern). The DFS stack can grow to O(n²) in the worst case (snake-shaped island). Overall: O(n²).