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 either 0 or 1.In #827 Making A Large Island, the goal is to determine the largest possible island size after converting at most one 0 in a binary grid to 1. A practical strategy is to first identify and label all existing islands using Depth-First Search (DFS) or Breadth-First Search (BFS). Each island is assigned a unique ID and its size is stored for quick lookup.
Once islands are labeled, iterate through every 0 cell and examine its four neighboring cells. By combining the sizes of uniquely adjacent islands (using a set to avoid double counting), you can estimate the potential island size if that 0 were flipped to 1. Track the maximum possible value across all such flips.
An alternative implementation uses the Union Find (Disjoint Set) structure to merge connected land cells and maintain component sizes. Both methods efficiently avoid recomputing island sizes repeatedly.
The overall solution runs in about O(n²) time for an n × n grid, with additional space used to store island identifiers and sizes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS/BFS Island Labeling | O(n^2) | O(n^2) |
| Union Find (Disjoint Set) | O(n^2 * α(n)) | O(n^2) |
take U forward
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.
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.
1class Solution {
2 private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
3
4 public int largestIsland(int[][] grid) {
5 int n = grid.length;
6 Map<Integer, Integer> areaMap = new HashMap<>();
7 int index = 2;
8 for (int i = 0; i < n; i++) {
9 for (int j = 0; j < n; j++) {
10 if (grid[i][j] == 1) {
11 int area = dfs(grid, i, j, index);
12 areaMap.put(index, area);
13 index++;
14 }
15 }
16 }
17
18 int maxArea = areaMap.values().stream().max(Integer::compare).orElse(0);
19
20 for (int i = 0; i < n; i++) {
21 for (int j = 0; j < n; j++) {
22 if (grid[i][j] == 0) {
23 Set<Integer> seen = new HashSet<>();
24 int newArea = 1;
25 for (int[] d : directions) {
26 int ni = i + d[0], nj = j + d[1];
27 if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] > 1 && seen.add(grid[ni][nj])) {
28 newArea += areaMap.get(grid[ni][nj]);
29 }
30 }
31 maxArea = Math.max(maxArea, newArea);
32 }
33 }
34 }
35
36 return maxArea;
37 }
38
39 private int dfs(int[][] grid, int i, int j, int index) {
40 grid[i][j] = index;
41 int area = 1;
42 for (int[] dir : directions) {
43 int ni = i + dir[0], nj = j + dir[1];
44 if (ni >= 0 && nj >= 0 && ni < grid.length && nj < grid[0].length && grid[ni][nj] == 1) {
45 area += dfs(grid, ni, nj, index);
46 }
47 }
48 return area;
49 }
50}The Java solution mirrors the logic of the Python solution, using a DFS helper method to explore and mark islands with unique indices. A HashMap stores the size of each island.
For each '0', its contribution to a possible larger island is calculated by evaluating surrounding marked areas, and potentially updating the maximum island size found.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Labeling islands assigns a unique identifier to each connected component of 1s. This allows quick lookup of island sizes when evaluating the effect of flipping a 0 cell, while also preventing double counting of the same island.
Yes, this problem reflects common FAANG interview patterns involving grids, connected components, and graph traversal. It tests DFS/BFS fundamentals, Union Find knowledge, and the ability to optimize brute-force approaches.
Common choices include DFS/BFS with a hash map to track island sizes or a Union Find (Disjoint Set) structure to maintain connected components. Both approaches efficiently track island groups and their sizes.
The optimal approach labels each island using DFS or BFS and stores its size. Then for every 0 cell, it checks neighboring islands and combines their sizes if the cell is flipped to 1. This avoids recomputation and keeps the overall complexity around O(n^2).