PPractick

The problem

A land-reclamation project can fill at most one water cell (turn a 0 into 1) on an n × n map. What's the largest island (4-directionally connected land) that can result? Trying every flip and re-running a flood fill is O(n⁴). Instead:

1. Label every existing island once with an ID and record its size.
2. For each water cell, the island formed by filling it has size 1 plus the sizes of the distinct islands around it, since the same island may touch it on several sides.
3. Also consider making no flip at all.

Example: [[1,0], [0,1]] → 3.

Function signature

int largestIsland(vector<vector<int>> grid);  // n x n of 0/1

Test cases

Input	Output	Explanation
[[1,0],[0,1]]	3	Filling either 0 joins both islands
[[1,1],[1,0]]	4
[[1,1],[1,1]]	4	Nothing to fill
[[1,0,1],[0,0,0],[1,0,1]]	3	An edge-centre cell joins two corners
[[0,0],[0,0]]	1	Only the filled cell

(Confirm: at most one cell is changed; connectivity is 4-directional.)

How interviewers phrase it

• "You may change at most one 0 to 1. Return the size of the largest island in the grid after applying this operation" (LeetCode 827).

Clarifying questions to ask

1. At most one flip, so zero flips is allowed? (Yes: an all-land grid is valid.)
2. 4-directional? (Yes.)
3. How large? (n up to 500, so an O(n²) method is needed.)

Follow-ups to expect

1. "Why label islands first?"
2. "Why track distinct IDs?"
3. "What if the grid has no water?"
4. "DSU alternative?"
5. "Complexity?"

Related questions

• Flood fill algorithm Medium
• Surrounded Regions Medium
• Number of enclaves Medium
• Number of islands Medium
• Detect a cycle in an undirected graph Hard
• Bipartite Graph (DFS) Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in