1568. Minimum Number of Days to Disconnect Island
Approach
Check 0 days (already disconnected), then try removing each land cell (1 day), otherwise answer is 2.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
// Approach: Check 0 days (already disconnected), then try removing each land cell (1 day), otherwise answer is 2.
// Time: O((mn)²) Space: O(mn)
public class Solution
{
public int MinDays(int[][] grid)
{
if (Disconnected(grid))
return 0;
// Try to remove 1 land.
for (int i = 0; i < grid.Length; ++i)
for (int j = 0; j < grid[0].Length; ++j)
if (grid[i][j] == 1)
{
grid[i][j] = 0;
if (Disconnected(grid))
return 1;
grid[i][j] = 1;
}
// Remove 2 lands.
return 2;
}
private readonly int[][] dirs = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
private bool Disconnected(int[][] grid)
{
int islandsCount = 0;
bool[][] seen = new bool[grid.Length][];
for (int i = 0; i < grid.Length; i++)
{
seen[i] = new bool[grid[0].Length];
}
for (int i = 0; i < grid.Length; ++i)
for (int j = 0; j < grid[0].Length; ++j)
{
if (grid[i][j] == 0 || seen[i][j])
continue;
if (++islandsCount > 1)
return true;
Dfs(grid, i, j, seen);
}
return islandsCount != 1;
}
private void Dfs(int[][] grid, int i, int j, bool[][] seen)
{
seen[i][j] = true;
foreach (var dir in dirs)
{
int x = i + dir[0];
int y = j + dir[1];
if (x < 0 || x == grid.Length || y < 0 || y == grid[0].Length)
continue;
if (grid[x][y] == 0 || seen[x][y])
continue;
Dfs(grid, x, y, seen);
}
}
}