Number of Enclaves

medium array dfs bfs matrix

Problem

Given a binary grid where 1 is land, return the number of land cells from which you cannot walk off the edge in 4 directions.

Inputgrid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Output3

DFS from every border 1 erasing reachable land; count remaining 1s.

grid (rows separated by ';')

def numEnclaves(grid):
    R, C = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != 1: return
        grid[r][c] = 0
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            dfs(r + dr, c + dc)
    for r in range(R):
        dfs(r, 0); dfs(r, C - 1)
    for c in range(C):
        dfs(0, c); dfs(R - 1, c)
    return sum(grid[r][c] for r in range(R) for c in range(C))

function numEnclaves(grid) {
  const R = grid.length, C = grid[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== 1) return;
    grid[r][c] = 0;
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  }
  for (let r = 0; r < R; r++) { dfs(r, 0); dfs(r, C - 1); }
  for (let c = 0; c < C; c++) { dfs(0, c); dfs(R - 1, c); }
  let count = 0;
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) count += grid[r][c];
  return count;
}

class Solution {
    int R, C; int[][] g;
    public int numEnclaves(int[][] grid) {
        g = grid; R = grid.length; C = grid[0].length;
        for (int r = 0; r < R; r++) { dfs(r, 0); dfs(r, C - 1); }
        for (int c = 0; c < C; c++) { dfs(0, c); dfs(R - 1, c); }
        int count = 0;
        for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) count += g[r][c];
        return count;
    }
    void dfs(int r, int c) {
        if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] != 1) return;
        g[r][c] = 0;
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
    }
}

int numEnclaves(vector<vector<int>>& grid) {
    int R = (int)grid.size(), C = (int)grid[0].size();
    function<void(int, int)> dfs = [&](int r, int c) {
        if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != 1) return;
        grid[r][c] = 0;
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
    };
    for (int r = 0; r < R; r++) { dfs(r, 0); dfs(r, C - 1); }
    for (int c = 0; c < C; c++) { dfs(0, c); dfs(R - 1, c); }
    int count = 0;
    for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) count += grid[r][c];
    return count;
}

Explanation

An "enclave" is land you can not escape from by walking to the grid's edge. Instead of testing each land cell separately, we flip the problem: first erase all land that can reach the border, and whatever land survives is trapped.

We launch a flood-fill DFS from every cell along the four borders. Each DFS turns connected land (1) into water (0), wiping out every island that touches the edge. The two loops dfs(r, 0); dfs(r, C-1) and dfs(0, c); dfs(R-1, c) cover the left/right columns and top/bottom rows.

After all border-connected land is erased, the only 1s left are the enclaves. So the answer is simply sum of all remaining cells, since land is 1 and water is 0.

Example: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]. The 1 at (1,0) sits on the border and gets erased, but the cluster at (1,2),(2,1),(2,2) never touches an edge, so 3 land cells remain — the answer is 3.

Each cell is touched at most a constant number of times, so the whole thing runs in time proportional to the grid size.

Time: O(R · C) Space: O(R · C)