How do you solve Number of Enclaves on LeetCode?

Number of Enclaves (LeetCode #1020) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: Cells on the boundary can directly reach the edge and are not enclaves.

What is the brute force solution for Number of Enclaves?

The brute force approach for Number of Enclaves is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking each land cell to see if it can reach the boundary. If it can't, we count it as an enclave. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Number of Enclaves?

Number of Enclaves uses the following concepts: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. The recommended patterns to study are: Depth-First Search, Breadth-First Search, Graph Traversal.

What are the interview tips for Number of Enclaves?

Always clarify the problem and constraints before jumping into coding. Think about edge cases and how your solution handles them. Explain your thought process while coding to demonstrate your understanding.

What are common mistakes when solving Number of Enclaves?

Forgetting to mark visited cells, leading to infinite loops. Not considering edge cases like small grids.

#1020

Number of Enclaves

Medium

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First SearchBreadth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal approach uses a modified DFS or BFS to mark all land cells connected to the boundary. This way, we can efficiently count the remaining land cells that are enclaves.

⚙️

Algorithm

3 steps

1Step 1: Iterate through the boundary cells of the grid.
2Step 2: For each land cell (1) found on the boundary, perform a DFS/BFS to mark all reachable land cells as visited.
3Step 3: After marking, count the remaining land cells (1s) that are not visited.

solution.py16 lines

1def numEnclaves(grid):
2    def dfs(x, y):
3        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == 0:
4            return
5        grid[x][y] = 0  # Mark as visited
6        dfs(x + 1, y)
7        dfs(x - 1, y)
8        dfs(x, y + 1)
9        dfs(x, y - 1)
10
11    for i in range(len(grid)):
12        for j in range(len(grid[0])):
13            if (i == 0 or i == len(grid) - 1 or j == 0 or j == len(grid[0]) - 1) and grid[i][j] == 1:
14                dfs(i, j)
15
16    return sum(row.count(1) for row in grid)

ℹ

Complexity note: The time complexity remains O(n²) since we still potentially visit every cell in the grid. The space complexity is O(1) as we are modifying the grid in place without using additional data structures.

1Cells on the boundary can directly reach the edge and are not enclaves.
2Using DFS/BFS allows us to efficiently mark connected components.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.