Number of Closed Islands

LeetCode 1380 | Difficulty: Medium

Medium

Problem Description

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

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

Example 3:

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

Constraints:

- `1 <= grid.length, grid[0].length <= 100`

- `0 <= grid[i][j] <=1`

Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Union-Find

Maintain disjoint sets with two operations: find (which set does element belong to?) and union (merge two sets). Use path compression and union by rank for near O(1) amortized operations.

When to use

Connected components, cycle detection in undirected graphs, grouping elements.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 108 ms)

Metric	Value
Runtime	108 ms
Memory	27.1 MB
Date	2020-11-02

Solution

public class Solution {
    public int ClosedIsland(int[][] grid) {
       int m = grid.Length;
    int n = grid[0].Length;
    bool[,] visited = new bool[m, n];
    int count = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 0 && !visited[i, j])
            {
                bool isCorner = false;
                ClosedDfs(grid, visited, i, j, ref isCorner);
                if(isCorner) continue;
                count++;
            }
        }
    }

    return count;

}

public void ClosedDfs(int[][] grid, bool[,] visited, int i, int j, ref bool isCorner)
{
    if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length || visited[i, j] || grid[i][j] == 1)
        return;
    

    isCorner = isCorner || (i == 0 || i == grid.Length - 1 || j == grid[0].Length - 1 || j == 0);
    visited[i, j] = true;

    ClosedDfs(grid, visited, i - 1, j, ref isCorner);
    ClosedDfs(grid, visited, i + 1, j, ref isCorner);
    ClosedDfs(grid, visited, i, j - 1, ref isCorner);
    ClosedDfs(grid, visited, i, j + 1, ref isCorner);
}
}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$
Union-Find	$O(n × α(n))$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Exclude connected group of 0s on the corners because they are not closed island.

Hint 2: Return number of connected component of 0s on the grid.