Minimum Number of Days to Disconnect Island: The Answer Is Always 0, 1, or 2

You are given an m x n binary grid where 1 represents land and 0 represents water. An island is a maximal group of 1s connected 4-directionally. The grid is said to be connected if it has exactly one island. In one day, you can change any single land cell to water. Return the minimum number of days to disconnect the grid (make it so the grid does not have exactly one island).

This is LeetCode 1568: Minimum Number of Days to Disconnect Island, and it looks intimidating at first. But there is a beautiful insight that makes the solution surprisingly clean.

Why this problem matters

Grid connectivity problems show up constantly in interviews. This one adds a twist: instead of finding connected components, you need to break one. It tests whether you can reason about the structure of a problem before writing code. Once you see the key insight, the brute-force approach becomes elegant enough to pass.

The technique here, counting connected components after toggling cells, is a building block for problems involving bridges, articulation points, and graph resilience.

The key insight

The answer is always 0, 1, or 2. Here is why:

• 0 days: If the grid already has zero islands or more than one island, it is already disconnected. Return 0.
• 1 day: If removing a single land cell breaks the one island into two or more pieces (or eliminates it entirely), return 1. This cell is an articulation point of the island.
• 2 days: If neither of the above applies, return 2. You can always disconnect any island by removing at most 2 cells. Think about a corner cell of the island: you can remove the two neighbors that connect it to the rest, isolating it. Every island has a corner, so 2 always works.

This means you never need to search beyond 2. You just check 0, then check 1, and if neither works, return 2.

The solution

def minDays(grid: list[list[int]]) -> int:
    def count_islands(g):
        seen = set()
        count = 0
        for r in range(len(g)):
            for c in range(len(g[0])):
                if g[r][c] == 1 and (r, c) not in seen:
                    count += 1
                    stack = [(r, c)]
                    seen.add((r, c))
                    while stack:
                        cr, cc = stack.pop()
                        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                            nr, nc = cr + dr, cc + dc
                            if 0 <= nr < len(g) and 0 <= nc < len(g[0]) and g[nr][nc] == 1 and (nr, nc) not in seen:
                                seen.add((nr, nc))
                                stack.append((nr, nc))
        return count

    if count_islands(grid) != 1:
        return 0

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

    return 2

Let's walk through what each piece does.

The count_islands helper does a standard DFS flood-fill. It scans every cell, and when it finds an unvisited land cell, it starts a new island and explores all connected land using a stack. It returns the total number of islands.

The first check handles the "0 days" case. If the grid does not have exactly one island (either zero islands or multiple islands), it is already disconnected.

The main loop handles the "1 day" case. For each land cell, we temporarily flip it to water, count the islands, and check if the result is no longer exactly one island. If flipping any single cell disconnects the grid, we return 1. We flip the cell back before trying the next one.

If no single removal works, we return 2. We know this is always sufficient because of the corner-cell argument above.

Visual walkthrough

Let's trace through a concrete example to see the algorithm in action. We will use a small 3x4 grid with a 2x2 block of land.

Notice the flow: check if already disconnected, try each single removal, and if nothing works, return 2. The brute-force approach is clean because the answer space is so small.

Complexity analysis

Time is O((m * n)^2). In the worst case, we try removing each of the m * n land cells, and for each removal we run count_islands which takes O(m * n) to scan the full grid. That gives us O(m * n) removals times O(m * n) per count.

Space is O(m * n) for the seen set inside count_islands. The DFS stack can also grow up to O(m * n) in the worst case (a single snake-shaped island).

The building blocks

1. Connected component counting

The pattern of counting distinct connected components via DFS flood-fill:

seen = set()
count = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 1 and (r, c) not in seen:
            count += 1
            dfs(r, c, seen)

This is the foundation for "Number of Islands," "Max Area of Island," and dozens of other grid problems. You scan every cell, and when you find an unvisited land cell, you increment the count and flood-fill to mark the entire island as visited.

2. Articulation point concept

The idea of testing whether removing a single node disconnects a graph. In this problem, we check it by brute force: flip each land cell to water and re-count. In more advanced graph problems, you would use Tarjan's algorithm to find articulation points in O(V + E) time. The brute-force version here is simpler and sufficient given the O(2) upper bound on the answer.

Edge cases

Before submitting, think through these scenarios:

• No land cells at all: count_islands returns 0, which is not 1. Return 0.
• Single land cell: removing it leaves 0 islands. Return 1.
• Grid is a straight line of land: removing the middle cell splits it. Return 1.
• Grid is a 2x2 block: no single removal disconnects it. Return 2.
• Already multiple islands: return 0 immediately without any removals.
• All cells are land: removing a corner cell does not disconnect it, but removing two cells from a corner does. Return 2.

From understanding to recall

You have seen the key insight: the answer is always 0, 1, or 2. The algorithm is a simple cascade of checks. But under interview pressure, the details matter. Do you check != 1 or > 1? Do you remember to flip the cell back after testing? Do you handle the "0 islands" case?

These are recall gaps, not understanding gaps. Spaced repetition is how you close them. You practice writing the count_islands helper and the removal loop from memory at increasing intervals. After a few rounds, you see "disconnect a grid" in a problem statement and the bounded-answer argument comes to mind immediately.

Related posts

• Number of Islands - The foundational grid DFS problem that teaches connected component counting
• Rotting Oranges - Multi-source BFS on a grid, another core grid traversal pattern
• Pacific Atlantic Water Flow - Multi-source exploration from grid borders, building on the same flood-fill foundations

CodeBricks breaks Minimum Number of Days to Disconnect Island into its connected component counting and cell-toggling building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid connectivity problem shows up in your interview, you do not think about it. You just write it.