Minimum Number of Days to Disconnect Island

Leetcode Problem:

• Minimum Number of Days to Disconnect Island

Summary

• This is a problem of finding the minimum number of days to disconnect a grid of land and water cells.

Approach

• The solution uses a breadth-first search (BFS) approach to find the number of islands in the grid, and then iteratively tries to disconnect the islands by changing the land cells to water cells
• The time complexity is O(R*C) for the BFS and O(R*C) for the iterative process, resulting in a total time complexity of O(R*C).

Complexity

• O(R*C)

Explain

• The solution first defines the grid size and the map of land and water cells
• It then defines a helper function to perform BFS and find the number of islands
• The main function iteratively tries to disconnect the islands by changing the land cells to water cells, and returns the minimum number of days required to disconnect the grid
• The time complexity is dominated by the BFS and iterative process, which is O(R*C) for each call
• The space complexity is also O(R*C) for the visited matrix and the recursive call stack.

Solution Code:

class Solution {
public:
    int R;
    int C;
    vector> map;
    void fill(int r, int c, bool visited[][31]){
        if (r < 0 || r >= R || c < 0 || c >= C || map[r][c] == 0 || map[r][c] == 3 || visited[r][c]){
            return;
        }
        visited[r][c]  = true;
        fill(r + 1, c, visited);
        fill(r, c + 1, visited);
        fill(r - 1, c, visited);
        fill(r, c - 1, visited);
    }
    int getIsland(){
        bool visited[31][31];
        int cnt = 0;
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                visited[i][j] = false;
            }
        }
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                if(map[i][j] == 1 && !visited[i][j]){
                    cnt++;
                    fill(i, j, visited);
                }
            }
        }
        return cnt;
    }
    bool closeWater(int r, int c){
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        for(int i = 0 ;i  < 4; i++){
            int nr = r + dy[i];
            int nc = c + dx[i];
            if(nr < 0 || nr >= R || nc < 0 || nc >= C){
                return true;
            }
            if (map[nr][nc] == 0){
                return true;
            }
        }
        return false;
    }
    int minDays(vector>& grid) {
        R = grid.size();
        C = grid[0].size();
        map = grid;
        int ans = 0;
        int island_cnt = getIsland();
        while(island_cnt == 1){
            for(int i = 0 ; i < R; i++){
                for(int j = 0 ; j < C; j++){
                    if(map[i][j] == 0) continue;
                    map[i][j] = 0;
                    int tmpCnt = getIsland();
                    if(tmpCnt != 1) return ans + 1;
                    map[i][j] = 1;
                }
            }
           
            return 2;
        }
        
        return ans;
    }
};