Number of Enclaves | Leetcode 1020 | Explained using BFS

Learn how to count the number of land cells in a grid that cannot reach the border by water. This step-by-step guide uses a multi-source BFS approach with clear, plain-English explanations and in-place code comments.

What the Problem Asks

You are given an m x n binary grid grid where 0 represents water and 1 represents land.
A move consists of walking from one land cell to another adjacent (4-directional) land cell.
A land cell is called an enclave if it cannot reach the boundary of the grid by any number of moves.
Return the number of land cells in all enclaves.

Intuition & Approach

1. Why BFS from the Border?
   Any land (1) that can reach the boundary is not an enclave. If we start BFS from all boundary land cells, we can mark every land cell that’s connected to the edge.
2. What’s Left Over?
   After that BFS, any land cell not visited must be unable to reach the border, that’s exactly the count we want.
3. High-Level Steps:
   • Create a visited grid, same size as grid, initialized to 0 (unvisited).
   • Enqueue every land cell on the four borders and mark them visited.
   • Run BFS: for each cell popped, enqueue its unvisited land neighbors and mark them.
   • Finally, scan the entire grid: every land cell that is still unvisited is an enclave, increment a counter.

Code Implementation (with Comments)

from collections import deque

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        # visited[r][c] == 1 means we've seen this land cell in BFS
        visited = [[0 for _ in range(cols)] for _ in range(rows)]
        queue = deque()

        # 1. Enqueue all land cells on the border
        for r in range(rows):
            for c in range(cols):
                # Is this cell on the outer border?
                if r == 0 or c == 0 or r == rows - 1 or c == cols - 1:
                    # If it's land, mark visited and enqueue
                    if grid[r][c] == 1:
                        queue.append((r, c))
                        visited[r][c] = 1

        # 2. BFS to mark all land cells reachable from the border
        while len(queue) != 0:
            i, j = queue.popleft()
            # Explore up, left, down, right
            for x, y in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                new_i, new_j = i + x, j + y
                # Skip out-of-bounds
                if new_i < 0 or new_i >= rows or new_j < 0 or new_j >= cols:
                    continue
                # Skip water
                if grid[new_i][new_j] == 0:
                    continue
                # Skip already visited land
                if visited[new_i][new_j] == 1:
                    continue
                # Mark and enqueue this land cell
                queue.append((new_i, new_j))
                visited[new_i][new_j] = 1

        # 3. Count all land cells that were never visited
        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1 and visited[r][c] == 0:
                    count += 1

        return count

Detailed Explanation

1. Setup
   • We read the grid size into rows and cols.
   • We build a visited matrix initialized to 0 for every cell.
   • We make an empty queue for our BFS.
2. Border Enqueue
   • We loop over every cell in the first row, last row, first column, and last column.
   • Whenever we see a land cell (grid[r][c] == 1), we mark visited[r][c] = 1 and add (r, c) to the queue.
   • This seeds our BFS with all border land cells at distance 0 from the edge.
3. Multi-Source BFS
   • While the queue isn’t empty, we pop (i, j).
   • We look at its four neighbors: up, left, down, right.
     • If the neighbor is out of bounds, skip it.
     • If it’s water (0), skip it.
     • If it’s already visited, skip it.
     • Otherwise, it’s unvisited land: we mark it visited and enqueue it.
   • This process floods inward from the border, marking every land cell that can reach the edge.
4. Counting Enclaves
   • After BFS, any land cell with visited[r][c] == 0 was never reached by our border-based flood.
   • We loop over all cells once more and count those unvisited land cells.

Time and Space Complexity

• Time Complexity: O(m·n) — we visit each cell at most twice (once to enqueue, once to process).
• Space Complexity: O(m·n) — for the visited matrix and the BFS queue in the worst case.

Conclusion

By starting BFS from all border land cells at once, we efficiently mark every land cell that can “escape” to the boundary. The rest are true enclaves and get counted. This multi-source BFS runs in linear time and uses only O(m·n) extra space, perfect for grids up to a few hundred in each dimension. Happy coding!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.