Making A Large Island
Asked at Uber
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | HARD | View all Uber 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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Making A Large Island?
Making A Large Island is asked at Uber. 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.