Making A Large Island solution and explanation
Google
9 more videos on this problem
G-52. Making a Large Island - DSUtake U forward · 26:16 · 168K views
Making A Large Island - Leetcode 827 - PythonNeetCodeIO · 26:56 · 17K views
MAKING A LARGE ISLAND | LEETCODE # 827 | PYTHON SOLUTIONCracking FAANG · 22:09 · 12K views
Making A Large Island | Brute Force | Better | Optimal | Dry Run | Leetcode 827 | codestorywithMIKcodestorywithMIK · 1:02:48 · 10K views
Making A Large Island | Leetcode 827 | Live Coding session 🔥🔥🔥Coding Decoded · 13:14 · 7K views
Making A Large Island | Leetcode 827Techdose · 25:12 · 3K views
827. Making A Large Island | DFS | Connect ComponentsAryan Mittal · 19:11 · 2K views
Making a Large Island | Google Interview Question | Disjoint Set Union | 827 LeetCode | Day 01CodeWithSunny · 25:36 · 1K views
Daily Leetcode #488: Aug 01, 2021 - 827. Making A Large IslandProgramming Live with Larry · 14:14 · 946 views
Google Coding Interview Question | Leetcode 827 | Making A Large IslandWorkWithGoogler · 37:37 · 739 views
The 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 1s.
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.lengthn == grid[i].length1 <= n <= 500grid[i][j]is either0or1.
Approach overview
Problem Overview: You get an n x n binary grid where 1 represents land and 0 represents water. You may flip at most one 0 to 1. The task is to return the size of the largest island possible after the flip. An island is a group of 4-directionally connected land cells.
Approach 1: Brute Force Flip + DFS (O(n^4) time, O(n^2) space)
Iterate through every cell in the grid. Whenever you encounter a 0, temporarily flip it to 1 and run a full depth-first search to compute the size of the resulting island. Track the maximum size across all flips, then revert the cell back to 0. Each DFS may scan the entire grid (O(n^2)) and you potentially perform it for every cell (O(n^2)), resulting in O(n^4) time. This approach is straightforward but too slow for large grids.
Approach 2: DFS with Island Labeling (O(n^2) time, O(n^2) space)
The key insight is to pre-compute the size of every island so you never recompute it. Traverse the grid once and run DFS whenever you encounter an unvisited land cell. During the DFS, label the island with a unique id (for example 2, 3, 4...) and store its size in a hash map keyed by the island id. This step converts the grid into labeled components using DFS over the matrix.
Next, iterate over each 0 cell. Look at its four neighbors and collect the distinct island ids touching that cell. If you flip the cell to 1, the new island size becomes 1 + sum(sizes of unique neighboring islands). Use a set to avoid counting the same island twice. Track the maximum possible size while scanning all water cells. The grid traversal and labeling both take O(n^2), giving an optimal O(n^2) solution.
Approach 3: Union Find (Disjoint Set) (O(n^2) time, O(n^2) space)
You can also treat each land cell as a node in a disjoint-set structure and union adjacent land cells. The union operations build connected components representing islands. Each component stores its size. After building the structure, iterate through every 0 cell and inspect up to four neighboring components. Similar to the DFS labeling idea, combine the sizes of unique neighboring components plus one for the flipped cell. This approach relies on the Union Find data structure and performs nearly constant-time unions and finds with path compression.
Recommended for interviews: DFS with island labeling is the most common interview solution. It demonstrates strong grid traversal skills, component labeling, and efficient reuse of computed island sizes. Brute force shows basic reasoning but fails performance constraints. The labeled DFS approach reaches O(n^2) time and is easy to implement compared to Union Find while still demonstrating optimal thinking.
Approach 1: DFS with Island Labeling
This approach involves two main steps: firstly labeling all the islands in the grid using DFS, and secondly calculating the maximum possible island size by changing a '0' to a '1'.
1. Traverse the grid using DFS and label each island with a unique identifier. As you label the islands, keep track of the size of each island in a dictionary.
2. Iterate over each '0' cell in the grid, consider changing it to '1', and calculate the potential island size by inspecting neighboring cells.
3. Use a set to aggregate the neighboring island labels, and use the sizes from the dictionary to compute the total size.
This allows us to efficiently calculate the new island sizes by directly accessing individual island sizes using their labels.
def largestIsland(grid):
n = len(grid)
def dfs(x, y, index):
stack = [(x, y)]
grid[x][y] = index
area = 1
for x, y in stack:
for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
grid[nx][ny] = index
stack.append((nx, ny))
area += 1
return area
index_to_area = {0: 0}
index = 2
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
index_to_area[index] = dfs(i, j, index)
index += 1
max_area = max(index_to_area.values())
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
seen = set()
area = 1
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < n and 0 <= nj < n:
index = grid[ni][nj]
if index > 1:
seen.add(index)
area += sum(index_to_area[index] for index in seen)
max_area = max(max_area, area)
return max_areaclass Solution {
private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int largestIsland(int[][] grid) {
int n = grid.length;
Map<Integer, Integer> areaMap = new HashMap<>();
int index = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int area = dfs(grid, i, j, index);
areaMap.put(index, area);
index++;
}
}
}
int maxArea = areaMap.values().stream().max(Integer::compare).orElse(0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
Set<Integer> seen = new HashSet<>();
int newArea = 1;
for (int[] d : directions) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] > 1 && seen.add(grid[ni][nj])) {
newArea += areaMap.get(grid[ni][nj]);
}
}
maxArea = Math.max(maxArea, newArea);
}
}
}
return maxArea;
}
private int dfs(int[][] grid, int i, int j, int index) {
grid[i][j] = index;
int area = 1;
for (int[] dir : directions) {
int ni = i + dir[0], nj = j + dir[1];
if (ni >= 0 && nj >= 0 && ni < grid.length && nj < grid[0].length && grid[ni][nj] == 1) {
area += dfs(grid, ni, nj, index);
}
}
return area;
}
}#include <vector>
#include <unordered_map>
#include <unordered_set>
class Solution {
public:
int largestIsland(std::vector<std::vector<int>>& grid) {
int n = grid.size();
int index = 2;
std::unordered_map<int, int> areaMap;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int area = dfs(grid, i, j, index);
areaMap[index] = area;
index++;
}
}
}
int maxArea = 0;
for (const auto& [key, value] : areaMap) {
maxArea = std::max(maxArea, value);
}
std::vector<std::pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
std::unordered_set<int> seen;
int area = 1;
for (auto [di, dj] : directions) {
int ni = i + di, nj = j + dj;
if (ni >= 0 && nj >= 0 && ni < n && nj < n) {
int idx = grid[ni][nj];
if (idx > 1) {
seen.insert(idx);
}
}
}
for (int idx : seen) {
area += areaMap[idx];
}
maxArea = std::max(maxArea, area);
}
}
}
return maxArea;
}
int dfs(std::vector<std::vector<int>>& grid, int i, int j, int index) {
int n = grid.size();
grid[i][j] = index;
int area = 1;
std::vector<std::pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (auto [di, dj] : directions) {
int ni = i + di, nj = j + dj;
if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {
area += dfs(grid, ni, nj, index);
}
}
return area;
}
};This code begins by defining a helper function dfs to traverse and mark connected islands. Each cell is associated with a unique island index, and the area of each island is stored in a dictionary.
The main loop iterates through all grid cells. For '1' cells, DFS is executed, labeling the island and calculating its area. '0' cells are evaluated by looking at their surrounding areas to calculate their possible contribution to an enlarged island size.
Time Complexity: O(n^2), because each cell of the grid is visited at most twice, once for DFS and once for change evaluation.
Space Complexity: O(n^2) for storage of the labeled grid and area dictionary.
Approach 2: DFS
We can assign a unique identifier to each connected component, using an array p to record the connected component each position belongs to, i.e., p[i][j] represents the connected component number of (i, j). Use an array cnt to record the size of each connected component, i.e., cnt[root] represents the size of the connected component root.
First, we traverse the entire matrix. For each position grid[i][j] = 1 and p[i][j] = 0, we perform a depth-first search on it, mark its connected component as root, and count the size of the connected component.
Then, we traverse the entire matrix again. For each position grid[i][j] = 0, we find the connected components of the four positions above, below, left, and right of it, add up the sizes of these connected components, and add 1 for the current position, to get the maximum island area after changing the current position to 1.
The time complexity is O(n^2), and the space complexity is O(n^2). Where n is the length of the sides of the matrix.
function largestIsland(grid: number[][]): number {
const n = grid.length;
const p = Array.from({ length: n }, () => Array(n).fill(0));
const cnt = Array(n * n + 1).fill(0);
const dirs = [-1, 0, 1, 0, -1];
let root = 0;
let ans = 0;
const dfs = (i: number, j: number): number => {
p[i][j] = root;
cnt[root]++;
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] === 1 && p[x][y] === 0) {
dfs(x, y);
}
}
return cnt[root];
};
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1 && p[i][j] === 0) {
root++;
ans = Math.max(ans, dfs(i, j));
}
}
}
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 0) {
const s = new Set<number>();
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
s.add(p[x][y]);
}
}
let t = 1;
for (const x of s) {
t += cnt[x];
}
ans = Math.max(ans, t);
}
}
}
return ans;
}func largestIsland(grid [][]int) int {
n := len(grid)
p := make([][]int, n)
for i := range p {
p[i] = make([]int, n)
}
cnt := make([]int, n*n+1)
dirs := []int{-1, 0, 1, 0, -1}
root := 0
ans := 0
var dfs func(int, int) int
dfs = func(i, j int) int {
p[i][j] = root
cnt[root]++
for k := 0; k < 4; k++ {
x := i + dirs[k]
y := j + dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1 && p[x][y] == 0 {
dfs(x, y)
}
}
return cnt[root]
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 && p[i][j] == 0 {
root++
ans = max(ans, dfs(i, j))
}
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 0 {
s := make(map[int]struct{})
for k := 0; k < 4; k++ {
x := i + dirs[k]
y := j + dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n {
s[p[x][y]] = struct{}{}
}
}
t := 1
for x := range s {
t += cnt[x]
}
ans = max(ans, t)
}
}
}
return ans
}use std::collections::HashSet;
impl Solution {
pub fn largest_island(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let mut p = vec![vec![0; n]; n];
let mut cnt = vec![0; n * n + 1];
let dirs = [-1, 0, 1, 0, -1];
let mut root = 0;
let mut ans = 0;
fn dfs(
grid: &Vec<Vec<i32>>,
p: &mut Vec<Vec<i32>>,
cnt: &mut Vec<i32>,
root: i32,
i: usize,
j: usize,
dirs: &[i32; 5],
) -> i32 {
p[i][j] = root;
cnt[root as usize] += 1;
for k in 0..4 {
let x = (i as i32) + dirs[k];
let y = (j as i32) + dirs[k + 1];
if x >= 0
&& (x as usize) < grid.len()
&& y >= 0
&& (y as usize) < grid.len()
&& grid[x as usize][y as usize] == 1
&& p[x as usize][y as usize] == 0
{
dfs(grid, p, cnt, root, x as usize, y as usize, dirs);
}
}
cnt[root as usize]
}
for i in 0..n {
for j in 0..n {
if grid[i][j] == 1 && p[i][j] == 0 {
root += 1;
ans = ans.max(dfs(&grid, &mut p, &mut cnt, root, i, j, &dirs));
}
}
}
for i in 0..n {
for j in 0..n {
if grid[i][j] == 0 {
let mut s = HashSet::new();
for k in 0..4 {
let x = (i as i32) + dirs[k];
let y = (j as i32) + dirs[k + 1];
if x >= 0 && (x as usize) < n && y >= 0 && (y as usize) < n {
s.insert(p[x as usize][y as usize]);
}
}
let mut t = 1;
for &x in &s {
t += cnt[x as usize];
}
ans = ans.max(t);
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS with Island Labeling | Time Complexity: O(n^2), because each cell of the grid is visited at most twice, once for DFS and once for change evaluation. Space Complexity: O(n^2) for storage of the labeled grid and area dictionary. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Flip + DFS | O(n^4) | O(n^2) | Conceptual starting point when first reasoning about flipping each water cell |
| DFS with Island Labeling | O(n^2) | O(n^2) | Best practical solution for interviews and coding platforms |
| Union Find (Disjoint Set) | O(n^2) | O(n^2) | Useful when practicing connectivity problems with dynamic component merging |
Frequently asked questions
Is Making A Large Island easy or hard?
Making A Large Island is rated Hard on LeetCode because it combines matrix traversal, connected component labeling, and careful handling of duplicate neighboring islands. The optimal solution requires recognizing that island sizes must be precomputed.
How to solve Making A Large Island in O(n^2)?
Label every connected land component using DFS and assign it a unique id while recording its size in a map. For each 0 cell, gather the unique neighboring island ids and sum their sizes plus one for the flipped cell. This avoids recomputing island sizes and keeps the total work proportional to the grid size.
What is the best approach for Making A Large Island?
DFS with island labeling is the most common optimal solution. First label each island with a unique id and store its size using DFS in O(n^2). Then evaluate every 0 cell and combine the sizes of adjacent distinct islands to compute the largest possible island after one flip.
What data structure is used in Making A Large Island?
The most common solution uses DFS with a hash map to store island sizes and a set to avoid counting duplicate neighboring islands. Some implementations also use the Union Find (Disjoint Set) data structure to track connected components.
What is the time complexity of Making A Large Island?
The optimal solution runs in O(n^2) time for an n x n grid. One DFS pass labels every island and computes sizes, and a second pass evaluates each water cell by checking its four neighbors.
Making A Large Island Python or Java solution approach?
Python and Java implementations typically run a DFS to label islands and store their sizes in a dictionary or map. Then each 0 cell checks its four neighbors, combines distinct island sizes, and updates the maximum possible island area.
Is Making A Large Island asked at Google, Amazon, or Meta?
Making A Large Island is a classic grid connectivity problem and appears in interviews at companies that test graph and matrix traversal skills, including Google, Amazon, and Meta-style interview loops. It evaluates DFS/BFS reasoning and component merging logic.