Making A Large Island

hard array dfs matrix

Problem

Given an n×n binary grid, you may flip at most one 0 to 1. Return the size of the largest island after the flip.

Inputgrid = [[1,0],[0,1]]

Output3

Flip (0,1) or (1,0) to connect both 1s — island of size 3.

grid rows (semicolon-separated, comma cells)

def largest_island(grid):
    n = len(grid)
    label = [[0] * n for _ in range(n)]
    area = {}
    def dfs(r, c, idx):
        if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] != 1 or label[r][c]:
            return 0
        label[r][c] = idx
        return 1 + dfs(r+1,c,idx) + dfs(r-1,c,idx) + dfs(r,c+1,idx) + dfs(r,c-1,idx)
    idx = 1
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1 and label[r][c] == 0:
                area[idx] = dfs(r, c, idx); idx += 1
    best = max(area.values(), default=0)
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 0:
                seen = set()
                cur = 1
                for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                    nr, nc = r+dr, c+dc
                    if 0 <= nr < n and 0 <= nc < n and label[nr][nc] and label[nr][nc] not in seen:
                        seen.add(label[nr][nc])
                        cur += area[label[nr][nc]]
                best = max(best, cur)
    return best

function largestIsland(grid) {
  const n = grid.length;
  const label = Array.from({length: n}, () => new Array(n).fill(0));
  const area = new Map();
  let idx = 1;
  const dfs = (r, c) => {
    if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] !== 1 || label[r][c]) return 0;
    label[r][c] = idx;
    return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1);
  };
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++)
    if (grid[r][c] === 1 && !label[r][c]) { area.set(idx, dfs(r, c)); idx++; }
  let best = 0;
  for (const v of area.values()) best = Math.max(best, v);
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) {
    if (grid[r][c] !== 0) continue;
    const seen = new Set();
    let cur = 1;
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && label[nr][nc] && !seen.has(label[nr][nc])) {
        seen.add(label[nr][nc]); cur += area.get(label[nr][nc]);
      }
    }
    best = Math.max(best, cur);
  }
  return best;
}

class Solution {
    int[][] grid, label;
    int n, idx = 1;
    public int largestIsland(int[][] g) {
        this.grid = g;
        this.n = g.length;
        this.label = new int[n][n];
        Map<Integer, Integer> area = new HashMap<>();
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++)
            if (g[r][c] == 1 && label[r][c] == 0) { area.put(idx, dfs(r, c)); idx++; }
        int best = 0;
        for (int v : area.values()) best = Math.max(best, v);
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) {
            if (g[r][c] != 0) continue;
            Set<Integer> seen = new HashSet<>();
            int cur = 1;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && label[nr][nc] != 0 && seen.add(label[nr][nc]))
                    cur += area.get(label[nr][nc]);
            }
            best = Math.max(best, cur);
        }
        return best;
    }
    int dfs(int r, int c) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1 || label[r][c] != 0) return 0;
        label[r][c] = idx;
        return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1);
    }
}

class Solution {
public:
    vector<vector<int>> g, label;
    int n, idx = 1;
    int largestIsland(vector<vector<int>>& grid) {
        g = grid; n = g.size();
        label.assign(n, vector<int>(n, 0));
        unordered_map<int, int> area;
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++)
            if (g[r][c] == 1 && !label[r][c]) { area[idx] = dfs(r, c); idx++; }
        int best = 0;
        for (auto& kv : area) best = max(best, kv.second);
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) {
            if (g[r][c] != 0) continue;
            unordered_set<int> seen;
            int cur = 1;
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && label[nr][nc] && !seen.count(label[nr][nc])) {
                    seen.insert(label[nr][nc]); cur += area[label[nr][nc]];
                }
            }
            best = max(best, cur);
        }
        return best;
    }
    int dfs(int r, int c) {
        if (r < 0 || r >= n || c < 0 || c >= n || g[r][c] != 1 || label[r][c]) return 0;
        label[r][c] = idx;
        return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1);
    }
};

Explanation

A naive approach would flip each 0 and re-scan the whole grid to measure the island, which is very slow. The smart idea is to measure every island once up front, then for each 0 just add up the areas of the islands touching it.

Phase 1: we DFS over the grid and give each connected blob of 1s a unique idx stored in label, while recording that island's size in area[idx]. Now every land cell knows which island it belongs to.

Phase 2: for each 0 cell, we look at its four neighbors, collect their distinct island ids in a seen set (so we never count the same island twice), and compute 1 + sum of those areas. That is the island we would get by flipping this cell.

We keep the running best, also seeded with the largest existing island in case flipping helps nothing.

Example: grid = [[1,0],[0,1]] has two islands of size 1. Flipping cell (0,1) touches both, giving 1 + 1 + 1 = 3, which is the answer.

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