Making A Large Island
Making A Large Island is a hard graphs problem solved with the connected components pattern.
The best approach, optimal (label islands, then try each water cell), runs in O(n²) time and O(n²) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flip each water cell and flood fill) up.
Problem
You are given an n x n binary grid where 1 is land and 0 is water. An island is a group of land cells connected up, down, left or right.
You may turn at most one water cell into land. Return the size (number of cells) of the largest island the grid can have after that change.
Examples
Example 1
- Input
grid = [[1,1,0],[0,0,1],[1,0,1]]- Output
5- Why
- Turning the cell at [1,1] into land joins the island of size 2 at the top with the island of size 2 on the right: 2 + 2 + 1 = 5.
Example 2
- Input
grid = [[1,1],[1,1]]- Output
4- Why
- There is no water to flip, so the answer is the whole grid.
Example 3
- Input
grid = [[0,0],[0,0]]- Output
1- Why
- Flipping any one cell creates an island of size 1.
Constraints
n == grid.length == grid[i].length1 <= n <= 500grid[i][j]is0(water) or1(land).- You may change at most one
0to1; changing none is also allowed.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (flip each water cell and flood fill) | O(n⁴) | O(n²) |
| Optimal (label islands, then try each water cell) | O(n²) | O(n²) |
1Brute force (flip each water cell and flood fill)
O(n⁴)Up to n² water cells, each followed by a BFS over up to n² cells.O(n²)The visited array and queue of one BFS.For every water cell, pretend it is land and run a BFS from it to measure the island it now belongs to. The best of these is the answer; if there is no water, the whole grid is already one island.
- For each cell with grid[i][j] == 0: set it to 1, BFS from it counting cells, set it back to 0.
- Track the largest count.
- If no water cell was found, return n · n.
class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length, best = 0;
boolean hasWater = false;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) continue;
hasWater = true;
grid[i][j] = 1;
best = Math.max(best, measure(grid, i, j));
grid[i][j] = 0;
}
return hasWater ? best : n * n;
}
private int measure(int[][] grid, int sr, int sc) {
int n = grid.length, size = 0;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
boolean[][] seen = new boolean[n][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] { sr, sc });
seen[sr][sc] = true;
while (!q.isEmpty()) {
int[] c = q.poll();
size++;
for (int[] d : dirs) {
int x = c[0] + d[0], y = c[1] + d[1];
if (x >= 0 && y >= 0 && x < n && y < n && !seen[x][y] && grid[x][y] == 1) {
seen[x][y] = true;
q.add(new int[] { x, y });
}
}
}
return size;
}
}class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def measure(sr: int, sc: int) -> int:
seen = [[False] * n for _ in range(n)]
seen[sr][sc] = True
q = deque([(sr, sc)])
size = 0
while q:
r, c = q.popleft()
size += 1
for dr, dc in dirs:
x, y = r + dr, c + dc
if 0 <= x < n and 0 <= y < n and not seen[x][y] and grid[x][y] == 1:
seen[x][y] = True
q.append((x, y))
return size
best, has_water = 0, False
for i in range(n):
for j in range(n):
if grid[i][j] != 0:
continue
has_water = True
grid[i][j] = 1
best = max(best, measure(i, j))
grid[i][j] = 0
return best if has_water else n * nclass Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size(), best = 0;
bool hasWater = false;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) continue;
hasWater = true;
grid[i][j] = 1;
best = max(best, measure(grid, i, j));
grid[i][j] = 0;
}
return hasWater ? best : n * n;
}
private:
int measure(vector<vector<int>>& grid, int sr, int sc) {
static const int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int n = grid.size(), size = 0;
vector<vector<bool>> seen(n, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push({sr, sc});
seen[sr][sc] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
size++;
for (auto& d : dirs) {
int x = r + d[0], y = c + d[1];
if (x >= 0 && y >= 0 && x < n && y < n && !seen[x][y] && grid[x][y] == 1) {
seen[x][y] = true;
q.push({x, y});
}
}
}
return size;
}
};function largestIsland(grid) {
const n = grid.length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function measure(sr, sc) {
const seen = Array.from({ length: n }, () => new Array(n).fill(false));
seen[sr][sc] = true;
const q = [[sr, sc]];
for (let head = 0; head < q.length; head++) {
const [r, c] = q[head];
for (const [dr, dc] of dirs) {
const x = r + dr, y = c + dc;
if (x >= 0 && y >= 0 && x < n && y < n && !seen[x][y] && grid[x][y] === 1) {
seen[x][y] = true;
q.push([x, y]);
}
}
}
return q.length;
}
let best = 0, hasWater = false;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) {
if (grid[i][j] !== 0) continue;
hasWater = true;
grid[i][j] = 1;
best = Math.max(best, measure(i, j));
grid[i][j] = 0;
}
return hasWater ? best : n * n;
}2Optimal (label islands, then try each water cell)
O(n²)Each cell is labelled once and each water cell looks at 4 neighbours.O(n²)The id-to-size map and the flood-fill stack. The grid itself is reused for the ids.First pass: flood fill every island once, writing an id (2, 3, 4, …) into its cells and storing the island's size under that id. Second pass: for each water cell, collect the distinct ids among its four neighbours and add up their sizes plus 1 for the cell itself. The largest such total (or the largest island when there is no water) is the answer.
- id = 2; for each land cell still marked 1, flood fill it with id, store size[id], id++.
- best = largest size (n · n if there is no water, since then one island fills the grid).
- For each 0 cell: seen = distinct neighbour ids; total = 1 + sum of size[id] for id in seen; best = max(best, total).
- Return best.
class Solution {
public int largestIsland(int[][] grid) {
int n = grid.length;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
List<Integer> size = new ArrayList<>(List.of(0, 0));
int best = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) continue;
int id = size.size(), count = 0;
ArrayDeque<int[]> st = new ArrayDeque<>();
st.push(new int[] { i, j });
grid[i][j] = id;
while (!st.isEmpty()) {
int[] c = st.pop();
count++;
for (int[] d : dirs) {
int x = c[0] + d[0], y = c[1] + d[1];
if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] == 1) {
grid[x][y] = id;
st.push(new int[] { x, y });
}
}
}
size.add(count);
best = Math.max(best, count);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) continue;
Set<Integer> seen = new HashSet<>();
int total = 1;
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] > 1 && seen.add(grid[x][y]))
total += size.get(grid[x][y]);
}
best = Math.max(best, total);
}
return best;
}
}class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
size = [0, 0]
best = 0
for i in range(n):
for j in range(n):
if grid[i][j] != 1:
continue
island = len(size)
grid[i][j] = island
stack = [(i, j)]
count = 0
while stack:
r, c = stack.pop()
count += 1
for dr, dc in dirs:
x, y = r + dr, c + dc
if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:
grid[x][y] = island
stack.append((x, y))
size.append(count)
best = max(best, count)
for i in range(n):
for j in range(n):
if grid[i][j] != 0:
continue
seen = set()
for dr, dc in dirs:
x, y = i + dr, j + dc
if 0 <= x < n and 0 <= y < n and grid[x][y] > 1:
seen.add(grid[x][y])
best = max(best, 1 + sum(size[k] for k in seen))
return bestclass Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size(), best = 0;
int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
vector<int> size = {0, 0};
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) continue;
int id = size.size(), count = 0;
vector<pair<int, int>> st = {{i, j}};
grid[i][j] = id;
while (!st.empty()) {
auto [r, c] = st.back();
st.pop_back();
count++;
for (auto& d : dirs) {
int x = r + d[0], y = c + d[1];
if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] == 1) {
grid[x][y] = id;
st.push_back({x, y});
}
}
}
size.push_back(count);
best = max(best, count);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) continue;
int ids[4], k = 0, total = 1;
for (auto& d : dirs) {
int x = i + d[0], y = j + d[1];
if (x < 0 || y < 0 || x >= n || y >= n || grid[x][y] <= 1) continue;
int id = grid[x][y];
bool dup = false;
for (int t = 0; t < k; t++) dup = dup || ids[t] == id;
if (!dup) { ids[k++] = id; total += size[id]; }
}
best = max(best, total);
}
return best;
}
};function largestIsland(grid) {
const n = grid.length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const size = [0, 0];
let best = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) {
if (grid[i][j] !== 1) continue;
const id = size.length;
let count = 0;
const st = [[i, j]];
grid[i][j] = id;
while (st.length > 0) {
const [r, c] = st.pop();
count++;
for (const [dr, dc] of dirs) {
const x = r + dr, y = c + dc;
if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] === 1) {
grid[x][y] = id;
st.push([x, y]);
}
}
}
size.push(count);
best = Math.max(best, count);
}
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) {
if (grid[i][j] !== 0) continue;
const seen = new Set();
let total = 1;
for (const [dr, dc] of dirs) {
const x = i + dr, y = j + dc;
if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] > 1 && !seen.has(grid[x][y])) {
seen.add(grid[x][y]);
total += size[grid[x][y]];
}
}
best = Math.max(best, total);
}
return best;
}Edge cases to test
- No water at all (answer n²)
- No land at all (answer 1)
- A water cell touching the same island from two or more sides (count that island once)
- A 1 x 1 grid
Hints
Hint 1
Trying every water cell and re-measuring the island from scratch works, but repeats a lot of the same flood fills.
Hint 2
Measure each existing island once. Give every island an id and remember its size.
Hint 3
For a water cell, the new island is 1 plus the sizes of the distinct island ids among its four neighbours. Use a small set so an island touching two sides is not counted twice.
FAQ
What is the best time complexity for Making A Large Island?
Optimal (label islands, then try each water cell) runs in O(n²) time and O(n²) extra space. Each cell is labelled once and each water cell looks at 4 neighbours.
Which pattern does Making A Large Island use?
It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.
Is there a brute force solution for Making A Large Island?
Yes. Brute force (flip each water cell and flood fill) takes O(n⁴) time and O(n²) space. For every water cell, pretend it is land and run a BFS from it to measure the island it now belongs to.
Which edge cases should I test for Making A Large Island?
No water at all (answer n²); No land at all (answer 1); A water cell touching the same island from two or more sides (count that island once); A 1 x 1 grid.