⚡Flashcard Drill➔
NeetCode #590LC-1254MediumGraphs
← Back to All Problems

#590 · #1254 · Number of Closed Islands(统计封闭岛屿的数目)

📌 Problem Statement & Constraints

Given an m x n binary matrix grid, return the number of closed islands: maximal 4-directionally connected groups of 0s completely surrounded by 1s. Constraints: 1 <= m, n <= 100.

💡 Core Algorithmic Approaches

  1. An island of 0s is closed unless it touches the grid border.
  2. Flood-fill each 0 component; the DFS returns whether the component stayed inside the grid.
  3. The border check is not (0 <= r < m and 0 <= c < n), which returns False (not closed).
  4. All four recursive calls must run so the whole component is consumed.

💻 Benchmark Python3 Implementation

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

        def dfs(r: int, c: int) -> bool:
            if not (0 <= r < m and 0 <= c < n):
                return False               # reached outside -> not closed
            if grid[r][c] != 0:
                return True
            grid[r][c] = 1                 # mark visited
            closed = True
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                if not dfs(r + dr, c + dc):
                    closed = False         # still explore the rest
            return closed

        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and dfs(i, j):
                    count += 1
        return count

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell is visited once.
💾 Space Complexity
O(m * n) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Short-circuiting with and: the component would not be fully marked, and part of it could be counted again.
  • Returning True for out-of-bounds: that would treat a border-touching island as closed.
  • Only checking the starting cell's border status: any cell of the component touching the border disqualifies it.
  • Marking visited only when the component is closed: marking must happen regardless.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems