Number of Closed Islands

Medium
295.

Number of Closed Islands

Number of Closed Islands is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Uber interviews.

You are given a 2-D grid where 0 is land and 1 is water. An island is a maximal group of 0s connected horizontally or vertically.

An island is closed if it is completely surrounded by water — that is, none of its cells lies on the border of the grid. Return the number of closed islands.

Example 1

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

Example 2

Input
grid = [[0,0,1],[1,1,1],[1,1,1]]
Output
0
Explanation
The only island touches the border.

Example 3

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

Constraints

  • 1 <= grid.length, grid[i].length <= 8
  • grid[i][j] is 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var closedIsland = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Closed Islands — Solution in Python, Java & C++

Number of Closed Islands solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Closed Islands is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Uber interviews.

Problem statement

You are given a 2-D grid where 0 is land and 1 is water. An island is a maximal group of 0s connected horizontally or vertically.

An island is closed if it is completely surrounded by water — that is, none of its cells lies on the border of the grid. Return the number of closed islands.

Example 1

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

Example 2

Input: grid = [[0,0,1],[1,1,1],[1,1,1]]
Output: 0
Explanation: The only island touches the border.

Example 3

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

Constraints

  • 1 <= grid.length, grid[i].length <= 8
  • grid[i][j] is 0 or 1.

Hints for Number of Closed Islands

  1. Hint 1

    Flood-fill each unvisited land cell to collect its whole island.

  2. Hint 2

    While filling, note whether any cell of the island sits on row 0, row m-1, column 0 or column n-1.

  3. Hint 3

    Count the island only if no such cell was found.

How to solve Number of Closed Islands

Flood-fill each unvisited land cell to collect its island, noting whether any cell lies on the border; count the island only if none does.

Approach

  1. For each unvisited 0, start a DFS/BFS marking cells seen.
  2. During the fill, set closed = false if a cell is on row 0, row m-1, column 0 or column n-1.
  3. After the fill, count the island if closed is still true.

Why it works

An island is closed exactly when it has no border cell, and the fill visits every cell of the island, so the flag is decided correctly.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Do not abort the fill on a border cell — the rest of that island must still be marked seen, or it will be recounted.
  • Here 0 is land and 1 is water, the reverse of the usual convention.

Reference solution

Python

def closedIsland(grid) -> int:
    m, n = len(grid), len(grid[0])
    seen = [[False] * n for _ in range(m)]
    count = 0
    for sr in range(m):
        for sc in range(n):
            if grid[sr][sc] != 0 or seen[sr][sc]:
                continue
            stack = [(sr, sc)]
            seen[sr][sc] = True
            closed = True
            while stack:
                r, c = stack.pop()
                if r == 0 or r == m - 1 or c == 0 or c == n - 1:
                    closed = False
                for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0 and not seen[nr][nc]:
                        seen[nr][nc] = True
                        stack.append((nr, nc))
            if closed:
                count += 1
    return count

Java

public static int closedIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    boolean[][] seen = new boolean[m][n];
    int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int count = 0;
    for (int sr = 0; sr < m; sr++) {
        for (int sc = 0; sc < n; sc++) {
            if (grid[sr][sc] != 0 || seen[sr][sc]) continue;
            Deque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[]{sr, sc});
            seen[sr][sc] = true;
            boolean closed = true;
            while (!stack.isEmpty()) {
                int[] cell = stack.pop();
                int r = cell[0], c = cell[1];
                if (r == 0 || r == m - 1 || c == 0 || c == n - 1) closed = false;
                for (int[] d : steps) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !seen[nr][nc]) {
                        seen[nr][nc] = true;
                        stack.push(new int[]{nr, nc});
                    }
                }
            }
            if (closed) count++;
        }
    }
    return count;
}

C++

int closedIsland(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<vector<bool>> seen(m, vector<bool>(n, false));
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    int count = 0;
    for (int sr = 0; sr < m; sr++) {
        for (int sc = 0; sc < n; sc++) {
            if (grid[sr][sc] != 0 || seen[sr][sc]) continue;
            vector<pair<int, int>> stack;
            stack.push_back(make_pair(sr, sc));
            seen[sr][sc] = true;
            bool closed = true;
            while (!stack.empty()) {
                pair<int, int> cell = stack.back();
                stack.pop_back();
                int r = cell.first, c = cell.second;
                if (r == 0 || r == m - 1 || c == 0 || c == n - 1) closed = false;
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !seen[nr][nc]) {
                        seen[nr][nc] = true;
                        stack.push_back(make_pair(nr, nc));
                    }
                }
            }
            if (closed) count++;
        }
    }
    return count;
}

JavaScript

var closedIsland = function(grid) {
    const m = grid.length, n = grid[0].length;
    const seen = [];
    for (let r = 0; r < m; r++) seen.push(new Array(n).fill(false));
    let count = 0;
    for (let sr = 0; sr < m; sr++) {
        for (let sc = 0; sc < n; sc++) {
            if (grid[sr][sc] !== 0 || seen[sr][sc]) continue;
            const stack = [[sr, sc]];
            seen[sr][sc] = true;
            let closed = true;
            while (stack.length > 0) {
                const cell = stack.pop();
                const r = cell[0], c = cell[1];
                if (r === 0 || r === m - 1 || c === 0 || c === n - 1) closed = false;
                const steps = [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]];
                for (let s = 0; s < 4; s++) {
                    const nr = steps[s][0], nc = steps[s][1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === 0 && !seen[nr][nc]) {
                        seen[nr][nc] = true;
                        stack.push([nr, nc]);
                    }
                }
            }
            if (closed) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)