We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Enclaves

Number: 1073

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg

Problem Description

Given a binary matrix where 0 represents sea and 1 represents land, determine the number of land cells from which it is impossible to walk off the grid boundary. A move consists of moving 4-directionally from one land cell to another. Essentially, count the enclave cells that are completely surrounded by sea.

Key Insights

  • Any land cell that is connected to the boundary can reach the edge and should not be counted.
  • Use DFS/BFS to traverse and mark all land cells connected to the boundary as water.
  • Once the boundary-connected cells are removed, count the remaining land cells in the grid.

Space and Time Complexity

Time Complexity: O(m * n) - Each cell is processed at most once. Space Complexity: O(m * n) - In worst-case scenarios (e.g., deep recursion in DFS), the auxiliary space used can be proportional to the number of cells.

Solution

The approach involves a two-step process:

  1. Traverse the boundaries of the grid and perform a DFS/BFS from each boundary cell that is a land cell. During traversal, mark all reachable land cells (i.e., cells that can potentially reach the boundary) as sea.
  2. After processing the boundaries, count all remaining land cells in the grid. These are the enclaves that cannot reach the boundary.

Key data structures include the grid itself and, depending on the implementation, either a recursion stack (DFS) or an explicit queue (BFS) for traversal. The main trick is to remove (or mark) all boundary-connected land cells before counting, effectively isolating the enclaves.

Code Solutions

Below are solutions in multiple languages with line-by-line comments.

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        # Calculate number of rows and columns
        m, n = len(grid), len(grid[0])
        
        # Helper function using DFS to mark connected land as sea.
        def dfs(r, c):
            # Base case: if out of bounds or already water, return
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
                return
            # Mark the current cell as water to avoid revisiting it
            grid[r][c] = 0
            # Explore all 4 directions (up, down, left, right)
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        
        # Remove boundary-connected land cells by traversing first and last columns for each row.
        for r in range(m):
            dfs(r, 0)
            dfs(r, n - 1)
        # Traverse first and last rows for each column.
        for c in range(n):
            dfs(0, c)
            dfs(m - 1, c)
        
        # Count remaining land cells that are enclaves.
        enclaveCount = sum(grid[r][c] for r in range(m) for c in range(n))
        return enclaveCount
← Back to All Questions