Frontend School

Count Enclosed Land Cells

DSA
medium

Count Enclosed Land Cells

Medium
Matrix
DFS
BFS
Graph

Overview

Imagine you are a cartographer working on a digital map. Your task is to identify and count land cells that are completely enclosed by water or the map's boundaries. These enclosed land cells represent isolated territories that cannot be reached from the 'ocean' (the map's edges) by traversing land. This is critical for assessing internal resource accessibility or planning isolated settlements.

What you need to do / Task

You are given an m x n binary matrix grid, where 0 represents water and 1 represents land. Your goal is to return the number of land cells (1s) that are enclosed. A land cell is considered enclosed if it cannot reach the boundary of the grid by moving horizontally or vertically through other land cells. In other words, if you start at an enclosed land cell and only move to adjacent land cells, you will never reach any cell on the outermost rows or columns of the grid.

Input & output

  • Input: grid: number[][] - An m x n binary matrix where grid[i][j] is 0 (water) or 1 (land).
  • Output: number - The total count of enclosed land cells.

Clarifications

  • Movement: You can only move to adjacent cells (up, down, left, right). Diagonal movement is not allowed.
  • Boundary cells: Land cells on the boundary (first row, last row, first column, last column) are never considered enclosed, as they inherently touch the 'ocean'.
  • Small grids: For grids where m < 3 or n < 3, the number of enclosed land cells will always be 0, as any land cell would inherently touch a boundary.

Examples

1

Example 1

Input:

grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Output:

3

Note:

The land cells at (1,2), (2,1), and (2,2) are enclosed. (1,0) is a '1' but it's on the boundary, so it's not enclosed. All other '1's are surrounded by water or boundary-connected land and cannot reach the grid's edge.

2

Example 2

Input:

grid = [[0,1,1,0],[0,0,1,0],[0,0,0,0]]

Output:

0

Note:

The '1's at (0,1) and (0,2) are on the boundary. The '1' at (1,2) can reach the boundary via (0,2). Therefore, no land cells are enclosed.

3

Example 3

Input:

grid = [[0,0,0,0,0],[0,0,0,0,0],[0,1,1,1,0],[0,0,0,0,0],[0,0,0,0,0]]

Output:

3

Note:

The land cells at (2,1), (2,2), and (2,3) are completely surrounded by water and cannot reach the grid boundaries by traversing land. Therefore, they are enclosed.

Constraints

Constraints & assumptions

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid[i][j] is 0 or 1.

Out of scope

  • Optimizing for extremely sparse or dense grids beyond standard BFS/DFS complexities.
  • Handling non-binary input values.

What interviewers evaluate

  • Correctness: Does the solution accurately identify and count all enclosed land cells?
  • Algorithm Design: Is the chosen approach (e.g., BFS/DFS) appropriate and correctly applied to traverse connected components?
  • Edge Cases: How well does the solution handle small grids (e.g., 1xN, Nx1, 2x2) and grids with no enclosed cells?
  • Time and Space Complexity: Is the solution efficient in terms of time and space, especially for larger grids?

Loading editor...