Making A Large Island

Hard

#0781Time: O(n^4). Let `N = n*n`. There are `O(N)` cells. For each of the `O(N)` cells that could be a zero, we perform a full grid traversal to find the largest island, which takes `O(N)` time. This results in a total time complexity of `O(N*N) = O((n^2)^2) = O(n^4)`.Space: O(n^2). The space is dominated by the `visited` array used in the island size calculation function and the recursion stack for DFS, both of which can be O(n^2) in the worst case.7 companies

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Array Matrix

Companies

Airbnb DoorDash Snowflake jio

Prompt

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.length
n == grid[i].length
1 <= n <= 500
grid[i][j] is either 0 or 1.

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simulate the process directly. We can iterate through every cell in the grid. If a cell contains a 0, we temporarily change it to a 1 and then calculate the size of the largest island in this newly modified grid. We keep track of the maximum size found across all these simulations.

Algorithm

Initialize maxSize = 0.
Initialize a boolean flag hasZero = false to track if any 0 exists in the grid.
Iterate through each cell (r, c) of the n x n grid.
If grid[r][c] == 0:
- Set hasZero = true.
- Temporarily change grid[r][c] to 1.
- Call a helper function calculateLargestIsland(grid) to find the size of the largest island in the modified grid. This helper function uses a standard DFS/BFS traversal with a visited array to explore and count connected 1s.
- Update maxSize = max(maxSize, calculatedSize).
- Revert grid[r][c] back to 0 to restore the grid for the next iteration.
After the loops, if hasZero is false, it means the grid was all 1s, so the answer is n*n. Otherwise, the answer is maxSize.

Walkthrough

This method involves a nested loop to traverse the grid. For each cell (r, c) containing a 0, we perform the following steps:

Flip grid[r][c] from 0 to 1.
Trigger a function to find the largest island size in the current state of the grid. This function itself would iterate through all cells, and for each unvisited 1, it would start a traversal (like Depth First Search or Breadth First Search) to find the size of the island it belongs to. A visited matrix is required to avoid recounting.
Update a global maximum size variable with the result from step 2.
Flip grid[r][c] back to 0 to restore the grid for the next iteration.

An initial check is needed for the case where the grid contains no zeros. In this scenario, the answer is simply the size of the single island, which is n*n.

1class Solution {2    public int largestIsland(int[][] grid) {3        int n = grid.length;4        int maxArea = 0;5        boolean hasZero = false;6 7        for (int i = 0; i < n; i++) {8            for (int j = 0; j < n; j++) {9                if (grid[i][j] == 0) {10                    hasZero = true;11                    grid[i][j] = 1; // Flip 0 to 112                    maxArea = Math.max(maxArea, findLargestIslandSize(grid));13                    grid[i][j] = 0; // Flip back14                }15            }16        }17 18        return hasZero ? maxArea : n * n;19    }20 21    private int findLargestIslandSize(int[][] grid) {22        int n = grid.length;23        boolean[][] visited = new boolean[n][n];24        int maxArea = 0;25        for (int i = 0; i < n; i++) {26            for (int j = 0; j < n; j++) {27                if (grid[i][j] == 1 && !visited[i][j]) {28                    maxArea = Math.max(maxArea, dfs(i, j, grid, visited));29                }30            }31        }32        return maxArea;33    }34 35    private int dfs(int r, int c, int[][] grid, boolean[][] visited) {36        int n = grid.length;37        if (r < 0 || r >= n || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {38            return 0;39        }40        visited[r][c] = true;41        int count = 1;42        count += dfs(r + 1, c, grid, visited);43        count += dfs(r - 1, c, grid, visited);44        count += dfs(r, c + 1, grid, visited);45        count += dfs(r, c - 1, grid, visited);46        return count;47    }48}

Complexity

Time

O(n^4). Let `N = n*n`. There are `O(N)` cells. For each of the `O(N)` cells that could be a zero, we perform a full grid traversal to find the largest island, which takes `O(N)` time. This results in a total time complexity of `O(N*N) = O((n^2)^2) = O(n^4)`.

Space

O(n^2). The space is dominated by the `visited` array used in the island size calculation function and the recursion stack for DFS, both of which can be O(n^2) in the worst case.

Trade-offs

Pros

Simple to understand and implement.
Directly simulates the problem statement.

Cons

Highly inefficient due to redundant calculations.
For each 0 that is flipped, it re-scans the entire grid and re-calculates island sizes from scratch.
Will likely result in a "Time Limit Exceeded" error for larger grids as specified in the constraints.

A much more efficient approach involves two main passes over the grid. The first pass identifies all existing islands, assigns each a unique ID, and calculates and stores its size. The second pass iterates through all the 0s in the grid. For each 0, it checks its neighboring cells to see which unique islands it could connect. By summing the sizes of these unique neighboring islands and adding 1 (for the 0 itself), we can find the potential size of the new, larger island.

Algorithm

Initialize a map islandSizes to store islandId -> size and an islandId counter starting from 2.
Pass 1: Labeling
- Iterate through each cell (r, c) of the grid.
- If grid[r][c] == 1, it's a new, unlabeled island.
- Start a DFS/BFS from (r, c).
- During the traversal, change all 1s of the island to the current islandId and count the number of cells (size).
- Store the result: islandSizes.put(islandId, size).
- Increment islandId for the next island.
Handle edge case: If islandSizes is empty after Pass 1, the grid was all 0s. Return 1 (since we can flip one 0).
Initialize maxSize to the largest value in islandSizes.values(). This covers the case where no 0s can be flipped.
Pass 2: Merging
- Iterate through each cell (r, c) of the grid.
- If grid[r][c] == 0:
  - Create a Set to store the unique islandIds of its 4-directional neighbors.
  - Calculate potentialSize = 1 (for the current 0).
  - For each unique islandId in the set, add its corresponding size from the islandSizes map to potentialSize.
  - Update maxSize = max(maxSize, potentialSize).
Return maxSize.

Walkthrough

This method avoids the redundant calculations of the brute-force approach by pre-computing the sizes of all initial islands.

Pass 1: Find and Label Islands We traverse the grid. When we encounter a 1 that hasn't been labeled, we start a traversal (DFS or BFS). We assign a new, unique islandId (e.g., starting from 2, to not conflict with 0 and 1). During the traversal, we find all connected 1s, count them to get the island's size, and update the grid cells of this island from 1 to islandId. We store the mapping of islandId to size in a hash map. We also find the largest island size found during this pass, which handles the edge case where the grid has no 0s.

Pass 2: Evaluate Zeros We traverse the grid again, this time looking for 0s. For each 0, we look at its four neighbors and collect their unique islandIds. The potential new island size is 1 (for the 0 we flip) plus the sum of the sizes of all unique neighboring islands. We update our overall maximum size with this potential size.

1class Solution {2    public int largestIsland(int[][] grid) {3        int n = grid.length;4        // map: islandId -> islandSize5        Map<Integer, Integer> islandSizes = new HashMap<>();6        int islandId = 2; // Start island IDs from 27 8        // Pass 1: Find all islands, label them, and store their sizes.9        for (int i = 0; i < n; i++) {10            for (int j = 0; j < n; j++) {11                if (grid[i][j] == 1) { // Found an unlabeled island12                    int size = paint(i, j, grid, islandId);13                    islandSizes.put(islandId, size);14                    islandId++;15                }16            }17        }18 19        // If no islands were found, the grid is all zeros. The largest we can make is 1.20        if (islandSizes.isEmpty()) {21            return 1;22        }23 24        int maxArea = 0;25        // Get the size of the largest existing island. This handles the all-1s case.26        for (int size : islandSizes.values()) {27            maxArea = Math.max(maxArea, size);28        }29 30        // Pass 2: Iterate through zeros and calculate potential merged island size.31        for (int i = 0; i < n; i++) {32            for (int j = 0; j < n; j++) {33                if (grid[i][j] == 0) {34                    Set<Integer> neighborIds = new HashSet<>();35                    // Check 4-directional neighbors36                    if (i > 0) neighborIds.add(grid[i - 1][j]);37                    if (i < n - 1) neighborIds.add(grid[i + 1][j]);38                    if (j > 0) neighborIds.add(grid[i][j - 1]);39                    if (j < n - 1) neighborIds.add(grid[i][j + 1]);40                    41                    int potentialArea = 1; // For the zero itself42                    for (int id : neighborIds) {43                        if (id > 1) { // It's a valid island ID44                            potentialArea += islandSizes.get(id);45                        }46                    }47                    maxArea = Math.max(maxArea, potentialArea);48                }49            }50        }51        52        return maxArea;53    }54 55    // Helper function to find an island, paint it with an ID, and return its size.56    private int paint(int r, int c, int[][] grid, int islandId) {57        int n = grid.length;58        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) {59            return 0;60        }61        grid[r][c] = islandId;62        return 1 + paint(r + 1, c, grid, islandId)63                 + paint(r - 1, c, grid, islandId)64                 + paint(r, c + 1, grid, islandId)65                 + paint(r, c - 1, grid, islandId);66    }67}

Complexity

Time

O(n^2). Let `N = n*n`. Pass 1 involves a full grid traversal where each cell is visited once (DFS/BFS), taking `O(N)` time. Pass 2 involves another full grid traversal, and for each cell, the work is constant (checking 4 neighbors). This also takes `O(N)` time. The total time is `O(N) + O(N) = O(N) = O(n^2)`.

Space

O(n^2). The space is used for the `islandSizes` map, which can store up to O(n^2) entries in the worst case (a checkerboard pattern). The recursion stack for the DFS can also go up to O(n^2) in the worst case (a snake-like island).

Trade-offs

Pros

Very efficient, with a linear time complexity relative to the grid size.
Avoids redundant computations by pre-calculating and storing island properties.
Passes for large inputs where brute-force would fail.

Cons

More complex to implement than the brute-force approach.
Requires modifying the input grid or using an auxiliary grid, which increases space complexity if the input is immutable.

Solutions

Solution

1class Solution {2private3  int n;4private5  int[] p;6private7  int[] size;8private9  int ans = 1;10private11  int[] dirs = new int[]{-1, 0, 1, 0, -1};12public13  int largestIsland(int[][] grid) {14    n = grid.length;15    p = new int[n * n];16    size = new int[n * n];17    for (int i = 0; i < p.length; ++i) {18      p[i] = i;19      size[i] = 1;20    }21    for (int i = 0; i < n; ++i) {22      for (int j = 0; j < n; ++j) {23        if (grid[i][j] == 1) {24          for (int k = 0; k < 4; ++k) {25            int x = i + dirs[k], y = j + dirs[k + 1];26            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {27              int pa = find(x * n + y), pb = find(i * n + j);28              if (pa == pb) {29                continue;30              }31              p[pa] = pb;32              size[pb] += size[pa];33              ans = Math.max(ans, size[pb]);34            }35          }36        }37      }38    }39    for (int i = 0; i < n; ++i) {40      for (int j = 0; j < n; ++j) {41        if (grid[i][j] == 0) {42          int t = 1;43          Set<Integer> vis = new HashSet<>();44          for (int k = 0; k < 4; ++k) {45            int x = i + dirs[k], y = j + dirs[k + 1];46            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {47              int root = find(x * n + y);48              if (!vis.contains(root)) {49                vis.add(root);50                t += size[root];51              }52            }53          }54          ans = Math.max(ans, t);55        }56      }57    }58    return ans;59  }60private61  int find(int x) {62    if (p[x] != x) {63      p[x] = find(p[x]);64    }65    return p[x];66  }67}

1class Solution {2public:3  const static inline vector<int> dirs = {-1, 0, 1, 0, -1};4  int largestIsland(vector<vector<int>> &grid) {5    int n = grid.size();6    vector<int> p(n * n);7    vector<int> size(n * n, 1);8    iota(p.begin(), p.end(), 0);9    function<int(int)> find;10    find = [&](int x) {11      if (p[x] != x) {12        p[x] = find(p[x]);13      }14      return p[x];15    };16    int ans = 1;17    for (int i = 0; i < n; ++i) {18      for (int j = 0; j < n; ++j) {19        if (grid[i][j]) {20          for (int k = 0; k < 4; ++k) {21            int x = i + dirs[k], y = j + dirs[k + 1];22            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y]) {23              int pa = find(x * n + y), pb = find(i * n + j);24              if (pa == pb)25                continue;26              p[pa] = pb;27              size[pb] += size[pa];28              ans = max(ans, size[pb]);29            }30          }31        }32      }33    }34    for (int i = 0; i < n; ++i) {35      for (int j = 0; j < n; ++j) {36        if (!grid[i][j]) {37          int t = 1;38          unordered_set<int> vis;39          for (int k = 0; k < 4; ++k) {40            int x = i + dirs[k], y = j + dirs[k + 1];41            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y]) {42              int root = find(x * n + y);43              if (!vis.count(root)) {44                vis.insert(root);45                t += size[root];46              }47            }48          }49          ans = max(ans, t);50        }51      }52    }53    return ans;54  }55};

1class Solution:2    def largestIsland(self, grid: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa == pb: return p[pa] = pb size[pb] += size[pa] n = len(grid) p = list(range(n * n)) size = [1] * (n * n) for i, row in enumerate(grid): for j, v in enumerate(row): if v: for a, b in [[0, - 1], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y]: union(x * n + y, i * n + j) ans = max(size) for i, row in enumerate(grid): for j, v in enumerate(row): if v == 0: vis = set() t = 1 for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y]: root = find(x * n + y) if root not in vis: vis . add(root) t += size[root] ans = max(ans, t) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem