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. Topics: Array, Depth-First Search, Breadth-First Search, Matrix, Strongly Connected Component, Articulation Point. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 40 parametrized pytest cases, and a playground notebook:

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 1s.

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

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.

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, full suite in test_solution.py:

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 mn single-cell trials, each O(mn)	O(m * n)

​

Tags

NeetCode All.