Making A Large Island Hard 0 attempts
LeetCode ↗

Making A Large Island

Hard GraphBFSDFS LeetCode

You're given an n x n binary grid, and you're allowed to flip at most one 0 into a 1. After doing so (or choosing not to), return the size of the biggest island you can produce. An island here means a group of 1s connected up, down, left, or right — diagonal neighbors don't count.

Input Format
Implement largestIsland(grid). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
grid = [[1,0],[0,1]]
Output
3

Example 2

Input
grid = [[1,1],[1,1]]
Output
4

Example 3

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

Island Labels and Sizes

Label each island with a distinct ID using an explicit stack. For each zero, add the sizes of its distinct neighboring islands plus one. Counting each ID once avoids double counting an island touching the zero on multiple sides.

javascript
function largestIsland(grid) {
  const n=grid.length,dirs=[[1,0],[-1,0],[0,1],[0,-1]],sizes=new Map();let id=2,best=0;
  for(let r=0;r<n;r++)for(let c=0;c<n;c++)if(grid[r][c]===1){
    const stack=[[r,c]];grid[r][c]=id;let size=0;
    while(stack.length){const [x,y]=stack.pop();size++;for(const [dx,dy] of dirs){const nx=x+dx,ny=y+dy;if(nx>=0&&nx<n&&ny>=0&&ny<n&&grid[nx][ny]===1){grid[nx][ny]=id;stack.push([nx,ny]);}}}
    sizes.set(id++,size);best=Math.max(best,size);
  }
  for(let r=0;r<n;r++)for(let c=0;c<n;c++)if(grid[r][c]===0){
    const seen=new Set();let total=1;
    for(const [dr,dc] of dirs){const nr=r+dr,nc=c+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]);}}
    best=Math.max(best,total);
  }
  return best;
}

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

Saved in this browser only. Private to you.

JavaScript