827. Making A Large Island
Asked at Uber, TikTok, Anduril
Difficulty
Hard
Time
O(n^2)
Space
O(n^2)
Pattern
Array
Companies
3
Problem
You are given an n x n grid of 0s and 1s. A 1 is land, a 0 is water. An island is a group of 1s that are connected side-by-side (up, down, left, right — not diagonally).
You may flip at most one 0 into a 1. After that single change (or no change at all), return the size of the largest island in the grid. Size means the number of 1 cells in the island.
If the grid has no 0 at all, you cannot make any change, so the answer is the whole grid: n * n.
One flip can join islands
Constraints
- ●
n == grid.length - ●
n == grid[i].length - ●
1 <= n <= 500 - ●
grid[i][j] is either 0 or 1
Examples
grid = [[1,0],[0,1]]3grid = [[1,1],[1,0]]4grid = [[1,1],[1,1]]4Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Uber | Hard | View all Uber questions → |
| TikTok | Hard | View all TikTok questions → |
| Anduril | Hard | View all Anduril questions → |
How to Think About It
Brute force: for every 0 cell, temporarily set it to 1, run BFS/DFS to find the largest island, then revert. Track the maximum.
Optimize by precomputing island sizes. Use Union-Find or BFS to label each island and record its size.
For each 0 cell, check its 4 neighbors. Sum the sizes of distinct neighboring islands. Add 1 for the cell itself.
Use Union-Find with path compression and union by size to efficiently merge and query island sizes.
The answer is the maximum of (sum of distinct neighbor island sizes + 1) across all 0 cells. If no 0 exists, the answer is n*n.
Optimal Approach
First, label each connected component of 1s using BFS or Union-Find, recording the size of each component. Then, iterate over every 0 cell. For each 0, look at its 4 neighbors. Collect the sizes of distinct neighboring components (use a set of component IDs to avoid duplicates). The potential island size if we flip this 0 is the sum of those sizes plus 1. Track the global maximum. If there are no 0 cells, the answer is n*n. Union-Find with path compression and union by size gives near O(1) amortized operations.
Label islands, then test each 0
What Trips People Up in Real Interviews
Ask whether changing a 0 is optional or required (it is optional — you may choose not to change any).
Clarify that diagonals do not count for connectivity.
Walk through the brute force first, then explain the precomputation optimization.
Be careful to avoid double-counting islands when a 0 cell borders the same island from multiple sides — use a hash set of island IDs.
Discuss time complexity: O(n^2) for Union-Find, O(n^2) for the final pass.
Solution Code
O(n^2) timeclass Solution:
def largestIsland(self, grid):
n = len(grid)
parent = list(range(n * n))
size = [1] * (n * n)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb: return
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
for dr, dc in [(0,1),(1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
union(r * n + c, nr * n + nc)
max_size = max(size) if any(grid[r][c] for r in range(n) for c in range(n)) else 0
for r in range(n):
for c in range(n):
if grid[r][c] == 0:
seen = set()
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:
seen.add(find(nr * n + nc))
total = 1 + sum(size[rid] for rid in seen)
max_size = max(max_size, total)
return max_size if max_size > 0 else n * nFrequently Asked Questions
What is the Making A Large Island problem?
You are given an n x n binary matrix grid where 1 represents land and 0 represents water. You can change at most one 0 to a 1. After the change, find the size of the largest island (connected group of 1s). An island is formed by connecting adjacent cells horizontally or vertically.
How do you solve Making A Large Island?
The optimal approach runs in O(n^2) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Making A Large Island?
Making A Large Island is asked at Uber, TikTok, Anduril. It is a hard difficulty problem.
What are common mistakes on Making A Large Island?
- Ask whether changing a 0 is optional or required (it is optional — you may choose not to change any).
- Clarify that diagonals do not count for connectivity.
- Walk through the brute force first, then explain the precomputation optimization.
- Be careful to avoid double-counting islands when a 0 cell borders the same island from multiple sides — use a hash set of island IDs.
- Discuss time complexity: O(n^2) for Union-Find, O(n^2) for the final pass.