Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.
A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.
Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.
Example 1:
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3 Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.
Example 2:
Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] Output: 0 Explanation: All 1s are either on the boundary or can reach the boundary.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid[i][j] is either 0 or 1.Problem summary: You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell. A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid. Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Union-Find
[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1020: Number of Enclaves
class Solution {
private int[][] grid;
public int numEnclaves(int[][] grid) {
this.grid = grid;
int m = grid.length, n = grid[0].length;
for (int j = 0; j < n; j++) {
for (int i : List.of(0, m - 1)) {
if (grid[i][j] == 1) {
dfs(i, j);
}
}
}
for (int i = 0; i < m; i++) {
for (int j : List.of(0, n - 1)) {
if (grid[i][j] == 1) {
dfs(i, j);
}
}
}
int ans = 0;
for (var row : grid) {
for (int x : row) {
ans += x;
}
}
return ans;
}
private void dfs(int i, int j) {
grid[i][j] = 0;
final int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; k++) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1) {
dfs(x, y);
}
}
}
}
// Accepted solution for LeetCode #1020: Number of Enclaves
func numEnclaves(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
dirs := [5]int{-1, 0, 1, 0, -1}
var dfs func(i, j int)
dfs = func(i, j int) {
grid[i][j] = 0
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
dfs(x, y)
}
}
}
for j := 0; j < n; j++ {
for _, i := range [2]int{0, m - 1} {
if grid[i][j] == 1 {
dfs(i, j)
}
}
}
for i := 0; i < m; i++ {
for _, j := range [2]int{0, n - 1} {
if grid[i][j] == 1 {
dfs(i, j)
}
}
}
for _, row := range grid {
for _, x := range row {
ans += x
}
}
return
}
# Accepted solution for LeetCode #1020: Number of Enclaves
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int):
grid[i][j] = 0
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y]:
dfs(x, y)
m, n = len(grid), len(grid[0])
dirs = (-1, 0, 1, 0, -1)
for j in range(n):
for i in (0, m - 1):
if grid[i][j]:
dfs(i, j)
for i in range(m):
for j in (0, n - 1):
if grid[i][j]:
dfs(i, j)
return sum(sum(row) for row in grid)
// Accepted solution for LeetCode #1020: Number of Enclaves
impl Solution {
pub fn num_enclaves(mut grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let dirs = [-1, 0, 1, 0, -1];
fn dfs(grid: &mut Vec<Vec<i32>>, i: usize, j: usize, dirs: &[i32; 5]) {
grid[i][j] = 0;
for k in 0..4 {
let (x, y) = (i as i32 + dirs[k], j as i32 + dirs[k + 1]);
if let Some(row) = grid.get_mut(x as usize) {
if let Some(&mut 1) = row.get_mut(y as usize) {
dfs(grid, x as usize, y as usize, dirs);
}
}
}
}
for j in 0..n {
if grid[0][j] == 1 {
dfs(&mut grid, 0, j, &dirs);
}
if grid[m - 1][j] == 1 {
dfs(&mut grid, m - 1, j, &dirs);
}
}
for i in 0..m {
if grid[i][0] == 1 {
dfs(&mut grid, i, 0, &dirs);
}
if grid[i][n - 1] == 1 {
dfs(&mut grid, i, n - 1, &dirs);
}
}
grid.into_iter().flatten().filter(|&x| x == 1).count() as i32
}
}
// Accepted solution for LeetCode #1020: Number of Enclaves
function numEnclaves(grid: number[][]): number {
const [m, n] = [grid.length, grid[0].length];
const dirs: number[] = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number) => {
grid[i][j] = 0;
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y <= n && grid[x][y] === 1) {
dfs(x, y);
}
}
};
for (let j = 0; j < n; ++j) {
for (let i of [0, m - 1]) {
if (grid[i][j] === 1) {
dfs(i, j);
}
}
}
for (let i = 0; i < m; ++i) {
for (let j of [0, n - 1]) {
if (grid[i][j] === 1) {
dfs(i, j);
}
}
}
return grid.flat().reduce((acc, cur) => acc + cur, 0);
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.