Making a large island
MetaThe problem
Given an n x n binary matrix grid, it is allowed to change at most one 0 to 1. A group of connected 1s forms an island, where two 1s are connected if they share one of their sides.
Return the size of the largest island in the grid after applying this operation.
Input: grid = [[1,0],[0,1]] Output: 3 Explanation: We change any one 0 to 1 and connect two 1s, then we get an island with maximum area = 3.
Input: grid = [[1,1],[1,1]] **Output: **4 Explanation: The largest island already exists with size 4.
Input: grid = [[1,1],[1,0]]
- 1 <= n <= 500
- 0 <= grid[i][j] <= 1
cpp
class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
}
};java
class Solution {
public int largestIsland(int[][] grid) {
}
}python
class Solution:
def largestIsland(self, grid):javascript
class Solution {
largestIsland(grid) {
}
}csharp
public class Solution
{
public int LargestIsland(int[][] grid)
{
}
}go
func largestIsland(grid [][]int) int {
}Stuck? Show a way to structure it+
- 01Restate the objective and identify the key invariant
- 02Develop the component labeling and one flip approach step by step
- 03Walk through a small adversarial example
- 04Cover boundary conditions before coding
- 05State time and space Big-O and explain the trade-off
Reference answer
Then expect these follow-ups
How would the approach change for streaming input?
Tests: constraint adaptation
Which boundary case is most likely to break an implementation?
Tests: implementation extension
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question