1020. Number of Enclaves

How to solve Number of Enclaves (LeetCode 1020): the approach in brief

The problem

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

Pattern

Number of Enclaves is a Graph Traversal Patterns (DFS & BFS) problem, in the Graph DFS - Connected Components / Island Counting subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Approach outline

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.

Complexity

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

Asked at

Number of Enclaves has been reported in interviews at Google.