Log inSign up
hardLeetCodeNot Started

Making A Large Island

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

An island is a 4-directionally connected group of 1s.

Return the size of the largest island in grid after applying this operation at most once.

---

### Examples

Example 1: ``text Input: grid = [[1, 0], [0, 1]] Output: 3 Explanation: Change one 0 to 1 at coordinate (0, 1) or (1, 0), joining two islands of size 1 into an island of size 3.

Example 2: ``text Input: grid = [[1, 1], [1, 0]] Output: 4 Explanation: Change the 0 at coordinate (1, 1) to 1. The whole grid becomes a single connected island of size 4.

Example 3: ``text Input: grid = [[1, 1], [1, 1]] Output: 4 Explanation: Can't change any 0 to 1, but the entire grid already forms an island of size 4.

---

### Constraints - n == grid.length - n == grid[i].length - 1 <= n <= 500 - grid[i][j] is either 0 or 1.

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 500
  • grid[i][j] is either 0 or 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Precompute component attributes using in-place matrix labeling.
  • Eliminate duplicate neighbor contributions using set deduplication.
  • Handle corner cases where no cell changes can be made (full grid).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Bridge connecting separate components by flipping at most one element
  • Finding maximal component size after a single edge insertion or cell change
  • Grouping components with persistent identifiers

Algorithmic Decision Tree:

  • Phase 1: DFS flood-fill each component with unique ID id = 2, 3, ... and record area[id].
  • Phase 2: For every 0 cell, sum = 1 + sum(area[id]) for all unique neighbor IDs.
  • Result is max(existing_max, best_flipped_sum).

Connected Patterns:

Number of IslandsMax Area of IslandSurrounded Regions

1. Flip Each Zero and Run Full Grid BFS

Intuition

Test every candidate zero. For each zero at (r, c), temporarily change grid[r][c] = 1. Launch a BFS flood-fill from (r, c) to calculate the connected island size, update the global maximum, and restore grid[r][c] = 0.

Algorithm

  1. Initialize maxIsland = initial island max.
  2. Loop r from 0 to n - 1 and c from 0 to n - 1:
  3. If grid[r][c] == 0:
  4. grid[r][c] = 1.
  5. Run BFS from (r, c) to find island size.
  6. maxIsland = max(maxIsland, size).
  7. grid[r][c] = 0 (backtrack).
  8. Return maxIsland.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6class Solution {
7 int getIslandSize(int sr, int sc, const std::vector<std::vector<int>>& grid) {
8 int n = grid.size();
9 std::vector<std::vector<bool>> visited(n, std::vector<bool>(n, false));
10 std::queue<std::pair<int, int>> q;
11
12 q.push({sr, sc});
13 visited[sr][sc] = true;
14 int size = 0;
15 int dr[] = {-1, 1, 0, 0};
16 int dc[] = {0, 0, -1, 1};
17
18 while (!q.empty()) {
19 auto [r, c] = q.front();
20 q.pop();
21 size++;
22
23 for (int k = 0; k < 4; ++k) {
24 int nr = r + dr[k], nc = c + dc[k];
25 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == 1) {
26 visited[nr][nc] = true;
27 q.push({nr, nc});
28 }
29 }
30 }
31 return size;
32 }
33public:
34 int largestIsland(std::vector<std::vector<int>>& grid) {
35 int n = grid.size();
36 int maxIsland = 0;
37 bool hasZero = false;
38
39 for (int r = 0; r < n; ++r) {
40 for (int c = 0; c < n; ++c) {
41 if (grid[r][c] == 0) {
42 hasZero = true;
43 grid[r][c] = 1;
44 maxIsland = std::max(maxIsland, getIslandSize(r, c, grid));
45 grid[r][c] = 0;
46 }
47 }
48 }
49
50 return hasZero ? maxIsland : n * n;
51 }
52};
53
54int main() {
55 Solution sol;
56 std::vector<std::vector<int>> grid = {{1, 0}, {0, 1}};
57 std::cout << "Brute force island: " << sol.largestIsland(grid) << " (Expected: 3)\n";
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(n^4)
  • Space complexity: O(n^2)

2. Disjoint Set Union (DSU / Union-Find) with Component Sizing

Intuition

DSU allows dynamic component grouping. First union all adjacent 1-cells and maintain component sizes in DSU. In pass 2, for each 0, query the roots of its 4 neighbors using a set. Sum the component sizes of unique roots plus 1 for the flipped zero.

Algorithm

  1. Initialize DSU of size n * n with component sizes initialized to 1.
  2. Loop r from 0 to n - 1, c from 0 to n - 1:
  3. If grid[r][c] == 1:
  4. Check right (r, c + 1) and down (r + 1, c); if 1, unite(r * n + c, nr * n + nc).
  5. Record maxIsland = maximum DSU component size among existing 1s.
  6. For each cell (r, c) where grid[r][c] == 0:
  7. Collect distinct roots of adjacent 1s into a set.
  8. sumSize = 1 + sum(dsu.size[root]).
  9. maxIsland = max(maxIsland, sumSize).
  10. Return maxIsland.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <algorithm>
5
6class DSU {
7public:
8 std::vector<int> parent, compSize;
9 int maxComp;
10 DSU(int n) : parent(n), compSize(n, 1), maxComp(0) {
11 for (int i = 0; i < n; ++i) parent[i] = i;
12 }
13 int find(int i) {
14 if (parent[i] == i) return i;
15 return parent[i] = find(parent[i]);
16 }
17 void unite(int i, int j) {
18 int rootI = find(i);
19 int rootJ = find(j);
20 if (rootI != rootJ) {
21 if (compSize[rootI] < compSize[rootJ]) std::swap(rootI, rootJ);
22 parent[rootJ] = rootI;
23 compSize[rootI] += compSize[rootJ];
24 maxComp = std::max(maxComp, compSize[rootI]);
25 }
26 }
27};
28
29class Solution {
30public:
31 int largestIsland(std::vector<std::vector<int>>& grid) {
32 int n = grid.size();
33 DSU dsu(n * n);
34 int dr[] = {-1, 1, 0, 0};
35 int dc[] = {0, 0, -1, 1};
36 bool hasZero = false;
37
38 for (int r = 0; r < n; ++r) {
39 for (int c = 0; c < n; ++c) {
40 if (grid[r][c] == 1) {
41 dsu.maxComp = std::max(dsu.maxComp, 1);
42 if (r + 1 < n && grid[r + 1][c] == 1) dsu.unite(r * n + c, (r + 1) * n + c);
43 if (c + 1 < n && grid[r][c + 1] == 1) dsu.unite(r * n + c, r * n + (c + 1));
44 } else {
45 hasZero = true;
46 }
47 }
48 }
49
50 if (!hasZero) return n * n;
51
52 int maxIsland = dsu.maxComp;
53 for (int r = 0; r < n; ++r) {
54 for (int c = 0; c < n; ++c) {
55 if (grid[r][c] == 0) {
56 std::unordered_set<int> uniqueRoots;
57 for (int k = 0; k < 4; ++k) {
58 int nr = r + dr[k], nc = c + dc[k];
59 if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1) {
60 uniqueRoots.insert(dsu.find(nr * n + nc));
61 }
62 }
63 int currentSize = 1;
64 for (int root : uniqueRoots) {
65 currentSize += dsu.compSize[root];
66 }
67 maxIsland = std::max(maxIsland, currentSize);
68 }
69 }
70 }
71
72 return maxIsland;
73 }
74};
75
76int main() {
77 Solution sol;
78 std::vector<std::vector<int>> grid = {{1, 0}, {0, 1}};
79 std::cout << "DSU island: " << sol.largestIsland(grid) << " (Expected: 3)\n";
80 return 0;
81}

Time & Space Complexity

  • Time complexity: O(n^2 * alpha(n^2))
  • Space complexity: O(n^2)

3. Canonical Island ID Labeling via DFS (Industry Benchmark)

Intuition

The universally preferred interview solution. By assigning a distinct integer ID (id >= 2) directly in grid[r][c] during a first-pass DFS flood-fill, we store the identity and area of every island in linear O(n2) time. In the second pass, we evaluate each 0 cell by querying its 4 neighbors: a set deduplicates neighboring island IDs, and their areas are summed with + 1. If no 0s exist, the answer is n * n.

Algorithm

  1. Initialize islandId = 2, areaMap mapping ID -> area.
  2. Pass 1: Loop r, c from 0 to n - 1:
  3. If grid[r][c] == 1:
  4. Run dfs(r, c, islandId) to flood-fill cells with islandId and count area.
  5. areaMap[islandId] = area.
  6. islandId++.
  7. Initialize maxIsland = max value in areaMap (or 0 if empty).
  8. Pass 2: Loop r, c from 0 to n - 1:
  9. If grid[r][c] == 0:
  10. Collect unique neighbor island IDs into a set.
  11. total = 1 + sum(areaMap[id] for id in set).
  12. maxIsland = max(maxIsland, total).
  13. If maxIsland == 0, return n * n (all 1s grid).
  14. Return maxIsland.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5#include <algorithm>
6
7class Solution {
8 int dfs(int r, int c, int islandId, std::vector<std::vector<int>>& grid) {
9 int n = grid.size();
10 grid[r][c] = islandId;
11 int area = 1;
12 int dr[] = {-1, 1, 0, 0};
13 int dc[] = {0, 0, -1, 1};
14
15 for (int k = 0; k < 4; ++k) {
16 int nr = r + dr[k], nc = c + dc[k];
17 if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1) {
18 area += dfs(nr, nc, islandId, grid);
19 }
20 }
21 return area;
22 }
23public:
24 int largestIsland(std::vector<std::vector<int>>& grid) {
25 int n = grid.size();
26 std::unordered_map<int, int> areaMap;
27 int islandId = 2;
28 int maxIsland = 0;
29
30 // Pass 1: Label each island with a unique ID >= 2
31 for (int r = 0; r < n; ++r) {
32 for (int c = 0; c < n; ++c) {
33 if (grid[r][c] == 1) {
34 int area = dfs(r, c, islandId, grid);
35 areaMap[islandId] = area;
36 maxIsland = std::max(maxIsland, area);
37 islandId++;
38 }
39 }
40 }
41
42 // If the grid was all 1s or already fully connected
43 if (maxIsland == n * n) return n * n;
44
45 int dr[] = {-1, 1, 0, 0};
46 int dc[] = {0, 0, -1, 1};
47
48 // Pass 2: Check each 0 as a potential bridge
49 for (int r = 0; r < n; ++r) {
50 for (int c = 0; c < n; ++c) {
51 if (grid[r][c] == 0) {
52 std::unordered_set<int> seenIds;
53 for (int k = 0; k < 4; ++k) {
54 int nr = r + dr[k], nc = c + dc[k];
55 if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] > 1) {
56 seenIds.insert(grid[nr][nc]);
57 }
58 }
59 int currentSize = 1; // The flipped 0
60 for (int id : seenIds) {
61 currentSize += areaMap[id];
62 }
63 maxIsland = std::max(maxIsland, currentSize);
64 }
65 }
66 }
67
68 return maxIsland;
69 }
70};
71
72int main() {
73 Solution sol;
74 std::vector<std::vector<int>> grid = {{1, 0}, {0, 1}};
75 std::cout << "Canonical largest island: " << sol.largestIsland(grid) << " (Expected: 3)\n";
76 return 0;
77}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n^2)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Flip Each Zero and Run Full BFSO(n^4)O(n^2)Tests each zero by flipping and re-traversing the entire grid.Repeated full BFS passes
2.Disjoint Set Union (DSU / Union-Find)O(n^2 * alpha(n^2))O(n^2)Unions adjacent 1s, bridges zeros using distinct neighbor root sets.Union-find lookups
3.Canonical Island ID Labeling via DFSOptimalO(n^2)O(n^2)Pass 1 paints island IDs and records areas; Pass 2 sums unique neighbor areas + 1.Grid scans

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not using a Set to deduplicate neighbor island IDs, double-counting an island that touches the 0 from multiple sides.

Pitfall 2:

Forgetting the grid-of-all-1s edge case, incorrectly returning 0 or 1 because no 0 was flipped.

Pitfall 3:

Using island IDs 0 or 1, which causes infinite loops during DFS flood fill.

Crucial Edge Cases to Validate:

  • Grid full of 1s (no 0s exist) — maxIsland initialized to area of the single island, returns n * n.
  • Grid full of 0s (no 1s exist) — Pass 1 creates no islands. Flipping any single 0 creates an island of size 1, returns 1.
  • 1x1 grid with [0] — Flipping the single 0 creates an island of size 1, returns 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the two-pass architecture clearly: 'Pass 1 paints each island with a unique ID and records its size; Pass 2 evaluates each 0 by summing unique neighbor island sizes + 1.'
  2. Emphasize the deduplication set: 'A set is essential because a single island may surround the 0 on multiple sides.'
  3. Point out the corner case: When there are no 0s in the matrix, return n * n.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must we use a Set to collect neighbor island IDs when inspecting a 0 cell in Pass 2?

2.Why do we start island IDs at 2 instead of 0 or 1?

3.What is the expected output if the grid initially contains ONLY 1s and NO 0s?

Back to DSA Sheet