LeetCode 1568 - Minimum Number of Days to Disconnect Island

The problem gives us a binary matrix where each cell is either land (1) or water (0). Land cells that touch vertically or horizontally belong to the same island. A grid is considered connected only when there is exactly one island in the entire grid.

leetcodehardarraydepth-first-searchbreadth-first-searchmatrixstrongly-connected-component

LeetCode Problem 1568

Difficulty: 🔴 Hard
Topics: Array, Depth-First Search, Breadth-First Search, Matrix, Strongly Connected Component

Solution

Problem Understanding

The problem gives us a binary matrix where each cell is either land (1) or water (0). Land cells that touch vertically or horizontally belong to the same island. A grid is considered connected only when there is exactly one island in the entire grid.

Every day, we may convert exactly one land cell into water. Our goal is to determine the minimum number of days required to make the grid disconnected. A disconnected grid means either:

  • there are zero islands, or
  • there are two or more islands

In other words, the moment the grid no longer contains exactly one connected component of land, we are done.

The grid dimensions are at most 30 x 30, so there are at most 900 cells total. This is small enough to allow repeated graph traversals such as DFS or BFS.

A few important observations immediately simplify the problem:

  • If the grid already contains zero islands or multiple islands, the answer is 0 because it is already disconnected.
  • If removing one land cell disconnects the island, the answer is 1.
  • Otherwise, the answer is always 2.

That final observation is the key insight behind the optimal solution. It comes from graph theory. Any connected island can always be disconnected by removing at most two cells. Intuitively, if no single articulation point exists, removing two carefully chosen cells will always work.

Several edge cases are important:

  • A grid containing only water is already disconnected.
  • A grid containing exactly one land cell becomes disconnected after removing that single cell.
  • A grid with two connected cells requires two removals because removing one still leaves a single island.
  • Thin structures such as lines or bridges may contain articulation points, making the answer 1.

Approaches

Brute Force Approach

The brute force solution tries every possible sequence of removals.

First, we check whether the grid is already disconnected. If it is, return 0.

Otherwise, for every land cell:

  1. Temporarily remove it.
  2. Count the number of islands using DFS or BFS.
  3. If the grid becomes disconnected, return 1.
  4. Restore the cell.

If no single removal works, we could theoretically try all pairs of land cells:

  1. Remove two cells.
  2. Recompute connectivity.
  3. Check whether the grid becomes disconnected.

This approach is correct because it exhaustively checks every possible set of removals. However, testing all pairs is unnecessarily expensive.

If there are k land cells, checking all pairs requires O(k²) attempts, and each attempt performs a full DFS over the grid. Since the grid can contain up to 900 cells, this becomes far too slow.

Key Insight

The crucial observation is that the answer can only be 0, 1, or 2.

Why?

  • 0 if the grid is already disconnected.
  • 1 if there exists an articulation point, meaning a single land cell whose removal disconnects the island.
  • Otherwise 2.

This property comes from connectivity theory on grids. A connected island without articulation points can always be disconnected using two removals.

Therefore, instead of checking all pairs, we only need:

  1. Initial connectivity check
  2. Try removing each land cell once
  3. If none work, return 2

This dramatically reduces the complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O((mn)³) O(mn) Tries all pairs of removals and recomputes islands repeatedly
Optimal O((mn)²) O(mn) Only checks single-cell removals because answer is at most 2

Algorithm Walkthrough

  1. Create a helper function count_islands() that counts how many connected components of land exist in the grid.

This function performs DFS from every unvisited land cell. Each DFS marks an entire island as visited. 2. Call count_islands() on the original grid.

If the result is not exactly 1, the grid is already disconnected, so return 0. 3. Iterate through every cell in the grid.

Whenever we encounter a land cell:

  • temporarily change it from 1 to 0
  • recompute the number of islands
  • if the result is not exactly 1, return 1
  • restore the cell back to 1
  1. If no single removal disconnects the island, return 2.

The DFS is a natural choice because the grid is small and we only need connectivity information. BFS would also work equally well.

Why it works

The algorithm checks all possible single-cell removals. If any removal disconnects the island, then one day is sufficient.

If none do, the island has no articulation point. A known property of connected grid graphs guarantees that at most two removals are always enough to disconnect the island. Therefore returning 2 is always correct.

Python Solution

from typing import List

class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def count_islands() -> int:
            visited = [[False] * cols for _ in range(rows)]

            def dfs(r: int, c: int) -> None:
                visited[r][c] = True

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if (
                        0 <= nr < rows
                        and 0 <= nc < cols
                        and not visited[nr][nc]
                        and grid[nr][nc] == 1
                    ):
                        dfs(nr, nc)

            island_count = 0

            for r in range(rows):
                for c in range(cols):
                    if grid[r][c] == 1 and not visited[r][c]:
                        island_count += 1
                        dfs(r, c)

            return island_count

        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

The implementation starts by defining the four possible movement directions used during DFS traversal.

The count_islands() helper constructs a visited matrix and scans the entire grid. Whenever it finds an unvisited land cell, it launches DFS to mark the entire connected component. Each DFS call corresponds to one island.

The main algorithm first checks whether the grid is already disconnected. If so, it immediately returns 0.

Next, the code iterates through every land cell and temporarily removes it. After each removal, it recomputes the number of islands. If the grid no longer contains exactly one island, then that single removal successfully disconnects the grid, so the answer is 1.

If all single-cell removals fail, the algorithm returns 2.

Go Solution

func minDays(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	var dfs func(int, int, [][]bool)

	dfs = func(r int, c int, visited [][]bool) {
		visited[r][c] = true

		for _, dir := range directions {
			nr := r + dir[0]
			nc := c + dir[1]

			if nr >= 0 && nr < rows &&
				nc >= 0 && nc < cols &&
				!visited[nr][nc] &&
				grid[nr][nc] == 1 {

				dfs(nr, nc, visited)
			}
		}
	}

	countIslands := func() int {
		visited := make([][]bool, rows)

		for i := range visited {
			visited[i] = make([]bool, cols)
		}

		islandCount := 0

		for r := 0; r < rows; r++ {
			for c := 0; c < cols; c++ {
				if grid[r][c] == 1 && !visited[r][c] {
					islandCount++
					dfs(r, c, visited)
				}
			}
		}

		return islandCount
	}

	if countIslands() != 1 {
		return 0
	}

	for r := 0; r < rows; r++ {
		for 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
}

The Go implementation follows exactly the same logic as the Python version.

Instead of Python sets or nested functions with closures, Go uses a visited 2D slice and a recursive DFS function. Since Go does not support default nested recursion syntax as cleanly as Python, the DFS function is declared as a variable before assignment.

The grid is modified in place during temporary removals and restored afterward.

Because the maximum grid size is only 30 x 30, recursion depth is safe in both languages.

Worked Examples

Example 1

Input:

[
  [0,1,1,0],
  [0,1,1,0],
  [0,0,0,0]
]

Initial island count:

Step Grid State Island Count
Initial original grid 1

Now try removing each land cell.

Remove (0,1):

[
  [0,0,1,0],
  [0,1,1,0],
  [0,0,0,0]
]

The remaining land is still connected.

Removed Cell Island Count
(0,1) 1

Remove (0,2):

[
  [0,1,0,0],
  [0,1,1,0],
  [0,0,0,0]
]

Still connected.

Removed Cell Island Count
(0,2) 1

Remove (1,1):

[
  [0,1,1,0],
  [0,0,1,0],
  [0,0,0,0]
]

Still connected.

Removed Cell Island Count
(1,1) 1

Remove (1,2):

[
  [0,1,1,0],
  [0,1,0,0],
  [0,0,0,0]
]

Still connected.

Since no single removal disconnects the island, answer is 2.

Example 2

Input:

[[1,1]]

Initial island count:

Step Island Count
Initial 1

Try removing first cell:

[[0,1]]

Still exactly one island.

Try removing second cell:

[[1,0]]

Still exactly one island.

No single removal works, so answer is 2.

Complexity Analysis

Measure Complexity Explanation
Time O((mn)²) We run DFS over the entire grid once for each land cell
Space O(mn) Visited matrix and recursion stack

Let N = m × n.

The count_islands() function takes O(N) time because every cell is visited at most once.

In the worst case, every cell is land, so we perform up to N removal attempts. Each attempt recomputes islands in O(N) time.

Therefore total complexity is O(N²).

The auxiliary space comes from the visited matrix and DFS recursion depth.

Test Cases

sol = Solution()

# Example 1
assert sol.minDays([
    [0,1,1,0],
    [0,1,1,0],
    [0,0,0,0]
]) == 2  # requires two removals

# Example 2
assert sol.minDays([
    [1,1]
]) == 2  # two adjacent cells need two removals

# Already disconnected
assert sol.minDays([
    [1,0],
    [0,1]
]) == 0  # already multiple islands

# Single land cell
assert sol.minDays([
    [1]
]) == 1  # removing one cell leaves zero islands

# All water
assert sol.minDays([
    [0,0],
    [0,0]
]) == 0  # already disconnected

# Line with articulation point
assert sol.minDays([
    [1,1,1]
]) == 1  # middle cell disconnects island

# Square block
assert sol.minDays([
    [1,1],
    [1,1]
]) == 2  # no articulation point

# Complex shape with articulation point
assert sol.minDays([
    [1,1,0],
    [0,1,0],
    [0,1,1]
]) == 1  # bridge cell disconnects

# Large connected island
assert sol.minDays([
    [1,1,1],
    [1,1,1],
    [1,1,1]
]) == 2  # highly connected structure

# Multiple islands initially
assert sol.minDays([
    [1,0,1],
    [0,0,0],
    [1,0,1]
]) == 0  # already disconnected
Test Why
[[0,1,1,0],[0,1,1,0],[0,0,0,0]] Validates case requiring two removals
[[1,1]] Small connected structure needing two days
[[1,0],[0,1]] Already disconnected grid
[[1]] Single-cell island
[[0,0],[0,0]] Entirely water
[[1,1,1]] Simple articulation point
[[1,1],[1,1]] Dense structure with no articulation point
[[1,1,0],[0,1,0],[0,1,1]] Bridge-like structure
3x3 all land Large connected component
Multiple isolated cells Tests initial disconnected detection

Edge Cases

A grid containing no land is an important corner case. Since the definition of connected requires exactly one island, a grid with zero islands is already disconnected. A naive implementation might incorrectly assume that no removals are needed only when multiple islands exist. The implementation correctly handles this because the initial island count check returns anything other than 1.

A single land cell is another tricky scenario. Removing that cell produces zero islands, which counts as disconnected. Some implementations mistakenly expect at least two components after removal. The algorithm instead checks whether the island count is not equal to 1, which correctly treats zero islands as disconnected.

Dense blocks of land such as a 2x2 square or larger rectangles can also be problematic. Removing any single cell still leaves the remaining land connected. A naive heuristic based on low-degree cells may incorrectly return 1. The implementation avoids this issue by explicitly recomputing connectivity after every removal attempt.

Thin bridge-like structures are especially important because they contain articulation points. Removing the bridge splits the island into multiple components. The DFS-based connectivity check correctly identifies this situation and returns 1.