Number of Enclaves

MediumGraphsdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n binary grid where 1 is land and 0 is sea. From a land cell you may walk to an edge-adjacent land cell (up, down, left, right), or walk off the grid if you are on its boundary. Return the number of land cells from which it is **impossible** to walk off the grid in any number of moves. Aim for O(m * n) time.

Examples

Input: grid = [[0,0,0,0,0],[0,1,1,0,1],[0,0,1,0,0],[1,0,0,1,0],[0,0,0,0,0]]
Output: 4
The group at (1,1), (1,2), (2,2) and the lone cell at (3,3) never touch the border. The cells at (1,4) and (3,0) sit on the border.
Input: grid = [[1,1],[1,1]]
Output: 0
Every land cell is on the boundary.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems