Making A Large Island Hard 0 attempts
LeetCode ↗

Making A Large Island

Hard GraphBFSDFS LeetCode

You are given an n x n binary grid. You are allowed to change at most one 0 to a 1. Return the size of the largest island in the 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

Example 2:

Input: grid = [[1,1],[1,0]]
Output: 4
Sample Input
—
Sample Output
—
Constraints
  • 1 <= n <= 500
  • grid[i][j] is 0 or 1
Test Cases
Case 1
Args: [[[1,0],[0,1]]] Expected: 3
Topics
GraphBFSDFS

Union-Find / DFS with Island IDs

Label islands with IDs and sizes. For each 0, check adjacent islands.

function largestIsland(grid) {
  const n = grid.length, dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  const sizes = new Map(); let id = 2, maxSize = 0;
  function dfs(r, c, id) {
    if (r<0||r>=n||c<0||c>=n||grid[r][c]!==1) return 0;
    grid[r][c] = id;
    return 1 + dfs(r+1,c,id) + dfs(r-1,c,id) + dfs(r,c+1,id) + dfs(r,c-1,id);
  }
  for (let i=0;i<n;i++) for (let j=0;j<n;j++)
    if (grid[i][j]===1) { const s = dfs(i,j,id); sizes.set(id,s); maxSize = Math.max(maxSize,s); id++; }
  for (let i=0;i<n;i++) for (let j=0;j<n;j++) if (grid[i][j]===0) {
    const seen = new Set(); let total = 1;
    for (const [dr,dc] of dirs) {
      const nr=i+dr, nc=j+dc;
      if (nr>=0&&nr<n&&nc>=0&&nc<n&&grid[nr][nc]>1&&!seen.has(grid[nr][nc])) {
        seen.add(grid[nr][nc]); total += sizes.get(grid[nr][nc]);
      }
    }
    maxSize = Math.max(maxSize, total);
  }
  return maxSize;
}

Time: O(n²) | Space: O(n²)

Saved in this browser only. Private to you.

JavaScript