Making A Large Island - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
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 | — |
Detailed 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 |
Video Solution
G-52. Making a Large Island - DSU • take U forward • 168,609 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Making A Large Island easy or hard?
How to solve Making A Large Island in O(n^2)?
What is the best approach for Making A Large Island?
What data structure is used in Making A Large Island?
What is the time complexity of Making A Large Island?
Making A Large Island Python or Java solution approach?
Is Making A Large Island asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Making A Large Island with our built-in code editor and test cases.
Practice on FleetCode