Number of Closed Islands

Problem

You are given a 2D grid of 0s (land) and 1s (water). An island is a maximal group of 0s connected 4-directionally. An island is closed if every one of its land cells is fully surrounded by water — that is, the island does not touch any edge of the grid. Return the number of closed islands.

Constraints

• 1 ≤ grid.length, grid[i].length ≤ 100
• grid[i][j] is 0 or 1

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def closedIsland(self, grid):
        m, n = len(grid), len(grid[0])
        def dfs(r, c):
            if r < 0 or c < 0 or r >= m or c >= n:
                return False
            if grid[r][c] == 1:
                return True
            grid[r][c] = 1
            d = dfs(r+1, c) & dfs(r-1, c) & dfs(r, c+1) & dfs(r, c-1)
            return d
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and dfs(i, j):
                    count += 1
        return count

Java

class Solution {
    public int closedIsland(int[][] grid) {
        int count = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 0 && dfs(grid, r, c)) {
                    count++;
                }
            }
        }
        return count;
    }

    // Returns true only if this land component never reaches the border.
    private boolean dfs(int[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) {
            return false;
        }
        if (grid[r][c] == 1) {
            return true;
        }
        grid[r][c] = 1; // mark visited by flooding to water
        boolean up    = dfs(grid, r - 1, c);
        boolean down  = dfs(grid, r + 1, c);
        boolean left  = dfs(grid, r, c - 1);
        boolean right = dfs(grid, r, c + 1);
        return up && down && left && right;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.