Scale Engineer

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 SearchBreadth-First SearchUnion Find
Data structures
ArrayMatrix
Companies
AirbnbDoorDashSnowflakejio

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:

  1. Flip grid[r][c] from 0 to 1.
  2. 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.
  3. Update a global maximum size variable with the result from step 2.
  4. 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.

class Solution {    public int largestIsland(int[][] grid) {        int n = grid.length;        int maxArea = 0;        boolean hasZero = false;         for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 0) {                    hasZero = true;                    grid[i][j] = 1; // Flip 0 to 1                    maxArea = Math.max(maxArea, findLargestIslandSize(grid));                    grid[i][j] = 0; // Flip back                }            }        }         return hasZero ? maxArea : n * n;    }     private int findLargestIslandSize(int[][] grid) {        int n = grid.length;        boolean[][] visited = new boolean[n][n];        int maxArea = 0;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1 && !visited[i][j]) {                    maxArea = Math.max(maxArea, dfs(i, j, grid, visited));                }            }        }        return maxArea;    }     private int dfs(int r, int c, int[][] grid, boolean[][] visited) {        int n = grid.length;        if (r < 0 || r >= n || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {            return 0;        }        visited[r][c] = true;        int count = 1;        count += dfs(r + 1, c, grid, visited);        count += dfs(r - 1, c, grid, visited);        count += dfs(r, c + 1, grid, visited);        count += dfs(r, c - 1, grid, visited);        return count;    }}

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.

Solutions

class Solution {private  int n;private  int[] p;private  int[] size;private  int ans = 1;private  int[] dirs = new int[]{-1, 0, 1, 0, -1};public  int largestIsland(int[][] grid) {    n = grid.length;    p = new int[n * n];    size = new int[n * n];    for (int i = 0; i < p.length; ++i) {      p[i] = i;      size[i] = 1;    }    for (int i = 0; i < n; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 1) {          for (int k = 0; k < 4; ++k) {            int x = i + dirs[k], y = j + dirs[k + 1];            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {              int pa = find(x * n + y), pb = find(i * n + j);              if (pa == pb) {                continue;              }              p[pa] = pb;              size[pb] += size[pa];              ans = Math.max(ans, size[pb]);            }          }        }      }    }    for (int i = 0; i < n; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 0) {          int t = 1;          Set<Integer> vis = new HashSet<>();          for (int k = 0; k < 4; ++k) {            int x = i + dirs[k], y = j + dirs[k + 1];            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {              int root = find(x * n + y);              if (!vis.contains(root)) {                vis.add(root);                t += size[root];              }            }          }          ans = Math.max(ans, t);        }      }    }    return ans;  }private  int find(int x) {    if (p[x] != x) {      p[x] = find(p[x]);    }    return p[x];  }}

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 →

Next problem