1020. Number of Enclaves

Number of Enclaves (LeetCode 1020) 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.

How to solve Number of Enclaves

Number of Enclaves is a DFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Work towards the solution in these steps:

1. Can you model this problem as a graph problem? Create n * m + 1 nodes where n * m nodes represents each cell of the map and one extra node to represent the exterior of the map.
2. In the map add edges between neighbors on land cells. And add edges between the exterior and land nodes which are in the boundary. Return as answer the number of nodes that are not reachable from the exterior node.

The reference solution runs in O(m * n) time and O(m * n) space.

The Number of Enclaves solution and editorial walks through the full approach with reference code.

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

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
• Evaluate Division — Medium, same subpattern
• Flood Fill — Easy, same subpattern
• Island Perimeter — Easy, same subpattern
• Keys and Rooms — Medium, same subpattern

Number of Enclaves FAQ