1020. Number of Enclaves Solution & Explanation

Q: Is Number of Enclaves easy or hard?

Number of Enclaves is rated Medium on LeetCode. The main challenge is recognizing that you should remove boundary-connected land first instead of trying to detect enclosed regions directly. Once that insight is clear, the DFS or BFS implementation is straightforward.

Q: How to solve Number of Enclaves in O(n)?

Treat the grid as a graph and perform a flood fill starting from all boundary land cells. Using DFS or BFS, mark every connected land cell as water or visited. After this elimination step, iterate through the grid and count the remaining land cells. Because each cell is visited only once, the runtime is O(m*n).

Q: What is the best approach for Number of Enclaves?

The most effective approach is boundary flood fill using DFS or BFS. Start from all land cells on the grid boundary and mark every reachable land cell as visited. After removing boundary-connected regions, count the remaining land cells. This runs in O(m*n) time and ensures each cell is processed only once.

Q: Is Number of Enclaves asked at Google/Amazon/Meta?

Grid traversal and flood-fill problems like Number of Enclaves frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests graph traversal on matrices and the ability to recognize boundary-based elimination strategies.

Q: What data structure is used in Number of Enclaves?

The problem treats the grid as a graph. DFS solutions rely on recursion or an explicit stack, while BFS solutions use a queue to process neighbors level by level. The grid itself often acts as the visited structure by converting visited land cells to water.

Q: What is the time complexity of Number of Enclaves?

Both DFS and BFS solutions run in O(m*n) time where m and n are the grid dimensions. Each cell is visited at most once during the flood fill and once during the final counting pass. Space complexity is O(m*n) in the worst case due to recursion stack or BFS queue usage.

Q: Number of Enclaves Python or Java solution approach?

Both Python and Java implementations typically perform DFS or BFS from boundary land cells. The algorithm marks all reachable land from the edges and then counts remaining cells with value 1. The complexity remains O(m*n) regardless of language.

The problem

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.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] is either 0 or 1.

Approach overview

Problem Overview: You are given a binary grid where 1 represents land and 0 represents water. An enclave is a land cell that cannot walk off the grid boundary by moving up, down, left, or right. The task is to count how many land cells are completely surrounded by water and cannot reach any boundary cell.

Approach 1: Depth-First Search (DFS) Flood Fill (Time: O(m*n), Space: O(m*n))

The key observation: land connected to the grid boundary can never be an enclave. Instead of searching for enclosed regions directly, eliminate all boundary-connected land first. Iterate over the grid edges and start a Depth-First Search from every boundary land cell. During DFS, mark each reachable land cell as water (or visited). This effectively removes every land region that can escape the grid. After the flood fill completes, iterate through the grid again and count the remaining 1 cells. Those are enclaves because they were never connected to the border.

This approach works because each cell is visited at most once during DFS traversal. The grid itself acts as the visited structure by flipping land to water. DFS is straightforward to implement and works well when recursion depth is manageable.

Approach 2: Breadth-First Search (BFS) Flood Fill (Time: O(m*n), Space: O(m*n))

This approach follows the same boundary-elimination idea but uses a queue-based Breadth-First Search. First scan the border of the matrix and push every boundary land cell into a queue. Then repeatedly pop cells and explore their four neighbors. If a neighbor is land, mark it visited and push it into the queue. BFS spreads outward from the edges and removes every land cell connected to the boundary.

After the BFS traversal finishes, any remaining land cells must be enclosed regions. A final pass over the grid counts them. BFS avoids recursion depth issues and is often preferred in languages where deep recursion can cause stack overflow.

Recommended for interviews: The boundary flood-fill idea is the expected insight. Either DFS or BFS works with identical O(m*n) time complexity because every cell is processed at most once. DFS is slightly shorter to code, while BFS is safer when recursion depth could exceed limits. Interviewers mainly look for the realization that you should start from boundary land and remove reachable cells instead of trying to detect enclaves directly.

Approach 1: Approach 1: Depth-First Search (DFS)

This approach uses a depth-first search (DFS) to mark land cells connected to the boundaries. We iterate over the boundary cells of the grid and if a land cell is found, we perform DFS to mark all connected land cells as visited. Finally, we count all remaining unvisited land cells inside the grid, which are considered enclaves.

Python

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int):
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
                return
            grid[i][j] = 0
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)

        m, n = len(grid), len(grid[0])
        for i in range(m):
            if grid[i][0] == 1:
                dfs(i, 0)
            if grid[i][n - 1] == 1:
                dfs(i, n - 1)
        for j in range(n):
            if grid[0][j] == 1:
                dfs(0, j)
            if grid[m - 1][j] == 1:
                dfs(m - 1, j)

        return sum(grid[i][j] for i in range(1, m - 1) for j in range(1, n - 1) if grid[i][j] == 1)

Java

class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                dfs(grid, i, 0);
            }
            if (grid[i][n - 1] == 1) {
                dfs(grid, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) {
                dfs(grid, 0, j);
            }
            if (grid[m - 1][j] == 1) {
                dfs(grid, m - 1, j);
            }
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(int[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0) {
            return;
        }
        grid[i][j] = 0;
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

C++

#include <vector>
using namespace std;

void dfs(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) {
        return;
    }
    grid[i][j] = 0;
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

int numEnclaves(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    for (int i = 0; i < m; i++) {
        if (grid[i][0] == 1) {
            dfs(grid, i, 0);
        }
        if (grid[i][n-1] == 1) {
            dfs(grid, i, n-1);
        }
    }
    for (int j = 0; j < n; j++) {
        if (grid[0][j] == 1) {
            dfs(grid, 0, j);
        }
        if (grid[m-1][j] == 1) {
            dfs(grid, m-1, j);
        }
    }

    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                count++;
            }
        }
    }
    return count;
}

JavaScript

var numEnclaves = function(grid) {
    const dfs = (i, j) => {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === 0) {
            return;
        }
        grid[i][j] = 0;
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    };

    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        if (grid[i][0] === 1) dfs(i, 0);
        if (grid[i][n - 1] === 1) dfs(i, n - 1);
    }
    for (let j = 0; j < n; j++) {
        if (grid[0][j] === 1) dfs(0, j);
        if (grid[m - 1][j] === 1) dfs(m - 1, j);
    }

    let count = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                count++;
            }
        }
    }
    return count;
};

#include <stdio.h>

void dfs(int** grid, int m, int n, int i, int j) {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) {
        return;
    }
    grid[i][j] = 0; // Marking visited land
    dfs(grid, m, n, i + 1, j);
    dfs(grid, m, n, i - 1, j);
    dfs(grid, m, n, i, j + 1);
    dfs(grid, m, n, i, j - 1);
}

int numEnclaves(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize;
    int n = *gridColSize;
    for (int i = 0; i < m; i++) {
        if (grid[i][0] == 1) {
            dfs(grid, m, n, i, 0);
        }
        if (grid[i][n-1] == 1) {
            dfs(grid, m, n, i, n-1);
        }
    }
    for (int j = 0; j < n; j++) {
        if (grid[0][j] == 1) {
            dfs(grid, m, n, 0, j);
        }
        if (grid[m-1][j] == 1) {
            dfs(grid, m, n, m-1, j);
        }
    }
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                count++;
            }
        }
    }
    return count;
}

public class Solution {
    public int NumEnclaves(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;

        void Dfs(int i, int j) {
            if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) {
                return;
            }
            grid[i][j] = 0;
            Dfs(i + 1, j);
            Dfs(i - 1, j);
            Dfs(i, j + 1);
            Dfs(i, j - 1);
        }

        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                Dfs(i, 0);
            }
            if (grid[i][n - 1] == 1) {
                Dfs(i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) {
                Dfs(0, j);
            }
            if (grid[m - 1][j] == 1) {
                Dfs(m - 1, j);
            }
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        return count;
    }
}

In this Python implementation, DFS is defined as an inner function. The method iterates over boundary cells, marking connected land cells. Finally, it sums remaining inner land cells (enclaves).

Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) due to potential for maximum recursion depth.

Try this approach in the editor

Approach 2: Approach 2: Breadth-First Search (BFS)

In this approach, we use a queue to perform BFS to mark land cells connected to the boundaries. By enqueueing each boundary land cell and exploring its neighbors iteratively, we can mark all reachable boundary-connected lands. This is followed by counting the unvisited land cells – those are the enclaves.

Python

from collections import deque

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def bfs(start_i: int, start_j: int):
            queue = deque([(start_i, start_j)])
            grid[start_i][start_j] = 0
            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            while queue:
                x, y = queue.popleft()
                for dx, dy in directions:
                    new_x, new_y = x + dx, y + dy
                    if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 1:
                        grid[new_x][new_y] = 0
                        queue.append((new_x, new_y))

        for i in range(m):
            if grid[i][0] == 1:
                bfs(i, 0)
            if grid[i][n - 1] == 1:
                bfs(i, n - 1)

        for j in range(n):
            if grid[0][j] == 1:
                bfs(0, j)
            if grid[m - 1][j] == 1:
                bfs(m - 1, j)

        return sum(grid[i][j] == 1 for i in range(m) for j in range(n))

Java

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) bfs(grid, i, 0);
            if (grid[i][n - 1] == 1) bfs(grid, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) bfs(grid, 0, j);
            if (grid[m - 1][j] == 1) bfs(grid, m - 1, j);
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) count++;
            }
        }
        return count;
    }

    private void bfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{i, j});
        grid[i][j] = 0;
        int[][] directions =new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            for (int[] dir : directions) {
                int newRow = cell[0] + dir[0];
                int newCol = cell[1] + dir[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
                    grid[newRow][newCol] = 0;
                    q.offer(new int[]{newRow, newCol});
                }
            }
        }
    }
}

C++

#include <vector>
#include <queue>
using namespace std;

void bfs(vector<vector<int>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int, int>> q;
    q.push({i, j});
    grid[i][j] = 0;
    vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        for (auto& d : directions) {
            int newRow = r + d[0], newCol = c + d[1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
                grid[newRow][newCol] = 0;
                q.push({newRow, newCol});
            }
        }
    }
}

int numEnclaves(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    
    for (int i = 0; i < m; i++) {
        if (grid[i][0] == 1) bfs(grid, i, 0);
        if (grid[i][n-1] == 1) bfs(grid, i, n-1);
    }
    for (int j = 0; j < n; j++) {
        if (grid[0][j] == 1) bfs(grid, 0, j);
        if (grid[m-1][j] == 1) bfs(grid, m-1, j);
    }

    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) count++;
        }
    }
    return count;
}

JavaScript

var numEnclaves = function(grid) {
    const bfs = (startRow, startCol) => {
        const queue = [];
        queue.push([startRow, startCol]);
        grid[startRow][startCol] = 0;
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

        while (queue.length !== 0) {
            const [r, c] = queue.shift();
            for (const [dx, dy] of directions) {
                const newRow = r + dx;
                const newCol = c + dy;
                if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid[0].length && grid[newRow][newCol] === 1) {
                    grid[newRow][newCol] = 0;
                    queue.push([newRow, newCol]);
                }
            }
        }
    };

    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m; i++) {
        if (grid[i][0] === 1) bfs(i, 0);
        if (grid[i][n - 1] === 1) bfs(i, n - 1);
    }
    for (let j = 0; j < n; j++) {
        if (grid[0][j] === 1) bfs(0, j);
        if (grid[m - 1][j] === 1) bfs(m - 1, j);
    }

    let count = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                count++;
            }
        }
    }
    return count;
};

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int row;
    int col;
} Point;

int** directions = (int* []){(int[]){1, 0}, (int[]){-1, 0}, (int[]){0, 1}, (int[]){0, -1}};

void bfs(int** grid, int m, int n, int startRow, int startCol) {
    Point* queue = (Point*)malloc(m * n * sizeof(Point));
    int front = 0, rear = 0;
    queue[rear++] = (Point){startRow, startCol};
    grid[startRow][startCol] = 0;
    while (front < rear) {
        Point current = queue[front++];
        for (int d = 0; d < 4; d++) {
            int newRow = current.row + directions[d][0];
            int newCol = current.col + directions[d][1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
                grid[newRow][newCol] = 0;
                queue[rear++] = (Point){newRow, newCol};
            }
        }
    }
    free(queue);
}

int numEnclaves(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = *gridColSize;

    for (int i = 0; i < m; i++) {
        if (grid[i][0] == 1) bfs(grid, m, n, i, 0);
        if (grid[i][n - 1] == 1) bfs(grid, m, n, i, n - 1);
    }
    for (int j = 0; j < n; j++) {
        if (grid[0][j] == 1) bfs(grid, m, n, 0, j);
        if (grid[m - 1][j] == 1) bfs(grid, m, n, m - 1, j);
    }

    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) count++;
        }
    }
    return count;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int NumEnclaves(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;

        void Bfs(int startRow, int startCol) {
            Queue<(int, int)> queue = new Queue<(int, int)>();
            queue.Enqueue((startRow, startCol));
            grid[startRow][startCol] = 0;
            int[][] directions = new int[][] { new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1} };
            while (queue.Count > 0) {
                var (r, c) = queue.Dequeue();
                foreach (var dir in directions) {
                    int newRow = r + dir[0], newCol = c + dir[1];
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 0;
                        queue.Enqueue((newRow, newCol));
                    }
                }
            }
        }

        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) Bfs(i, 0);
            if (grid[i][n - 1] == 1) Bfs(i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) Bfs(0, j);
            if (grid[m - 1][j] == 1) Bfs(m - 1, j);
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) count++;
            }
        }
        return count;
    }
}

The Python solution utilizes a deque for breadth-first traversal from the boundary. As it iterates over the boundary cells, deque adds and processes reachable land cells, marking them as explored. Enclaves are counted as left-over land.

Complexity

Time Complexity: O(m * n).
Space Complexity: O(min(m, n)) due to deque's space consumption.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function numEnclaves(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dirs = [-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 i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] === 1 && (i === 0 || i === m - 1 || j === 0 || j === n - 1)) {
                dfs(i, j);
            }
        }
    }
    let ans = 0;
    for (const row of grid) {
        for (const v of row) {
            ans += v;
        }
    }
    return ans;
}

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 i, row := range grid {
		for j, v := range row {
			if v == 1 && (i == 0 || i == m-1 || j == 0 || j == n-1) {
				dfs(i, j)
			}
		}
	}
	for _, row := range grid {
		for _, v := range row {
			ans += v
		}
	}
	return
}

Rust

impl Solution {
    fn dfs(grid: &mut Vec<Vec<i32>>, y: usize, x: usize) {
        if y >= grid.len() || x >= grid[0].len() || grid[y][x] == 0 {
            return;
        }
        grid[y][x] = 0;
        Solution::dfs(grid, y + 1, x);
        Solution::dfs(grid, y, x + 1);
        if y != 0 {
            Solution::dfs(grid, y - 1, x);
        }
        if x != 0 {
            Solution::dfs(grid, y, x - 1);
        }
    }
    pub fn num_enclaves(mut grid: Vec<Vec<i32>>) -> i32 {
        let mut res = 0;
        let m = grid.len();
        let n = grid[0].len();
        for i in 0..m {
            Solution::dfs(&mut grid, i, 0);
            Solution::dfs(&mut grid, i, n - 1);
        }
        for i in 0..n {
            Solution::dfs(&mut grid, 0, i);
            Solution::dfs(&mut grid, m - 1, i);
        }
        for i in 1..m - 1 {
            for j in 1..n - 1 {
                if grid[i][j] == 1 {
                    res += 1;
                }
            }
        }
        res
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Depth-First Search (DFS)	Time Complexity: O(m * n) Space Complexity: O(m * n) due to potential for maximum recursion depth.
Approach 2: Breadth-First Search (BFS)	Time Complexity: O(m * n). Space Complexity: O(min(m, n)) due to deque's space consumption.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Depth-First Search (DFS) Flood Fill	O(m*n)	O(m*n) recursion stack worst case	Simple implementation when recursion depth is manageable
Breadth-First Search (BFS) Flood Fill	O(m*n)	O(m*n) queue in worst case	Preferred when avoiding recursion or stack overflow concerns

Frequently asked questions

Is Number of Enclaves easy or hard?

Number of Enclaves is rated Medium on LeetCode. The main challenge is recognizing that you should remove boundary-connected land first instead of trying to detect enclosed regions directly. Once that insight is clear, the DFS or BFS implementation is straightforward.

How to solve Number of Enclaves in O(n)?

Treat the grid as a graph and perform a flood fill starting from all boundary land cells. Using DFS or BFS, mark every connected land cell as water or visited. After this elimination step, iterate through the grid and count the remaining land cells. Because each cell is visited only once, the runtime is O(m*n).

What is the best approach for Number of Enclaves?

The most effective approach is boundary flood fill using DFS or BFS. Start from all land cells on the grid boundary and mark every reachable land cell as visited. After removing boundary-connected regions, count the remaining land cells. This runs in O(m*n) time and ensures each cell is processed only once.

Is Number of Enclaves asked at Google/Amazon/Meta?

Grid traversal and flood-fill problems like Number of Enclaves frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests graph traversal on matrices and the ability to recognize boundary-based elimination strategies.

What data structure is used in Number of Enclaves?

The problem treats the grid as a graph. DFS solutions rely on recursion or an explicit stack, while BFS solutions use a queue to process neighbors level by level. The grid itself often acts as the visited structure by converting visited land cells to water.

What is the time complexity of Number of Enclaves?

Both DFS and BFS solutions run in O(m*n) time where m and n are the grid dimensions. Each cell is visited at most once during the flood fill and once during the final counting pass. Space complexity is O(m*n) in the worst case due to recursion stack or BFS queue usage.

Number of Enclaves Python or Java solution approach?

Both Python and Java implementations typically perform DFS or BFS from boundary land cells. The algorithm marks all reachable land from the edges and then counts remaining cells with value 1. The complexity remains O(m*n) regardless of language.

Number of Enclaves solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Depth-First Search (DFS)

Approach 2: Approach 2: Breadth-First Search (BFS)

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Number of Enclaves solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Depth-First Search (DFS)

Approach 2: Approach 2: Breadth-First Search (BFS)

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems