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.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search, Union Find
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 12grid[i][j] is 0 or 1.
Hints for Number of Enclaves
Hint 1
Instead of testing each cell, flood the land that touches the border.
Hint 2
Start a DFS or BFS from every land cell on the four edges and mark everything it reaches.
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
- Push every border land cell and mark it.
- DFS/BFS through four-directional land neighbours.
- 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)