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

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

✓ Brute Force - Try All Combinations

⏱️ Time: O(m²n²(m+n)) Space: O(mn)

Check if grid is already disconnected. If not, try removing each single cell and check connectivity. If still connected, try all pairs of cells.

Optimized - Mathematical Insight

⏱️ Time: O(mn) Space: O(mn)

Use mathematical insight that answer is always 0 (already disconnected), 1 (articulation point exists), or 2 (maximum for any connected graph). Check articulation points efficiently.

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);
    
    // Remove newline if present
    int len = strlen(line);
    if (len > 0 && line[len-1] == '\n') {
        line[len-1] = '\0';
        len--;
    }
    
    // Parse dimensions first
    m = 0; // number of rows
    n = 0; // number of columns
    
    // Count rows by counting inner arrays []
    bool in_inner_array = false;
    for (int i = 0; i < len; i++) {
        if (line[i] == '[' && i > 0) {
            in_inner_array = true;
            m++;
        }
    }
    
    // Count columns by counting elements in first row
    bool first_row = true;
    in_inner_array = false;
    for (int i = 0; i < len; i++) {
        if (line[i] == '[' && i > 0) {
            in_inner_array = true;
            if (!first_row) break;
        } else if (line[i] == ']' && in_inner_array) {
            in_inner_array = false;
            first_row = false;
        } else if (in_inner_array && first_row && (line[i] >= '0' && line[i] <= '9')) {
            n++;
        }
    }
    
    // Allocate memory
    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;
    in_inner_array = false;
    
    for (int i = 0; i < len; i++) {
        if (line[i] == '[' && i > 0) {
            in_inner_array = true;
            col = 0;
        } else if (line[i] == ']' && in_inner_array) {
            in_inner_array = false;
            row++;
        } else if (in_inner_array && (line[i] >= '0' && line[i] <= '9')) {
            grid[row][col++] = line[i] - '0';
        }
    }
    
    printf("%d\n", solution());
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(grid[i]);
        free(visited[i]);
    }
    free(grid);
    free(visited);
    
    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

✓ Linear 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

Minimum Number of Days to Disconnect Island - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler