1254. Number of Closed Islands

Problem¶

Given a binary grid where 0 is land and 1 is water, count the 4-directionally connected land components that do not touch the grid boundary.

0 = land, 1 = water
grid = [[0,1,1],
        [1,0,1],
        [1,1,1]]
output = 1  # The center island is closed; the boundary land is not.

Key trick¶

Flood-fill all land connected to the boundary first; every remaining land component must be a closed island.

Trap¶

Land is represented by 0, contrary to many island problems.
Diagonal cells are not connected.
Mark cells when adding them to the stack, not when removing them.
This approach mutates the input grid.

Why is it interesting?¶

It turns a global condition, being surrounded by water, into a standard connected-component count by first eliminating every component that touches the boundary.

Python solution¶

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

        def flood(r, c):
            if grid[r][c] != 0:
                return

            stack = [(r, c)]
            grid[r][c] = 1

            while stack:
                r, c = stack.pop()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        stack.append((nr, nc))

        # Remove every island connected to the boundary.
        for r in range(m):
            flood(r, 0)
            flood(r, n - 1)

        for c in range(n):
            flood(0, c)
            flood(m - 1, c)

        # Each remaining component is closed.
        ans = 0

        for r in range(1, m - 1):
            for c in range(1, n - 1):
                if grid[r][c] == 0:
                    ans += 1
                    flood(r, c)

        return ans

Time complexity: \(O(mn)\).

Space complexity: \(O(mn)\) in the worst case for the explicit stack.

Comment on my solution¶

Your solution is correct and interview-ready:

It identifies the right reduction: remove boundary-connected land, then count what remains.
It uses an iterative flood fill, avoiding recursion-depth failures.
It marks cells before pushing them, preventing duplicate work.
Its time and space complexities are optimal for this approach.

Minor improvements:

Add spaces after commas for idiomatic formatting.
Name the result ans or closed rather than islands to clarify that only closed islands are counted.
Scan only interior cells during the counting phase, since all boundary cells have already been eliminated.

# Ideas:
# - weird because land is often represented by 1s not 0s.
# - Similar problem as surrounded island and number of island problem
# - multi source BFS from the edges to flood fill island touching the
#   edges
# - then BFS on other island to count component (islands)

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def flood(r,c):
            if grid[r][c] != 0:
                return
            stack = [(r,c)]
            grid[r][c] = 1

            while stack:
                r, c = stack.pop()
                for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        stack.append((nr,nc))

        for r in range(m):
            flood(r, 0)
            flood(r, n - 1)
        for c in range(n):
            flood(0, c)
            flood(m - 1, c)

        islands = 0

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 0:
                    islands += 1
                    flood(r,c)
        return islands