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
- The classic result: the answer is always 0, 1, or 2.
- 0 -- the grid is already disconnected (or has no land).
- 1 -- removing some single land cell disconnects it.
- 2 -- otherwise; removing a corner cell and then an adjacent one always suffices.
- 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.