> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Number of Days to Disconnect Island

> Tested Python solution for LeetCode 1568 with 40 pytest cases. Generate a practice environment with lcpy.

LeetCode 1568, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Matrix](/catalog/topics/matrix), Strongly Connected Component, Articulation Point. [View on LeetCode](https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/description/).

Generate this problem as a practice environment: tested reference solution, 40 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1568   # by problem number
lcpy gen -s minimum_number_of_days_to_disconnect_island   # by problem name
```

## Problem

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*.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/12/24/land1.jpg)

```
Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
```

![Example 2](https://assets.leetcode.com/uploads/2021/12/24/land2.jpg)

```
Input: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.
```

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_number_of_days_to_disconnect_island/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_number_of_days_to_disconnect_island/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m^2 * n^2) - at most m*n single-cell trials, each O(m*n)
    # Space: O(m * n)
    def min_days(self, grid: list[list[int]]) -> int:
        if self._count_islands(grid) != 1:
            return 0

        m, n = len(grid), len(grid[0])
        for row in range(m):
            for col in range(n):
                if grid[row][col] != 1:
                    continue
                grid[row][col] = 0
                connected = self._count_islands(grid) == 1
                grid[row][col] = 1
                if not connected:
                    return 1
        return 2

    def _count_islands(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        seen = [[False] * n for _ in range(m)]
        count = 0
        for start_row in range(m):
            for start_col in range(n):
                if grid[start_row][start_col] != 1 or seen[start_row][start_col]:
                    continue
                count += 1
                seen[start_row][start_col] = True
                stack = [(start_row, start_col)]
                while stack:
                    row, col = stack.pop()
                    for d_row, d_col in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        n_row, n_col = row + d_row, col + d_col
                        if (
                            0 <= n_row < m
                            and 0 <= n_col < n
                            and grid[n_row][n_col] == 1
                            and not seen[n_row][n_col]
                        ):
                            seen[n_row][n_col] = True
                            stack.append((n_row, n_col))
        return count
```

## Complexity

| Time | Space |
| - | - |
| O(m^2 \* n^2) - at most m*n single-cell trials, each O(m*n) | O(m \* n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.