Problem
You are given an n x n
binary matrix grid
. You are allowed to change at most one 0
to be 1
.
Return the size of the largest island in grid
after applying this operation.
An island is a 4-directionally connected group of 1
s.
Examples
Example 1:
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j]
is either0
or1
.
Solution
Method 1 - Using DFS + Hashing
This problem will be similar to Number of Islands. Here is the approach:
- Identify Islands: Traverse the grid to find and label all existing islands. Use DFS or BFS to calculate the size of each island. Store each island’s size in a dictionary.
- Track Connectivity: Use a parent array to track the root of each cell in every island. Also, mark cells (
0
s) that, when flipped to1
, can connect two or more islands. - Simulate Flipping: For each
0
, calculate the potential island size if that0
is flipped to1
by summing the sizes of all unique islands it would connect. - Calculate the Largest Island: Compare the size of the islands after each possible flip to find the maximum size.
Code
Java
public class Solution {
private int n;
private final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // Down, Up, Right, Left
public int largestIsland(int[][] grid) {
n = grid.length;
int[] size = new int[n * n + 2];
int id = 2; // Start from 2 because 1s are already used
int maxSize = 0;
// First pass: label every island with a unique id and calculate their size
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
size[id] = dfs(grid, i, j, id);
maxSize = Math.max(maxSize, size[id]);
id++;
}
}
}
// Second pass: check potential size by flipping each 0 to 1
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
Set<Integer> seenIds = new HashSet<>();
int potentialSize = 1; // The flipped cell itself
for (int[] dir : dirs) {
int newRow = i + dir[0];
int newCol = j + dir[1];
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] != 0) {
int islandId = grid[newRow][newCol];
if (seenIds.add(islandId)) {
potentialSize += size[islandId];
}
}
}
maxSize = Math.max(maxSize, potentialSize);
}
}
}
return maxSize;
}
private int dfs(int[][] grid, int x, int y, int id) {
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) return 0;
grid[x][y] = id;
int size = 1;
for (int[] dir : dirs) {
size += dfs(grid, x + dir[0], y + dir[1], id);
}
return size;
}
}
Python
class Solution:
def __init__(self):
self.n: int = 0
self.dirs: List[List[int]] = [[1, 0], [-1, 0], [0, 1], [0, -1]] # Down, Up, Right, Left
def largestIsland(self, grid: List[List[int]]) -> int:
self.n = len(grid)
size: List[int] = [0] * (self.n * self.n + 2)
id: int = 2 # Start from 2 because 1s are already used
maxSize: int = 0
# First pass: label every island with a unique id and calculate their size
for i in range(self.n):
for j in range(self.n):
if grid[i][j] == 1:
size[id] = self.dfs(grid, i, j, id)
maxSize = max(maxSize, size[id])
id += 1
# Second pass: check potential size by flipping each 0 to 1
for i in range(self.n):
for j in range(self.n):
if grid[i][j] == 0:
seenIds: Set[int] = set()
potentialSize: int = 1 # The flipped cell itself
for dir in self.dirs:
newRow, newCol = i + dir[0], j + dir[1]
if 0 <= newRow < self.n and 0 <= newCol < self.n and grid[newRow][newCol] != 0:
islandId = grid[newRow][newCol]
if islandId not in seenIds:
seenIds.add(islandId)
potentialSize += size[islandId]
maxSize = max(maxSize, potentialSize)
return maxSize
def dfs(self, grid: List[List[int]], x: int, y: int, id: int) -> int:
if x < 0 or x >= self.n or y < 0 or y >= self.n or grid[x][y] != 1:
return 0
grid[x][y] = id
sz: int = 1
for dir in self.dirs:
sz += self.dfs(grid, x + dir[0], y + dir[1], id)
return sz
Complexity
- ⏰ Time complexity:
O(n^2)
, since we potentially traverse the entire grid multiple times. - 🧺 Space complexity:
O(n^2)
, for storing island labels and sizes.