1254. Number of Closed Islands

📝 Problem Details

• Title: 1254. Number of Closed Islands
• Link: https://leetcode.com/problems/number-of-closed-islands/
• Difficulty: Medium
• Tags/Categories: Graphs DFS BFS Matrix

input matrix grid consisting of 0s (land) and 1s (water) island: vertically and horizontally connected groups of 0s closed island: an island completely surrounded by 1s return the number of closed islands

💭What Were My Initial Thoughts?

- we need to count islands of 0s that are completely surrounded by 1s
	- this also means they dont touch the border
- dfs is a good fit for exploring connected regions in a grid
- idea:
	1. first eliminate all "open" islands - any land connected to a border cannot be a closed island
	2. then iterate through the inner grid and count isalnds using dfs
	3. mark visited cells to avoid recomputation

💡 Explanation of Solution

1. traverse all boundary cells
	- if 0 is found on the border, its a part of an open island
	- run dfs from there to mark all connected land as visited (i.e., convert to 1)

2. after cleaning up open islands, iterate through the grid again
	- when you find a 0, its a closed island 
	- increment count and run dfs to mark all its land as visited 

3. use in-place marking (e.g. set 0 --> 1) to avoid using extra visited array

⌛ Complexity Analysis

Time Complexity: O(n * m)
Space Complexity: O(n * m)
- for worst case recursive call stack 
- O(1) if we ignore the call stack

💻 Implementation of Solution

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int r, int c) {
        int rows = grid.size();
        int cols = grid[0].size();
 
        // base case: out of bounds water
        if(r < 0
        || r >= rows
        || c < 0
        || c >= cols
        || grid[r][c] == 1) return;
 
        grid[r][c] = 1; // mark as visited
 
        // explore all 4 directions
        dfs(grid, r+1, c);
        dfs(grid, r-1, c);
        dfs(grid, r, c+1);
        dfs(grid, r, c-1);
    }
 
    int closedIsland(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
 
        // 1. remove open islands (land connected to border)
        for(int r = 0; r < rows; r++) {
            if(grid[r][0] == 0) dfs(grid, r, 0);
            if(grid[r][cols-1] == 0) dfs(grid, r, cols - 1);
        }
        for (int c = 0; c < cols; ++c) {
            if (grid[0][c] == 0) dfs(grid, 0, c);
            if (grid[rows - 1][c] == 0) dfs(grid, rows - 1, c);
        }
 
        // 2. count remaining closed islands
        int count = 0;
        for (int r = 1; r < rows - 1; ++r) {
            for (int c = 1; c < cols - 1; ++c) {
                if (grid[r][c] == 0) {
                    dfs(grid, r, c);
                    count++;
                }
            }
        }
 
        return count;
    }
};