☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Number of enclaves

Medium TUF ID 533 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n × m grid where 0 is sea and 1 is land. From a land cell you may step to an adjacent land cell (up, down, left or right), and from a land cell on the border you may also step off the grid. Return the number of land cells from which it is impossible to walk off the grid, no matter how many moves you make. These cells are called enclaves.

Constraints: 1 ≤ n, m ≤ 500.

Example 1

0 0 0 0
1 0 1 0
0 1 1 0
0 0 0 0
answer = 3

(1,0) is on the border, so it can walk off. The three cells (1,2), (2,1), (2,2) form an island that touches no border, so all three are enclaves.

Example 2

0 1 1 0
0 0 1 0
0 0 1 0
0 0 0 0
answer = 0

Every land cell is connected to (0,1) or (0,2) in the top row, so every land cell can escape.

The problem is really about connectivity to the border. A land cell can escape exactly when its island contains at least one border cell. So the answer is the total size of all islands that never touch the border.

Approach 1: Brute force, one search per land cell

Intuition. Follow the statement literally: for every land cell, run a BFS through land and see whether it ever stands on the border. If it does, one more step leaves the grid. Count the cells for which the search fails.

Algorithm.

  1. For every land cell (i, j), call canEscape(i, j).
  2. canEscape runs a BFS over land cells and returns true as soon as it dequeues a border cell.
  3. Count the cells for which it returns false.
static final int[] DR = {-1, 0, 1, 0}, DC = {0, 1, 0, -1};

static int bruteForce(int[][] grid) {
    int n = grid.length, m = grid[0].length, count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1 && !canEscape(grid, i, j)) count++;
        }
    }
    return count;
}

static boolean canEscape(int[][] grid, int sr, int sc) {
    int n = grid.length, m = grid[0].length;
    boolean[][] seen = new boolean[n][m];
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{sr, sc});
    seen[sr][sc] = true;
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        int r = cell[0], c = cell[1];
        if (r == 0 || c == 0 || r == n - 1 || c == m - 1) return true;   // one more step walks off the grid
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (grid[nr][nc] == 1 && !seen[nr][nc]) { seen[nr][nc] = true; q.offer(new int[]{nr, nc}); }
        }
    }
    return false;
}

A cell only expands its neighbours after the border test has failed, so it is an interior cell and its four neighbours are inside the grid. No bounds check is needed.

Complexity. Time O((n·m)^2): an island of k cells is searched k times, and one island can cover most of the grid. Space O(n·m) for one search’s seen array.

Approach 2: Optimal, multi-source BFS from the border

Intuition. Every brute-force search on the same island repeats the same work. Flip the direction: a land cell can escape exactly when it can be reached from a border land cell, because moves between land cells are symmetric. So start one BFS with every border land cell in the queue at once and mark everything it reaches. Those marked cells are the escapable ones. Any land cell left unmarked is an enclave.

Why start them all together instead of one BFS per border cell? Either works and both are linear, since a cell once marked is never expanded again. Putting them all in the queue at the start is simply the cleanest way to say “flood from the entire border”.

Algorithm.

  1. Enqueue and mark every land cell on the border.
  2. Run BFS: for each dequeued cell, mark and enqueue every unmarked land neighbour.
  3. Count land cells that are not marked.
static int optimalBfs(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    boolean[][] vis = new boolean[n][m];
    Deque<int[]> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            boolean border = i == 0 || j == 0 || i == n - 1 || j == m - 1;
            if (border && grid[i][j] == 1) { vis[i][j] = true; q.offer(new int[]{i, j}); }
        }
    }
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        for (int k = 0; k < 4; k++) {
            int r = cell[0] + DR[k], c = cell[1] + DC[k];
            if (r >= 0 && c >= 0 && r < n && c < m && grid[r][c] == 1 && !vis[r][c]) {
                vis[r][c] = true;
                q.offer(new int[]{r, c});
            }
        }
    }
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (grid[i][j] == 1 && !vis[i][j]) count++;
    return count;
}

Dry run on Example 1. Border land cells: only (1,0).

step dequeued newly marked
start   (1,0)
1 (1,0) none, its neighbours (0,0), (2,0), (1,1) are sea

The queue is empty. Land cells (1,2), (2,1), (2,2) are unmarked, so the answer is 3.

Complexity. Time O(n·m): every cell is enqueued at most once and has four neighbours. Space O(n·m) for vis and the queue.

Approach 3: DFS per island

Intuition. Another linear method that follows the “answer = total size of islands that never touch the border” view directly. Scan the grid; each time we meet unvisited land, flood its whole island with DFS, counting the cells and noting whether any of them is on the border. If the island never touched the border, add its size to the answer. Each cell is visited once over the whole scan.

The info array is a small trick to return two values from a recursive method: info[0] is the island’s size and info[1] becomes 1 once a border cell is seen.

static int optimalDfs(int[][] grid) {
    int n = grid.length, m = grid[0].length, count = 0;
    boolean[][] vis = new boolean[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1 && !vis[i][j]) {
                int[] info = new int[2];             // {cells in this island, 1 if it touches the border}
                explore(grid, i, j, vis, info);
                if (info[1] == 0) count += info[0];
            }
        }
    }
    return count;
}

static void explore(int[][] grid, int r, int c, boolean[][] vis, int[] info) {
    int n = grid.length, m = grid[0].length;
    if (r < 0 || c < 0 || r >= n || c >= m || grid[r][c] == 0 || vis[r][c]) return;
    vis[r][c] = true;
    info[0]++;
    if (r == 0 || c == 0 || r == n - 1 || c == m - 1) info[1] = 1;
    for (int k = 0; k < 4; k++) explore(grid, r + DR[k], c + DC[k], vis, info);
}

Complexity. Time O(n·m). Space O(n·m) for vis, plus recursion depth up to the size of the largest island, which can reach n·m on a snake-shaped island. For big grids prefer the BFS version.

Edge cases and pitfalls