1691. Minimum Number of Days to Disconnect Island
My accepted C++ solution to LeetCode problem 1691, Minimum Number of Days to Disconnect Island, running in 84ms.
- Difficulty: Hard
- C++
- Runtime 84ms
- Memory 19.4MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
C++
Accepted on LeetCode — runtime 84ms, memory 19.4MB, accepted 2025-12-27.
class Solution {
public:
int m, n;
int countIslands(vector<vector<int>>& grid) {
vector<vector<bool>> vis(m, vector<bool>(n, false));
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !vis[i][j]) {
dfs(grid, vis, i, j);
count++;
}
}
}
return count;
}
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 || vis[i][j]) return;
vis[i][j] = true;
dfs(grid, vis, i+1, j); dfs(grid, vis, i-1, j);
dfs(grid, vis, i, j+1); dfs(grid, vis, i, j-1);
}
int minDays(vector<vector<int>>& grid) {
m = grid.size(); n = grid[0].size();
if (countIslands(grid) != 1) return 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
grid[i][j] = 0;
if (countIslands(grid) != 1) return 1;
grid[i][j] = 1;
}
}
}
return 2;
}
};