Number of Enclaves

Medium
449.

Number of Enclaves

Number of Enclaves is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon and Google interviews.

You are given a binary matrix grid where 0 is sea and 1 is land. A move takes you to an adjacent land cell (up, down, left or right) or off the edge of the grid.

Return the number of land cells from which you cannot walk off the boundary.

Example 1

Input
grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output
3

Example 2

Input
grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output
0

Example 3

Input
grid = [[1]]
Output
0

Constraints

  • 1 <= grid.length, grid[i].length <= 12
  • grid[i][j] is 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var numEnclaves = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Enclaves — Solution in Python, Java & C++

Number of Enclaves solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Enclaves is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon and Google interviews.

Problem statement

You are given a binary matrix grid where 0 is sea and 1 is land. A move takes you to an adjacent land cell (up, down, left or right) or off the edge of the grid.

Return the number of land cells from which you cannot walk off the boundary.

Example 1

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3

Example 2

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0

Example 3

Input: grid = [[1]]
Output: 0

Constraints

  • 1 <= grid.length, grid[i].length <= 12
  • grid[i][j] is 0 or 1.

Hints for Number of Enclaves

  1. Hint 1

    Instead of testing each cell, flood the land that touches the border.

  2. Hint 2

    Start a DFS or BFS from every land cell on the four edges and mark everything it reaches.

  3. Hint 3

    The answer is the number of land cells that stayed unmarked.

How to solve Number of Enclaves

Flood-fill the land connected to the border; every land cell that stays unmarked cannot escape.

Approach

  1. Push every border land cell and mark it.
  2. DFS/BFS through four-directional land neighbours.
  3. Count land cells not marked.

Why it works

A cell can walk off the grid iff it is connected to a border land cell, which is exactly what the flood from the border computes.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Same inversion trick as Surrounded Regions — find the escapers, not the trapped.

Reference solution

Python

def numEnclaves(grid) -> int:
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    stack = []
    for r in range(rows):
        for c in range(cols):
            on_border = r == 0 or c == 0 or r == rows - 1 or c == cols - 1
            if on_border and grid[r][c] == 1 and not seen[r][c]:
                seen[r][c] = True
                stack.append((r, c))
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and not seen[nr][nc]:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return sum(1 for r in range(rows) for c in range(cols) if grid[r][c] == 1 and not seen[r][c])

Java

public static int numEnclaves(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    boolean[][] seen = new boolean[rows][cols];
    Deque<int[]> stack = new ArrayDeque<>();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            boolean onBorder = r == 0 || c == 0 || r == rows - 1 || c == cols - 1;
            if (onBorder && grid[r][c] == 1 && !seen[r][c]) {
                seen[r][c] = true;
                stack.push(new int[]{r, c});
            }
        }
    }
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    while (!stack.isEmpty()) {
        int[] cell = stack.pop();
        for (int d = 0; d < 4; d++) {
            int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
            if (grid[nr][nc] == 1 && !seen[nr][nc]) {
                seen[nr][nc] = true;
                stack.push(new int[]{nr, nc});
            }
        }
    }
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1 && !seen[r][c]) count++;
        }
    }
    return count;
}

C++

int numEnclaves(vector<vector<int>>& grid) {
    int rows = (int) grid.size(), cols = (int) grid[0].size();
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    vector<pair<int,int>> stack;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            bool onBorder = r == 0 || c == 0 || r == rows - 1 || c == cols - 1;
            if (onBorder && grid[r][c] == 1 && !seen[r][c]) {
                seen[r][c] = true;
                stack.push_back(make_pair(r, c));
            }
        }
    }
    int dr[4] = {1, -1, 0, 0};
    int dc[4] = {0, 0, 1, -1};
    while (!stack.empty()) {
        pair<int,int> cell = stack.back();
        stack.pop_back();
        for (int d = 0; d < 4; d++) {
            int nr = cell.first + dr[d], nc = cell.second + dc[d];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
            if (grid[nr][nc] == 1 && !seen[nr][nc]) {
                seen[nr][nc] = true;
                stack.push_back(make_pair(nr, nc));
            }
        }
    }
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1 && !seen[r][c]) count++;
        }
    }
    return count;
}

JavaScript

var numEnclaves = function(grid) {
    const rows = grid.length, cols = grid[0].length;
    const seen = [];
    for (let r = 0; r < rows; r++) {
        const row = [];
        for (let c = 0; c < cols; c++) row.push(false);
        seen.push(row);
    }
    const stack = [];
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            const onBorder = r === 0 || c === 0 || r === rows - 1 || c === cols - 1;
            if (onBorder && grid[r][c] === 1 && !seen[r][c]) {
                seen[r][c] = true;
                stack.push([r, c]);
            }
        }
    }
    const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    while (stack.length > 0) {
        const cell = stack.pop();
        for (let d = 0; d < 4; d++) {
            const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
            if (grid[nr][nc] === 1 && !seen[nr][nc]) {
                seen[nr][nc] = true;
                stack.push([nr, nc]);
            }
        }
    }
    let count = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 1 && !seen[r][c]) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)