Number of Closed Islands

Share

Given a 2D grid where 0=land and 1=water, return the number of closed islands. A closed island is surrounded by water on all four sides.

Example 1
Input: [[1,1,1,1,1],[1,0,1,0,1],[1,1,1,1,1]] → Output: 2
Example 2
Input: [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] → Output: 1

Solution Approach

First, DFS from boundary to eliminate land connected to boundary. Then count remaining land components (closed islands).

  • DFS from all 0-cells on boundary, mark them as 1 (or visited).
  • Then iterate entire grid: if 0 found, DFS to mark whole island, count++.
  • Return count.
Java
class Solution {
    int m, n;
    public int closedIsland(int[][] grid) {
        m = grid.length; n = grid[0].length;
        // Eliminate boundary-connected land
        for (int i = 0; i < m; i++) { dfs(grid,i,0); dfs(grid,i,n-1); }
        for (int j = 0; j < n; j++) { dfs(grid,0,j); dfs(grid,m-1,j); }
        int count = 0;
        for (int i = 1; i < m-1; i++)
            for (int j = 1; j < n-1; j++)
                if (grid[i][j] == 0) { dfs(grid,i,j); count++; }
        return count;
    }
    private void dfs(int[][] grid, int r, int c) {
        if (r<0||r>=m||c<0||c>=n||grid[r][c]!=0) return;
        grid[r][c] = 1;
        dfs(grid,r+1,c); dfs(grid,r-1,c); dfs(grid,r,c+1); dfs(grid,r,c-1);
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(M*N)