Making a Large Island

78.5k
0

Given an N×N binary grid, return the size of the largest island possible after changing at most one 0 cell into 1.

An island is a group of 1 cells connected horizontally or vertically. Diagonal cells are not connected. If the grid already contains only land, return N×N.

Example 1

Input: grid = [[1,0],[0,1]]

Output: 3

Explanation: Flipping either zero connects two diagonal land cells through the flipped cell, forming an island of size 3.

Example 2

Input: grid = [[1,1],[1,0]]

Output: 4

Explanation: Flipping the only zero makes the entire grid one island.

Brute Force Approach

Every water cell is temporarily converted into land, followed by a complete island-area calculation using DFS. The largest area obtained across all possible flips becomes the final answer.

A fresh visited matrix keeps every trial independent, while restoring the flipped cell preserves the original grid for the next candidate. Repeated full-grid exploration makes the approach computationally expensive.

Algorithm

  • Compute the largest existing island using DFS and store the area as the initial answer, covering cases where no beneficial flip exists.

  • Traverse the grid using an outer loop for rows and an inner loop for columns, ensuring that every water cell is considered as a candidate.

  • Temporarily change the current water cell to land, simulating the allowed single conversion.

  • Create a fresh visited matrix and scan the modified grid, using DFS to calculate the area of every island formed during the current trial.

  • Update the maximum answer with the largest island area obtained from the temporary conversion.

  • Restore the candidate cell to water, ensuring that the next trial begins with the original grid.

  • Return N×N when no water cell exists; otherwise, return the maximum area found across all trials.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to count one island after a candidate flip.
int dfs(int row, int col, vector<vector<int>>& grid, vector<vector<int>>& visited) {
int n = grid.size();
// Stop for invalid cells, water cells, and already counted cells.
if (row < 0 || col < 0 || row >= n || col >= n || grid[row][col] == 0 || visited[row][col] == 1) {
return 0;
}
// Mark current land cell as counted.
visited[row][col] = 1;
// Count current cell and four neighboring directions.
int area = 1;
area += dfs(row - 1, col, grid, visited);
area += dfs(row + 1, col, grid, visited);
area += dfs(row, col - 1, grid, visited);
area += dfs(row, col + 1, grid, visited);
// Return island area for current DFS.
return area;
}
// Function to compute largest island for the current grid.
int largestCurrentIsland(vector<vector<int>>& grid) {
int n = grid.size();
int best = 0;
vector<vector<int>> visited(n, vector<int>(n, 0));
// Traverse every cell and count unvisited islands.
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (grid[row][col] == 1 && visited[row][col] == 0) {
best = max(best, dfs(row, col, grid, visited));
}
}
}
// Return largest island found.
return best;
}
public:
// Function to find largest island by trying every zero flip.
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
int answer = largestCurrentIsland(grid);
bool hasZero = false;
// Try every zero as a flip candidate.
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (grid[row][col] == 0) {
hasZero = true;
grid[row][col] = 1;
answer = max(answer, largestCurrentIsland(grid));
grid[row][col] = 0;
}
}
}
// Return full grid size for all-land grid.
if (!hasZero) {
return n * n;
}
// Return best area after at most one flip.
return answer;
}
};
// Driver code.
int main() {
vector<vector<int>> grid = {{1, 0}, {0, 1}};
Solution sol;
cout << sol.largestIsland(grid);
return 0;
}

Complexity Analysis

Time Complexity: O((N×N)²), where N×N is the total number of cells; each water candidate can require a complete N×N grid traversal.

Space Complexity: O(N×N), where the visited matrix and recursive DFS stack can each store up to N×N cells.

Optimal Approach 1

Every existing island receives a unique identifier, starting from 2 to avoid conflict with the original water value 0 and land value 1. DFS replaces each island cell with the identifier and records the corresponding area.

For every water cell, a set collects unique neighboring island identifiers. Adding the areas of such islands with one converted cell produces the largest island obtainable from the candidate flip.

Algorithm

  • Initialize the island identifier to 2, an area map for storing island sizes, and a maximum-area variable for tracking the answer.

  • Traverse the grid and start DFS from every cell containing 1, allowing each unprocessed island to be discovered independently.

  • During DFS, replace every connected land cell with the current island identifier and count the visited cells, permanently labeling the complete component.

  • Store the calculated area against the island identifier and increment the identifier for the next island.

  • Traverse every water cell and collect the identifiers of adjacent islands in a set, preventing the same island from being counted through multiple neighboring cells.

  • Calculate the candidate area as 1 for the converted cell plus the stored areas of all unique neighboring islands, then update the maximum area.

  • Return N×N when the grid contains no water; otherwise, return the maximum candidate area.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to label one island and return area.
int dfs(int row, int col, vector<vector<int>>& grid, int islandId) {
int n = grid.size();
// Stop for invalid cells and non-land cells.
if (row < 0 || col < 0 || row >= n || col >= n || grid[row][col] != 1) {
return 0;
}
// Replace land with island id.
grid[row][col] = islandId;
// Count current cell and all connected land cells.
int area = 1;
area += dfs(row - 1, col, grid, islandId);
area += dfs(row + 1, col, grid, islandId);
area += dfs(row, col - 1, grid, islandId);
area += dfs(row, col + 1, grid, islandId);
return area;
}
public:
// Function to find largest island using component labels.
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
unordered_map<int, int> areaById;
int islandId = 2;
int answer = 0;
bool hasZero = false;
vector<int> deltaRow = {-1, 1, 0, 0};
vector<int> deltaCol = {0, 0, -1, 1};
// Label every existing island with a unique id.
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (grid[row][col] == 1) {
int area = dfs(row, col, grid, islandId);
areaById[islandId] = area;
answer = max(answer, area);
islandId++;
}
}
}
// Try every zero and merge unique neighboring islands.
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (grid[row][col] != 0) {
continue;
}
hasZero = true;
unordered_set<int> seen;
int mergedArea = 1;
for (int dir = 0; dir < 4; dir++) {
int nextRow = row + deltaRow[dir];
int nextCol = col + deltaCol[dir];
if (nextRow >= 0 && nextCol >= 0 && nextRow < n && nextCol < n && grid[nextRow][nextCol] > 1) {
seen.insert(grid[nextRow][nextCol]);
}
}
for (int id : seen) {
mergedArea += areaById[id];
}
answer = max(answer, mergedArea);
}
}
// Return full grid area when no zero exists.
if (!hasZero) {
return n * n;
}
// Return maximum possible island area.
return answer;
}
};
// Driver code.
int main() {
vector<vector<int>> grid = {{1, 1}, {1, 0}};
Solution sol;
cout << sol.largestIsland(grid);
return 0;
}

Complexity Analysis

Time Complexity: O(N×N), where N is the grid dimension; island labeling and flip evaluation each process every cell a constant number of times.

Space Complexity: O(N×N), where the recursive DFS stack and island-area map can collectively store information for up to N×N cells.

Optimal Approach 2

Disjoint Set Union groups adjacent land cells into connected components before evaluating any flip. A cell at row r and column c maps to the one-dimensional identifier r×N+c.

For every water cell, a set stores the unique representatives of neighboring land components. The potential island area equals one converted cell plus the sizes of all distinct neighboring components.

Algorithm

  • Initialize DSU parent and size arrays for all N×N cells, along with four-direction arrays for adjacent-cell traversal.

  • Traverse every grid cell, map (row, col) to row×N+col, and record the presence of water while skipping union operations for water cells.

  • For every land cell, inspect all four directions and merge every valid neighboring land cell. Duplicate connection checks remain harmless because unite returns when both nodes already share a representative.

  • Return N×N when no water cell exists, as the entire grid already forms the largest possible island.

  • Traverse every water cell and collect the DSU representatives of all four neighboring land cells in a set, preventing duplicate component counting.

  • Calculate the candidate area as 1 plus the sizes of all unique neighboring components, then update the maximum area.

  • Return the largest candidate area after every water cell has been evaluated.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to find representative with path compression.
int findParent(int node, vector<int>& parent) {
if (parent[node] == node) {
return node;
}
parent[node] = findParent(parent[node], parent);
return parent[node];
}
// Function to merge two land components.
void unite(int first, int second, vector<int>& parent, vector<int>& size) {
int parentFirst = findParent(first, parent);
int parentSecond = findParent(second, parent);
if (parentFirst == parentSecond) {
return;
}
if (size[parentFirst] < size[parentSecond]) {
swap(parentFirst, parentSecond);
}
parent[parentSecond] = parentFirst;
size[parentFirst] += size[parentSecond];
}
public:
// Function to find largest island using DSU.
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
int total = n * n;
vector<int> parent(total);
vector<int> size(total, 1);
vector<int> deltaRow = {-1, 1, 0, 0};
vector<int> deltaCol = {0, 0, -1, 1};
bool hasZero = false;
// Initialize each cell as a separate component.
for (int node = 0; node < total; node++) {
parent[node] = node;
}
// Merge adjacent land cells.
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (grid[row][col] == 0) {
hasZero = true;
continue;
}
int current = row * n + col;
for (int dir = 0; dir < 4; dir++) {
int nextRow = row + deltaRow[dir];
int nextCol = col + deltaCol[dir];
if (nextRow >= 0 && nextCol >= 0 && nextRow < n && nextCol < n && grid[nextRow][nextCol] == 1) {
unite(current, nextRow * n + nextCol, parent, size);
}
}
}
}
if (!hasZero) {
return total;
}
int answer = 1;
// Try every zero and combine neighboring DSU components.
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (grid[row][col] != 0) {
continue;
}
unordered_set<int> seen;
int mergedArea = 1;
for (int dir = 0; dir < 4; dir++) {
int nextRow = row + deltaRow[dir];
int nextCol = col + deltaCol[dir];
if (nextRow >= 0 && nextCol >= 0 && nextRow < n && nextCol < n && grid[nextRow][nextCol] == 1) {
seen.insert(findParent(nextRow * n + nextCol, parent));
}
}
for (int root : seen) {
mergedArea += size[root];
}
answer = max(answer, mergedArea);
}
}
return answer;
}
};
// Driver code.
int main() {
vector<vector<int>> grid = {{1, 1}, {1, 1}};
Solution sol;
cout << sol.largestIsland(grid);
return 0;
}

Complexity Analysis

Time Complexity: O(N×N×α(N×N)), where N×N is the cell count and α is the inverse Ackermann cost of each optimized DSU operation.

Space Complexity: O(N×N), where the DSU parent and size arrays store one entry for every grid cell.

Interview follow-up Questions

Yes. A set of island ids prevents double-counting the same island.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: D...

89.1k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.2k
Comments0