Scale Engineer

Number of Enclaves

Med
#0974Time: O((m*n)²) - In the worst-case scenario, for each of the O(m*n) land cells, we might perform a traversal that visits all O(m*n) cells. This results in a quadratic time complexity.Space: O(m*n) - For each check, a `visited` matrix of size m*n is created. The queue used for BFS can also grow up to O(m*n) in the worst case.
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
ArrayMatrix

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every cell in the grid. For each land cell (1), it performs an independent search (like Depth-First Search or Breadth-First Search) to determine if a path exists from that cell to the grid's boundary. If a cell is a land cell and no such path to the boundary can be found, it is counted as an enclave cell.

Algorithm

  • Initialize enclave_count = 0.
  • Iterate through each cell (r, c) of the grid.
  • If grid[r][c] is 1:
    • Perform a traversal (e.g., BFS) starting from (r, c) to see if it can reach a boundary cell. This requires a new visited array for each starting cell.
    • During the traversal, if any visited cell is on the boundary, we know the starting cell (r, c) can escape.
    • If the entire traversal completes without finding a path to the boundary, the starting cell (r, c) is an enclave cell. Increment enclave_count.
  • Return enclave_count.

Walkthrough

The algorithm proceeds cell by cell. For every single land cell, we initiate a new traversal to check its connectivity to the boundary. This leads to a lot of repeated work, as cells belonging to the same island will be re-explored multiple times.

class Solution {    public int numEnclaves(int[][] grid) {        int m = grid.length;        int n = grid[0].length;        int enclaveCount = 0;        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1) {                    if (!canReachBoundary(grid, i, j, m, n)) {                        enclaveCount++;                    }                }            }        }        return enclaveCount;    }     private boolean canReachBoundary(int[][] grid, int r, int c, int m, int n) {        boolean[][] visited = new boolean[m][n];        java.util.Queue<int[]> queue = new java.util.LinkedList<>();                queue.offer(new int[]{r, c});        visited[r][c] = true;         int[] dr = {-1, 1, 0, 0};        int[] dc = {0, 0, -1, 1};         while (!queue.isEmpty()) {            int[] cell = queue.poll();            int row = cell[0];            int col = cell[1];             if (row == 0 || row == m - 1 || col == 0 || col == n - 1) {                return true; // Found a path to the boundary            }             for (int i = 0; i < 4; i++) {                int newRow = row + dr[i];                int newCol = col + dc[i];                 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&                    grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {                    visited[newRow][newCol] = true;                    queue.offer(new int[]{newRow, newCol});                }            }        }        return false; // No path to the boundary found    }}

Complexity

Time

O((m*n)²) - In the worst-case scenario, for each of the O(m*n) land cells, we might perform a traversal that visits all O(m*n) cells. This results in a quadratic time complexity.

Space

O(m*n) - For each check, a `visited` matrix of size m*n is created. The queue used for BFS can also grow up to O(m*n) in the worst case.

Trade-offs

Pros

  • Conceptually straightforward, as it directly translates the question: 'for each land cell, can it reach the boundary?'

Cons

  • Extremely inefficient due to massive redundant computations.

  • Traverses the same group of connected land cells multiple times, once for each cell in that group.

  • Likely to result in a 'Time Limit Exceeded' error on larger inputs.

Solutions

class Solution {private  int m;private  int n;private  int[][] grid;public  int numEnclaves(int[][] grid) {    this.grid = grid;    m = grid.length;    n = grid[0].length;    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 1 && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {          dfs(i, j);        }      }    }    int ans = 0;    for (var row : grid) {      for (var v : row) {        ans += v;      }    }    return ans;  }private  void dfs(int i, int j) {    grid[i][j] = 0;    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 < m && y >= 0 && y < n && grid[x][y] == 1) {        dfs(x, y);      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem