Minimum Number of Days to Disconnect Island

Minimum Number of Days to Disconnect Island - Problem

Array Depth-First Search Breadth-First Search Matrix Strongly Connected Component Hard

You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1's.

The grid is said to be connected if we have exactly one island, otherwise is said disconnected.

In one day, we are allowed to change any single land cell (1) into a water cell (0).

Return the minimum number of days to disconnect the grid.

Input & Output

Example 1 — Single Critical Point

$ Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

› Output: 2

💡 Note: The grid forms one connected island. No single cell removal disconnects it, so we need to remove 2 cells to create separation.

Example 2 — Already Disconnected

$ Input: grid = [[1,1,0,1,1],[1,1,1,1,1],[1,1,0,1,1],[1,1,1,1,1]]

› Output: 1

💡 Note: Removing the center cell at (1,2) or (2,2) would disconnect the island into multiple parts.

Example 3 — Small Island

$ Input: grid = [[1,0,1,0]]

› Output: 0

💡 Note: There are already 2 separate islands, so the grid is already disconnected.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 30
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Binary matrix with 1s forming connected island

Find Disconnection

Remove minimum cells to create multiple islands

Output Result

Return minimum number of days needed

Key Takeaway

🎯 Key Insight: Mathematical theorem proves answer is always 0, 1, or 2 - check articulation points efficiently

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that the answer can only be 0, 1, or 2. Use DFS to count islands and check for articulation points efficiently. Optimized approach runs in O(mn) time by checking edge cells first, which are most likely to be critical connection points.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(m²n²(m+n))	O(mn)	Try removing 1 cell, then all pairs of cells until grid disconnects
Optimized - Mathematical Insight	O(mn)	O(mn)	Answer can only be 0, 1, or 2 based on grid structure

Brute Force - Try All Combinations — Algorithm Steps

Count islands initially - if not exactly 1, return 0
Try removing each land cell one by one
For each removal, count islands - if not 1, return 1
Try all pairs of land cells and check connectivity
If any pair works, return 2

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Check

Count islands in original grid

Try Single Cells

Remove each land cell and test connectivity

Result

Return minimum days needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int m, n;
int** grid;
bool** visited;

void dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] == 0) return;
    visited[i][j] = true;
    int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    for (int d = 0; d < 4; d++) {
        dfs(i + dirs[d][0], j + dirs[d][1]);
    }
}

int countIslands() {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }
    
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                dfs(i, j);
                count++;
            }
        }
    }
    return count;
}

int solution() {
    if (countIslands() != 1) return 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                grid[i][j] = 0;
                if (countIslands() != 1) return 1;
                grid[i][j] = 1;
            }
        }
    }
    
    return 2;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[1,1,0],[0,1,0],[0,0,1]] format
    // Count dimensions first
    int rows = 0, cols = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && i > 0 && line[i-1] != '[') rows++;
        if (rows == 1 && (line[i] == ',' || line[i] == ']')) cols++;
    }
    
    m = rows;
    n = cols;
    
    grid = (int**)malloc(m * sizeof(int*));
    visited = (bool**)malloc(m * sizeof(bool*));
    for (int i = 0; i < m; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
        visited[i] = (bool*)malloc(n * sizeof(bool));
    }
    
    // Parse values
    int row = 0, col = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] >= '0' && line[i] <= '9') {
            grid[row][col++] = line[i] - '0';
            if (col == n) {
                col = 0;
                row++;
            }
        }
    }
    
    printf("%d\n", solution());
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²(m+n))

O(mn) pairs of cells to try, each requiring O(mn) DFS to count islands

⚠ Quadratic Growth

Space Complexity

O(mn)

DFS recursion stack and visited array for connectivity check

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler