⚡Flashcard Drill➔
NeetCode #649LC-1568HardAdvanced Graphs
← Back to All Problems

#649 · #1568 · Minimum Number of Days to Disconnect Island(使陆地分离的最少天数)

📌 Problem Statement & Constraints

You are given an m x n binary grid where 1 is land. In one day you may change one land cell to water. Return the minimum number of days to disconnect the island (make it not connected). Constraints: 1 <= m, n <= 30.

💡 Core Algorithmic Approaches

  1. The classic result: the answer is always 0, 1, or 2.
  2. 0 -- the grid is already disconnected (or has no land).
  3. 1 -- removing some single land cell disconnects it.
  4. 2 -- otherwise; removing a corner cell and then an adjacent one always suffices.
  5. So: check 0, then brute-force every single removal, and default to 2.

💻 Benchmark Python3 Implementation

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

        def count_islands() -> int:
            seen = [[False] * n for _ in range(m)]
            cnt = 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1 and not seen[i][j]:
                        cnt += 1
                        stack = [(i, j)]
                        seen[i][j] = True
                        while stack:
                            r, c = stack.pop()
                            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                                nr, nc = r + dr, c + dc
                                if (0 <= nr < m and 0 <= nc < n
                                        and grid[nr][nc] == 1 and not seen[nr][nc]):
                                    seen[nr][nc] = True
                                    stack.append((nr, nc))
            return cnt

        if count_islands() != 1:
            return 0                       # already disconnected
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    grid[i][j] = 0         # try removing this cell
                    if count_islands() != 1:
                        grid[i][j] = 1
                        return 1
                    grid[i][j] = 1         # restore
        return 2                           # two removals always suffice

⚡ Complexity Deep Dive

⏱️ Time Complexity
O((m*n)^2): one island count per candidate cell.
💾 Space Complexity
O(m * n) for the visited grid.

⚠️ Interview Pitfalls & Follow-ups

  • Trying to brute-force two removals: O((m*n)^3); the 0/1/2 theorem makes it unnecessary.
  • Forgetting to restore the grid: later candidates would see a modified grid.
  • Assuming a single-cell island needs 0 days: removing it leaves no land, which counts as disconnected (0 islands != 1).
  • Returning 1 when the grid has no land: count_islands() returns 0, so the answer is 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems