Number of Closed Islands

Medium Graphs Matrix Graphs Original on LeetCode

Reported atZeptoAirtel

Number of Closed Islands is a medium graphs problem solved with the matrix graphs pattern. The best approach, optimal (sink border land, then count), runs in O(m · n) time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs per island with a border flag up.

Problem

You are given an m x n grid where 0 means land and 1 means water. An island is a group of land cells connected horizontally or vertically.

An island is closed if it does not touch the outer border of the grid, i.e. it is completely surrounded by water on its left, right, top and bottom. Return the number of closed islands.

Examples

Example 1

Input
grid = [[1,1,1,1,1],[1,0,0,1,1],[1,0,1,0,1],[1,1,1,1,1]]
Output
2
Why
Land {(1,1), (1,2), (2,1)} and the single cell (2,3) are both surrounded by water on every side.

Example 2

Input
grid = [[1,1,1,1],[1,0,1,0],[1,1,1,1]]
Output
1
Why
Cell (1,1) is closed, but cell (1,3) lies on the right border, so it is not.

Example 3

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

Constraints

  • 1 <= grid.length, grid[0].length <= 100
  • grid[i][j] is 0 (land) or 1 (water)

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
DFS per island with a border flagO(m · n)O(m · n)
Optimal (sink border land, then count)O(m · n)O(m · n)

1DFS per island with a border flag

TimeO(m · n)Every cell is visited once.
SpaceO(m · n)The recursion can be as deep as the largest island, up to m · n cells.

Visit every unvisited land cell with a recursive DFS that marks the whole island. The DFS reports whether any of the island's cells is on the border. Count the islands for which it never touched the border. The DFS must explore the entire island even after it finds a border cell, so that no part of it is counted later.

  1. For every land cell not yet visited, run dfs(r, c).
  2. dfs marks the cell, returns false if the cell is on the border, and combines the results of all four neighbours with a non-short-circuiting AND.
  3. If dfs returns true, increment the count.
  4. Return the count.
class Solution {
    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, count = 0;
        boolean[][] seen = new boolean[m][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0 && !seen[r][c] && dfs(grid, seen, r, c)) count++;
            }
        }
        return count;
    }

    private boolean dfs(int[][] grid, boolean[][] seen, int r, int c) {
        int m = grid.length, n = grid[0].length;
        if (r < 0 || c < 0 || r >= m || c >= n) return false;
        if (grid[r][c] == 1 || seen[r][c]) return true;
        seen[r][c] = true;
        boolean closed = r > 0 && c > 0 && r < m - 1 && c < n - 1;
        closed &= dfs(grid, seen, r + 1, c);
        closed &= dfs(grid, seen, r - 1, c);
        closed &= dfs(grid, seen, r, c + 1);
        closed &= dfs(grid, seen, r, c - 1);
        return closed;
    }
}

2Optimal (sink border land, then count)

TimeO(m · n)Each cell is turned into water at most once.
SpaceO(m · n)The BFS queue can hold O(m · n) cells in the worst case; the grid itself is reused as the visited marker.

First flood every island that touches the border, turning its cells into water, since none of them can be closed. After that, every remaining island is closed, so simply count the islands with one more flood fill each. Using an explicit BFS queue keeps the memory bounded even for a huge snake-shaped island.

  1. For every land cell on the border, flood its island into water with BFS.
  2. Scan the inner cells; for each remaining land cell, increment the count and flood its island.
  3. Return the count.
class Solution {
    private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                boolean border = r == 0 || c == 0 || r == m - 1 || c == n - 1;
                if (border && grid[r][c] == 0) sink(grid, r, c);
            }
        }
        int count = 0;
        for (int r = 1; r < m - 1; r++) {
            for (int c = 1; c < n - 1; c++) {
                if (grid[r][c] == 0) {
                    count++;
                    sink(grid, r, c);
                }
            }
        }
        return count;
    }

    private void sink(int[][] grid, int sr, int sc) {
        int m = grid.length, n = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        grid[sr][sc] = 1;
        queue.add(new int[] { sr, sc });
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : DIRS) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r >= 0 && c >= 0 && r < m && c < n && grid[r][c] == 0) {
                    grid[r][c] = 1;
                    queue.add(new int[] { r, c });
                }
            }
        }
    }
}

Edge cases to test

  • A grid with only one row or one column (nothing can be closed)
  • All water or all land
  • An island that reaches the border through a long thin path
  • Islands nested inside a ring of water that sits inside a bigger island

Hints

Hint 1

Note the encoding: here 0 is land and 1 is water.

Hint 2

An island is closed exactly when none of its cells is on the outer border of the grid.

Hint 3

Remove (flood) every island that touches the border first; every island that is left is closed.

FAQ

What is the best time complexity for Number of Closed Islands?

Optimal (sink border land, then count) runs in O(m · n) time and O(m · n) extra space. Each cell is turned into water at most once.

Which pattern does Number of Closed Islands use?

It is a graphs problem that uses the matrix graphs pattern. Other problems with the same pattern: Flood Fill, Maximum Number of Points From Grid Queries, Contain Virus.

Is there a brute force solution for Number of Closed Islands?

Yes. DFS per island with a border flag takes O(m · n) time and O(m · n) space. Visit every unvisited land cell with a recursive DFS that marks the whole island.

Which edge cases should I test for Number of Closed Islands?

A grid with only one row or one column (nothing can be closed); All water or all land; An island that reaches the border through a long thin path; Islands nested inside a ring of water that sits inside a bigger island.