Number of Closed Islands

medium grid dfs flood fill

Problem

Given a 2D grid where 0 is land and 1 is water, an island is a maximal group of 0s connected horizontally or vertically. A closed island is one that is completely surrounded by water and does not touch the border of the grid. Return the number of closed islands.

Inputgrid = [[1,1,1,1],[1,0,0,1],[1,0,0,1],[1,1,1,1]]

Output1

The block of land in the middle never touches the border, so it counts as one closed island.

grid (rows separated by ';', cells by ',')

def closed_island(grid):
    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           # walked off the border
        if grid[r][c] == 1:
            return True            # water: nothing to flood
        grid[r][c] = 1             # sink this land cell
        a = dfs(r + 1, c); b = dfs(r - 1, c)
        d = dfs(r, c + 1); e = dfs(r, c - 1)
        return a and b and d and e

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

function closedIsland(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;
    const a = dfs(r + 1, c), b = dfs(r - 1, c);
    const d = dfs(r, c + 1), e = dfs(r, c - 1);
    return a && b && d && e;
  }

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

class Solution {
    int rows, cols;
    public int closedIsland(int[][] grid) {
        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 && dfs(grid, r, c)) count++;
        return count;
    }
    boolean dfs(int[][] grid, 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;
        boolean a = dfs(grid, r + 1, c), b = dfs(grid, r - 1, c);
        boolean d = dfs(grid, r, c + 1), e = dfs(grid, r, c - 1);
        return a && b && d && e;
    }
}

class Solution {
    int rows, cols;
    bool dfs(vector<vector<int>>& grid, 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 a = dfs(grid, r + 1, c), b = dfs(grid, r - 1, c);
        bool d = dfs(grid, r, c + 1), e = dfs(grid, r, c - 1);
        return a && b && d && e;
    }
public:
    int closedIsland(vector<vector<int>>& grid) {
        rows = grid.size(); cols = grid[0].size();
        int count = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == 0 && dfs(grid, r, c)) count++;
        return count;
    }
};

Explanation

An island is "closed" only if it is fully surrounded by water and never touches the edge of the grid. So as we explore each island we just need to detect whether it ever reaches the border — if it does, it's open; if it never does, it's closed.

We scan every cell, and whenever we find unvisited land (a 0) we run a flood-fill DFS. The DFS sinks each land cell it visits by setting grid[r][c] = 1, which doubles as a "visited" marker so we never count the same island twice.

The cleverness is in the return values. If the DFS ever steps off the grid it returns False (this island touched the border). Hitting water returns True (a clean wall). Each cell combines its four neighbors with AND — a and b and d and e — so the whole island reports True only if no branch ever fell off the edge. We count the island when the top-level call returns True.

Example: [[1,1,1,1],[1,0,0,1],[1,0,0,1],[1,1,1,1]]. The 2×2 block of land in the middle is ringed by water and never touches the border, so its DFS returns True and the count is 1.

Since each cell is visited once, the whole scan is linear in the grid size.

Time: O(rows × cols) Space: O(rows × cols)