Closed Islands
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Union Find · Matrix
Problem
You are given a 2D grid in which 0 is land and 1 is water. An island is a maximal group of land cells connected horizontally or vertically.
A closed island is an island that is completely surrounded by water on all four sides, which means none of its cells lies on the border of the grid.
Return the number of closed islands.
Examples
Input: grid = [[1,1,1,1,1],[1,0,0,1,1],[1,1,1,0,1],[1,0,1,1,0]] Output: 2
The islands at (1,1)-(1,2) and at (2,3) are enclosed; the islands at (3,1) and (3,4) touch the border.
Input: grid = [[0,0],[0,0]] Output: 0
The only island touches the border.
Input: grid = [[1,1,1],[1,0,1],[1,1,1]] Output: 1
The middle cell is land surrounded by water: one closed island.
Constraints
- 1 <= len(grid), len(grid[0]) <= 100
- Each grid[i][j] is 0 or 1.
Approaches
- Spread border reach by repeated sweeps — time O((m · n)²), space O(m · n)
Follow-up
A single pass also works: flood each island and record whether any of its cells is on the border; count it only if none was. Be careful to finish flooding the island even after you find a border cell, or its leftover cells start a new island.
Related problems
Start free on Cariara · Coding problems · System design studio
