1254. Number of Closed Islands

HardView on LeetCode

Array Depth-First Search Breadth-First Search Union Find Matrix

Time: O(m * n)

Space: O(m * n)

Problem Overview

A closed island is a patch of land, the cells marked 0, that never touches the border of the grid.

Intuition

A closed island is a patch of land, the cells marked 0, that never touches the border of the grid. Water is marked 1. One land cell on the first row, the last row, the first column, or the last column opens the whole patch to the outside. A grid with fewer than three rows or fewer than three columns has no interior cell, so its answer is 0. Every land cell belongs to exactly one patch, so flooding each patch once is enough.

Algorithm

1Return 0 when the grid has fewer than 3 rows or fewer than 3 columns.
2Scan every cell. On unvisited land, flood that patch with an explicit stack and mark each cell as water.
3While flooding, remember whether any cell of the patch sits on the border.
4Count the patch only when every cell stayed in the interior.

Example Walkthrough

Input: three rows: 0 0 1 0 0 / 0 1 0 1 0 / 0 1 1 1 0

1.The land on the left, cells (0,0), (0,1), and (1,0), touches the border, so that patch is open.
2.The single 0 at row 1, column 2 is surrounded by water and never reaches an edge, so it is closed.
3.The land on the right touches the top and the bottom, so it is open too.

Output: 1

Common Pitfalls

•Land is 0 and water is 1. Marking a visited land cell as 1 keeps a later scan from starting the same patch again.
•A border cell makes the whole patch open. Finish the flood so the remaining cells are marked, then reject the patch.
•All four neighbors still need to be expanded after a border cell is found. Stopping early leaves unmarked land that a later start would count as another island.
•A recursive flood on a long snake of land can overflow the call stack. An explicit stack of packed row and column indices stays on the heap.

1254.cs

// Approach: A closed island is a 0-component that never touches the border.
// Flood each unvisited 0 with an explicit stack and mark it as visited. The
// component counts only when none of its cells lie on the first or last row
// or column. A grid thinner than 3 in either direction has no interior cell,
// so the answer is 0.
// Time: O(m * n) Space: O(m * n)

public class Solution
{
    public int ClosedIsland(int[][] grid)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        if (m < 3 || n < 3)
            return 0;

        int ans = 0;
        int[] stack = new int[m * n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 0 && Fill(grid, stack, i, j))
                    ans++;
        return ans;
    }

    private static bool Fill(int[][] grid, int[] stack, int si, int sj)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        bool closed = si > 0 && sj > 0 && si < m - 1 && sj < n - 1;
        int top = 0;
        stack[top++] = si * n + sj;
        grid[si][sj] = 1;

        while (top > 0)
        {
            int id = stack[--top];
            int r = id / n;
            int c = id - r * n;
            closed &= Push(grid, stack, ref top, r - 1, c, m, n);
            closed &= Push(grid, stack, ref top, r + 1, c, m, n);
            closed &= Push(grid, stack, ref top, r, c - 1, m, n);
            closed &= Push(grid, stack, ref top, r, c + 1, m, n);
        }
        return closed;
    }

    private static bool Push(int[][] grid, int[] stack, ref int top, int r, int c, int m, int n)
    {
        if (r < 0 || c < 0 || r == m || c == n || grid[r][c] == 1)
            return true;
        grid[r][c] = 1;
        stack[top++] = r * n + c;
        return r != 0 && c != 0 && r != m - 1 && c != n - 1;
    }
}

Was this solution helpful?