# Number of Closed Islands
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-closed-islands)
Canonical: https://scaleengineer.com/dsa/problems/number-of-closed-islands
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## Problem
Given a 2D `grid` consists of `0s` (land) and `1s` (water). An _island_ is a maximal 4-directionally connected group of `0s` and a _closed island_ is an island **totally** (all left, top, right, bottom) surrounded by `1s.`

Return the number of _closed islands_.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-closed-islands/image0.png)

**Input:** 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]]
**Output:** 2
**Explanation:** 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

**Example 2:**

![](https://assets.glich.co/dsa/number-of-closed-islands/image1.png)

**Input:** grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
**Output:** 1

**Example 3:**

**Input:** grid = [[1,1,1,1,1,1,1],
               [1,0,0,0,0,0,1],
               [1,0,1,1,1,0,1],
               [1,0,1,0,1,0,1],
               [1,0,1,1,1,0,1],
               [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
**Output:** 2

**Constraints:**

* `1 <= grid.length, grid[0].length <= 100`
* `0 <= grid[i][j] <=1`

# Approaches
## Brute-Force Traversal for Each Island
This approach iterates through the grid to find the start of a potential island (a '0'). Once an unvisited land cell is found, it initiates a traversal (like Depth First Search or Breadth First Search) to find all connected land cells that form the island. During the traversal, it checks if any cell of the island lies on the grid's boundary. If no cell touches the boundary after the entire island is explored, it's counted as a closed island. A separate `visited` array is used to keep track of visited cells to avoid redundant work.
**Time:** O(M * N), where M is the number of rows and N is the number of columns. Each cell is visited a constant number of times. · **Space:** O(M * N) for the `visited` array and the recursion stack in the worst-case scenario, where M is the number of rows and N is the number of columns.
**Pros:** Conceptually straightforward, directly follows the problem definition.
**Cons:** Requires an auxiliary `visited` array, which consumes extra space.; The traversal logic is coupled with the boundary checking logic, which can be slightly less clean than separating the concerns.
### Explanation
We'll use a 2D `visited` array to keep track of cells we've already processed. We iterate through every cell `(i, j)` of the grid. If we find a land cell (`grid[i][j] == 0`) that has not been visited (`visited[i][j] == false`), we know we've found a new island. We then start a DFS from this cell. The DFS will explore the entire island and simultaneously check if it's a closed island. We use a boolean flag, `isClosed`, initialized to `true` before starting the DFS for a new island. The DFS function will be designed to turn this flag to `false` if it ever encounters a cell on the grid's border.

The DFS function takes the current cell's coordinates `(r, c)` as input. It first checks for boundary conditions for the island itself. If the current cell `(r, c)` is on the border of the grid, it means the island is not closed, so we set `isClosed = false`. It marks the current cell as visited and then recursively calls itself for all 4-directionally adjacent land cells. After the DFS for the island is complete, we check the `isClosed` flag. If it's still `true`, we increment our count of closed islands. This process continues until all cells in the grid have been visited.

```java
class Solution {
    private boolean isClosed;
    private int rows, cols;
    private int[][] grid;
    private boolean[][] visited;

    public int closedIsland(int[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
        this.visited = new boolean[rows][cols];
        int closedIslandCount = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0 && !visited[i][j]) {
                    // Found a new island, check if it's closed
                    isClosed = true;
                    dfs(i, j);
                    if (isClosed) {
                        closedIslandCount++;
                    }
                }
            }
        }
        return closedIslandCount;
    }

    private void dfs(int r, int c) {
        // Base cases for stopping the recursion
        if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || grid[r][c] == 1) {
            return;
        }

        // If a land cell is on the border, the island is not closed
        if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) {
            isClosed = false;
        }

        visited[r][c] = true;

        // Explore neighbors
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }
}
```
### Algorithm
- Initialize `count = 0`.
- Create a `visited` 2D array of the same dimensions as `grid`, initialized to `false`.
- Iterate through each cell `(i, j)` in the `grid`.
- If `grid[i][j] == 0` and `visited[i][j]` is `false`:
    - This is a new island. Initialize a boolean flag `isCurrentIslandClosed = true`.
    - Start a traversal (DFS/BFS) from `(i, j)`.
    - During traversal, mark visited cells in the `visited` array.
    - If any cell of the island is on the grid boundary (i.e., `i=0`, `i=rows-1`, `j=0`, or `j=cols-1`), set `isCurrentIslandClosed = false`.
    - After the traversal for the current island is complete, if `isCurrentIslandClosed` is `true`, increment `count`.
- Return `count`.

## Two-Pass Approach: Sink Border Islands First
This is a more elegant and often preferred approach. The core idea is that any island connected to the border of the grid cannot be a closed island. We can first eliminate all such islands. This is done by iterating over the border cells of the grid. If a border cell is land ('0'), we start a traversal (DFS/BFS) from it and "sink" all connected land cells by changing their value to '1' (water). After this first pass, any remaining '0's in the grid must belong to closed islands. A second pass is then made to count these remaining islands.
**Time:** O(M * N), where M is the number of rows and N is the number of columns. The grid is traversed at most twice, and each cell is processed a constant number of times across all DFS calls. · **Space:** O(M * N) in the worst case for the recursion stack depth. This approach modifies the grid in-place, so it doesn't require an additional `visited` array.
**Pros:** More efficient in practice as it avoids a separate `visited` array.; The logic is cleaner, separating the problem into two distinct, simpler subproblems: eliminating non-closed islands and then counting the remaining ones.; Modifying the input grid is a common and accepted technique for this class of problems.
**Cons:** Modifies the input grid, which might not be permissible in all contexts. If the original grid must be preserved, a copy would be needed, increasing space complexity.
### Explanation
The problem is simplified by first removing all islands that are guaranteed *not* to be closed. An island is not closed if any of its land cells touch the grid's border.

**Pass 1: Sink non-closed islands.**
We iterate along the four borders of the grid (top row, bottom row, left column, right column). Whenever we find a land cell (`grid[i][j] == 0`) on a border, we know it's part of a non-closed island. We start a DFS from this cell. The purpose of this DFS is to find all connected land cells and change their value from `0` to `1`. This effectively "sinks" the entire island, removing it from consideration. We can modify the grid in-place.

**Pass 2: Count remaining islands.**
After the first pass, the grid has been modified. All `0`s connected to the border are now `1`s. Any `0` that still exists in the grid must be part of an island completely surrounded by `1`s, i.e., a closed island. We now perform a standard "count islands" algorithm on the modified grid. We iterate through every cell `(i, j)`. If we find a `grid[i][j] == 0`, we've found a new closed island. We increment our counter. To avoid counting the same island again, we immediately "sink" this newly found island by starting another DFS from `(i, j)` to change all its connected `0`s to `1`s.

This two-pass approach neatly separates the logic of identifying and counting closed islands.

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

        // Pass 1: Sink all land cells connected to the border.
        // These are part of non-closed islands.
        for (int i = 0; i < rows; i++) {
            // Left border
            if (grid[i][0] == 0) {
                dfs(i, 0, grid);
            }
            // Right border
            if (grid[i][cols - 1] == 0) {
                dfs(i, cols - 1, grid);
            }
        }
        for (int j = 0; j < cols; j++) {
            // Top border
            if (grid[0][j] == 0) {
                dfs(0, j, grid);
            }
            // Bottom border
            if (grid[rows - 1][j] == 0) {
                dfs(rows - 1, j, grid);
            }
        }

        // Pass 2: Count the remaining islands.
        // Any '0' left is part of a closed island.
        int closedIslandCount = 0;
        for (int i = 1; i < rows - 1; i++) {
            for (int j = 1; j < cols - 1; j++) {
                if (grid[i][j] == 0) {
                    closedIslandCount++;
                    dfs(i, j, grid); // Sink this island to not recount it
                }
            }
        }

        return closedIslandCount;
    }

    private void dfs(int r, int c, int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 1) {
            return;
        }

        // Sink the land cell
        grid[r][c] = 1;

        // Explore neighbors
        dfs(r + 1, c, grid);
        dfs(r - 1, c, grid);
        dfs(r, c + 1, grid);
        dfs(r, c - 1, grid);
    }
}
```
### Algorithm
- Get grid dimensions `rows` and `cols`.
- **First Pass:**
    - Iterate through the cells on the top and bottom borders (`i=0`, `i=rows-1`). If a cell is land (`0`), start a traversal (DFS/BFS) to find all connected land cells and change them to water (`1`).
    - Iterate through the cells on the left and right borders (`j=0`, `j=cols-1`). If a cell is land (`0`), do the same traversal and sinking process.
- **Second Pass:**
    - Initialize `count = 0`.
    - Iterate through the *inner* cells of the grid (from `(1,1)` to `(rows-2, cols-2)`).
    - If a cell `(i, j)` is land (`0`):
        - Increment `count`.
        - Start a traversal from `(i, j)` to sink this entire island (change all its `0`s to `1`s) to prevent recounting.
- Return `count`.

# Solutions
### CSharp

```csharp
public class Solution {
    private int m;
    private int n;
    private int[][] grid;
    public int ClosedIsland(int[][] grid) {
        m = grid.Length;
        n = grid[0].Length;
        this.grid = grid;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    ans += dfs(i, j);
                }
            }
        }
        return ans;
    }
    private int dfs(int i, int j) {
        int res = i > 0 && i < m - 1 && j > 0 && j < n - 1 ? 1 : 0;
        grid[i][j] = 1;
        int[] dirs = {
            -1,
            0,
            1,
            0,
            -1
        };
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) {
                res &= dfs(x, y);
            }
        }
        return res;
    }
}
```

### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] grid;
public
  int closedIsland(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 0) {
          ans += dfs(i, j);
        }
      }
    }
    return ans;
  }
private
  int dfs(int i, int j) {
    int res = i > 0 && i < m - 1 && j > 0 && j < n - 1 ? 1 : 0;
    grid[i][j] = 1;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) {
        res &= dfs(x, y);
      }
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int closedIsland(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int ans = 0;
    int dirs[5] = {-1, 0, 1, 0, -1};
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      int res = i > 0 && i < m - 1 && j > 0 && j < n - 1 ? 1 : 0;
      grid[i][j] = 1;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) {
          res &= dfs(x, y);
        }
      }
      return res;
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans += grid[i][j] == 0 && dfs(i, j);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int: def dfs(i: int, j: int) -> int: res = int(0 < i < m - 1 and 0 < j < n - 1) grid[i][j] = 1 for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y] == 0: res &= dfs(x, y) return res m, n = len(grid), len(grid[0]) dirs = (- 1, 0, 1, 0, - 1) return sum(grid[i][j] == 0 and dfs(i, j) for i in range(m) for j in range(n))

```