Minimum Number of Days to Disconnect Island

hard graph dfs matrix

Problem

You are given a binary grid where 1 is land and 0 is water. The grid is connected when its land cells form exactly one island (cells joined up, down, left or right). On each day you may flip one land cell to water. Return the minimum number of days needed to make the grid disconnected — meaning the land forms zero islands or two-or-more islands.

A useful fact bounds the answer: any island can always be cut apart within two days by removing a corner cell and one of its neighbours, so the answer is only ever 0, 1 or 2. That lets us simply test the cheap cases first.

Input

1 1
1 0

Output1

The three land cells form one island. Removing the top-left cell leaves cells (0,1) and (1,0), which only touch diagonally — so they become two separate islands. One day is enough.

grid (rows separated by ';', cells by space or comma)

def min_days(grid):
    rows, cols = len(grid), len(grid[0])

    def count_islands():
        seen = [[False] * cols for _ in range(rows)]
        islands = 0
        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return
            if grid[r][c] != 1 or seen[r][c]:
                return
            seen[r][c] = True
            dfs(r + 1, c); dfs(r - 1, c)
            dfs(r, c + 1); dfs(r, c - 1)
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1 and not seen[r][c]:
                    islands += 1
                    dfs(r, c)
        return islands

    if count_islands() != 1:
        return 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                grid[r][c] = 0
                if count_islands() != 1:
                    grid[r][c] = 1
                    return 1
                grid[r][c] = 1
    return 2

function minDays(grid) {
  const rows = grid.length, cols = grid[0].length;
  function countIslands() {
    const seen = grid.map(row => row.map(() => false));
    let islands = 0;
    function dfs(r, c) {
      if (r < 0 || c < 0 || r >= rows || c >= cols) return;
      if (grid[r][c] !== 1 || seen[r][c]) return;
      seen[r][c] = true;
      dfs(r + 1, c); dfs(r - 1, c);
      dfs(r, c + 1); dfs(r, c - 1);
    }
    for (let r = 0; r < rows; r++)
      for (let c = 0; c < cols; c++)
        if (grid[r][c] === 1 && !seen[r][c]) { islands++; dfs(r, c); }
    return islands;
  }
  if (countIslands() !== 1) return 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === 1) {
        grid[r][c] = 0;
        if (countIslands() !== 1) { grid[r][c] = 1; return 1; }
        grid[r][c] = 1;
      }
  return 2;
}

class Solution {
    int[][] g; int R, C; boolean[][] seen;
    public int minDays(int[][] grid) {
        g = grid; R = grid.length; C = grid[0].length;
        if (countIslands() != 1) return 0;
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                if (g[r][c] == 1) {
                    g[r][c] = 0;
                    if (countIslands() != 1) { g[r][c] = 1; return 1; }
                    g[r][c] = 1;
                }
        return 2;
    }
    int countIslands() {
        seen = new boolean[R][C];
        int islands = 0;
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                if (g[r][c] == 1 && !seen[r][c]) { islands++; dfs(r, c); }
        return islands;
    }
    void dfs(int r, int c) {
        if (r < 0 || c < 0 || r >= R || c >= C) return;
        if (g[r][c] != 1 || seen[r][c]) return;
        seen[r][c] = true;
        dfs(r + 1, c); dfs(r - 1, c);
        dfs(r, c + 1); dfs(r, c - 1);
    }
}

int R, C;
vector<vector<int>> seen;
void dfs(vector<vector<int>>& g, int r, int c) {
    if (r < 0 || c < 0 || r >= R || c >= C) return;
    if (g[r][c] != 1 || seen[r][c]) return;
    seen[r][c] = 1;
    dfs(g, r + 1, c); dfs(g, r - 1, c);
    dfs(g, r, c + 1); dfs(g, r, c - 1);
}
int countIslands(vector<vector<int>>& g) {
    seen.assign(R, vector<int>(C, 0));
    int islands = 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (g[r][c] == 1 && !seen[r][c]) { islands++; dfs(g, r, c); }
    return islands;
}
int minDays(vector<vector<int>> grid) {
    R = grid.size(); C = grid[0].size();
    if (countIslands(grid) != 1) return 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == 1) {
                grid[r][c] = 0;
                if (countIslands(grid) != 1) { grid[r][c] = 1; return 1; }
                grid[r][c] = 1;
            }
    return 2;
}

Explanation

"Disconnected" here means the land is not exactly one island — it is either gone entirely (zero islands) or split into two or more pieces. We want the fewest cells we must turn into water to reach that state.

The surprising part is that the answer can never be more than two. Pick any corner cell of the island; it touches the rest of the land through at most two neighbours. Removing those neighbours always severs the corner from the body, so two days is always enough. That bounds the whole problem to three possible answers: 0, 1, or 2.

With such a tiny range, we just check the cheap cases in order. First we count the islands with a flood-fill DFS. If the grid is already not one island (zero or two-plus), it is disconnected right away, so the answer is 0.

Otherwise we try every single removal: temporarily flip one land cell to water, recount the islands, then flip it back. If any one removal leaves something other than a single island, then one day suffices and we return 1.

If no single cell does the job, we fall back on the guarantee above and return 2.

Walking the example [[1,1],[1,0]]: it starts as one island, so the answer is not 0. We then try removing the top-left cell. The remaining cells (0,1) and (1,0) only meet at a diagonal, which does not count as connected, so we now have two islands — disconnected with a single removal. The answer is 1.

Time: O((R · C)²) Space: O(R · C)