Code Implementation

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return False
            if grid[r][c] == 1:
                return True
            grid[r][c] = 1  # mark as visited
            up = dfs(r - 1, c)
            down = dfs(r + 1, c)
            left = dfs(r, c - 1)
            right = dfs(r, c + 1)
            return up and down and left and right

        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    if dfs(r, c):
                        count += 1
        return count
      

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        function<bool(int, int)> dfs = [&](int r, int c) {
            if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
            if (grid[r][c] == 1) return true;
            grid[r][c] = 1;
            bool up = dfs(r - 1, c);
            bool down = dfs(r + 1, c);
            bool left = dfs(r, c - 1);
            bool right = dfs(r, c + 1);
            return up && down && left && right;
        };
        int count = 0;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 0) {
                    if (dfs(r, c)) ++count;
                }
            }
        }
        return count;
    }
};
      

class Solution {
    public int closedIsland(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int count = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 0) {
                    if (dfs(grid, r, c, rows, cols)) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private boolean dfs(int[][] grid, int r, int c, int rows, int cols) {
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (grid[r][c] == 1) return true;
        grid[r][c] = 1;
        boolean up = dfs(grid, r - 1, c, rows, cols);
        boolean down = dfs(grid, r + 1, c, rows, cols);
        boolean left = dfs(grid, r, c - 1, rows, cols);
        boolean right = dfs(grid, r, c + 1, rows, cols);
        return up && down && left && right;
    }
}
      

var closedIsland = function(grid) {
    const rows = grid.length, cols = grid[0].length;

    function dfs(r, c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (grid[r][c] === 1) return true;
        grid[r][c] = 1;
        let up = dfs(r - 1, c);
        let down = dfs(r + 1, c);
        let left = dfs(r, c - 1);
        let right = dfs(r, c + 1);
        return up && down && left && right;
    }

    let count = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 0) {
                if (dfs(r, c)) count++;
            }
        }
    }
    return count;
};
      

Problem Description

You are given a 2D grid of integers where 0 represents land and 1 represents water. An island is a group of connected 0s (land) connected 4-directionally (up, down, left, right). A closed island is an island that is completely surrounded by water (i.e., it does not touch the grid's border at any point).

The task is to count the number of closed islands in the grid. You must ensure that each land cell is used in at most one island, and you cannot reuse elements between islands.

• Input: grid - a 2D list of integers (0s and 1s)
• Output: Integer representing the number of closed islands
• Constraints: Each land cell belongs to at most one island. Each island is counted only if it is fully surrounded by water and does not touch the grid border.

Thought Process

At first glance, the problem seems similar to counting islands in a grid, a classic DFS/BFS problem. However, the twist is that only islands which do not touch the grid border are considered "closed".

A brute-force approach would be to search for every group of connected land (0s) and, for each group, check if any part of it touches the border. If it does, it's not closed. Otherwise, it's a closed island.

To optimize, we can merge the detection and marking steps: as we traverse each island with DFS or BFS, we can simultaneously check if we ever reach the border. If so, we know immediately that this island isn't closed, saving us from extra checks.

The key insight is that an island is closed if, during traversal, none of its land cells are on the border. We can use recursion to propagate this status up as we visit each cell.

Solution Approach

• Step 1: Traverse the grid
  Loop through each cell in the grid. When you find a land cell (0), start a DFS (or BFS) traversal from there.
• Step 2: DFS/BFS traversal and marking
  For each land cell visited, mark it as visited (e.g., change it to 1). This prevents revisiting the same cell and ensures each land cell is only part of one island.
• Step 3: Detect border contact
  If during traversal you move outside the grid boundaries, that means the island touches the border and is not closed. In the recursive DFS, if any path leads out of bounds, propagate this information back up.
• Step 4: Aggregate the result
  If the DFS returns true (i.e., the island is closed), increment your closed island count.
• Step 5: Repeat
  Continue until all cells in the grid have been processed.

This approach ensures we only visit each cell once and immediately know if an island is closed or not as we traverse it.

Example Walkthrough

Consider the following grid:

    1 1 1 1 1 1 1 0
    1 0 0 0 0 1 1 0
    1 0 1 0 1 1 1 0
    1 0 0 0 0 1 0 1
    1 1 1 1 1 1 1 0
  

• We start scanning from the top-left. The first 0 we find is at (1,1).
• We start a DFS from (1,1), marking all connected 0s as visited.
• We check if any of those cells touch the border. In this case, none do, so we increment our closed island count.
• Continue scanning. The next unvisited 0 is at (3,6). We start a DFS and see that it connects to the border at (4,7), so this is not a closed island.
• After finishing, only one closed island is found (the group in the middle).

Time and Space Complexity

• Brute-force approach: For each cell, you might recursively check all possible paths around the island, leading to a time complexity of up to O((m*n)^2) in the worst case.
• Optimized approach (DFS/BFS): Each cell is visited at most once, so the time complexity is O(m*n), where m and n are the grid's dimensions.
• Space complexity: O(m*n) in the worst case for the recursion stack (DFS) or queue (BFS) if the entire grid is land.

The optimized approach is efficient and suitable for large grids.

Summary

The "Number of Closed Islands" problem is a variation of the classic island-counting task, with the added challenge of only counting islands fully surrounded by water. By using DFS or BFS to traverse each island and marking visited cells, we efficiently identify closed islands by checking border contact during traversal. The solution is elegant because it combines marking and checking in a single pass, ensuring optimal performance and clarity.