Number of Enclaves

Number of Enclaves is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.

Problem statement

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.

Topics and companies

Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix.

Reported in interviews at Google.

How to practise Number of Enclaves on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.

Open Number of Enclaves in the code editor, or read the Number of Enclaves editorial for a worked solution with its approach and complexity analysis.

Where Number of Enclaves sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph DFS - Connected Components / Island Counting subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Number of Enclaves

Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

• Count Sub Islands — Medium, same subpattern
• Detonate the Maximum Bombs — Medium, same subpattern
• Flood Fill — Easy, same subpattern
• Keys and Rooms — Medium, same subpattern
• Max Area of Island — Medium, same subpattern
• Number of Closed Islands — Medium, same subpattern