1020. Number of Enclaves

MediumDepth-First SearchBreadth-First SearchUnion FindArrayMatrix

Problem Description

You have a matrix where each cell can either be land (1) or sea (0). A move is defined as walking from one land cell to an adjacent land cell. Adjacent means above, below, to the left, or to the right (but not diagonally). The edge of the matrix is considered as a boundary that one can walk off from. The problem asks you to find out how many land cells are there in the matrix such that it's not possible to walk off the edge of the matrix starting from any of these cells; in other words, these land cells are enclosed by other land cells or by the matrix boundaries. This can be visualized as counting the number of land cells from which you cannot reach the sea by moving only horizontally or vertically on the land cells.

Flowchart Walkthrough

First, let's determine the appropriate algorithm using the Flowchart. We will follow the paths that lead us to deduce whether Depth-First Search (DFS) is suitable for solving this problem:

Is it a graph?

Yes: The grid in this problem can be treated as a graph where each cell acts as a node, and edges connect adjacent cells.

Is it a tree?

No: The grid-like structure comprises numerous possible connected components, and there is no hierarchical tree structure with a single root.

Is the problem related to directed acyclic graphs (DAGs)?

No: This problem involves finding regions (enclaves) in a grid, which does not pertain to the characteristics of DAGs.

Is the problem related to shortest paths?

No: The challenge is to calculate the number of cells in enclaves that are fully surrounded by water, not to find a path or its length.

Does the problem involve connectivity?

Yes: The crux of the problem involves identifying all the land cells (denoted by 1s) that are not connected to the borders, thereby marking them as enclaves.

Finally, since this is a question of connectivity analysis in a grid structure, DFS is the pattern suggested by the flowchart steps we followed. It works well for exploring each cell and marking or counting connected components, especially in this grid layout where recursively visiting neighboring cells is straightforward.

Conclusion: According to the flowchart and based on the characteristics of the problem, using DFS for identifying and processing cells inside enclaves is an optimal approach.

Intuition

To solve this problem, we can make use of a Depth-First Search (DFS) approach. The key intuition is to identify and eliminate the land cells that can lead to the boundary (and hence, to the sea), so that what remains will be our "enclosed" cells.

We start by iterating over the boundary rows and columns of the grid. If there's a land cell on the boundary, it means that this land cell can directly lead to the sea. But we also need to consider the land cells connected to it. Thus, we use DFS starting from this land cell on the boundary to traverse and "sink" all connected land cells, marking them as sea cells (by setting them to 0). "Sinking" in this context means we are marking the cell as visited and ensuring we won't count it later as an enclosed land cell.

DFS is continued until all cells that can reach the boundary are marked as sea cells. After marking these cells, the remaining land cells in the grid are guaranteed to be enclosed as they cannot reach the boundary.

Lastly, we count and return the number of cells left with a 1, which represents the number of enclosed land cells. For this, we simply iterate through the entire grid and sum up the values.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The solution utilizes a Depth-First Search (DFS) algorithm to explore and manipulate the grid. Here's a step-by-step explanation of how it works:

Define the dfs function, which will be used to mark the land cells that can lead to the boundary as sea cells. This function takes the current coordinates (i, j) of a land cell as arguments.
Inside the dfs function, the current land cell is first "sunk" by setting grid[i][j] to 0.
The function then iterates over the adjacent cells in the 4 cardinal directions using a tuple dirs that contains the relative coordinates to move up, down, left, and right. The pairwise pattern (a common programming idiom) is used to retrieve directions in pairs. However, in this particular solution code, it seems they have made an error by referring to pairwise(dirs), which should have been a traversal through the directions one by one; instead, this should be replaced with code that iterates over each pair of directions in dirs, something akin to (dirs[i], dirs[i + 1]) for i in range(len(dirs) - 1).
It checks if the new coordinates (x, y) are within the grid and if the cell is a land cell. If these conditions are met, DFS is recursively called on that cell.
Before starting the DFS, the main part of the function initializes the dimensions of the grid m and n.
The function then iterates over the cells on the boundaries of the grid - this is done by iterating through the rows and columns at the edges.
For each boundary cell that is land (has value 1), the DFS is called to "sink" the cell and any connected land cells.
After DFS traversal, all the cells that could walk off the boundary will be marked as 0.
Finally, the function counts and returns the number of cells with a value of 1, which now represent only the enclosed cells, by summing up all the values in the grid.

The data structure used here is the grid itself, which is a 2D list (a list of lists in Python), which is modified in place. The solution doesn't use any additional complex data structures. The DFS pattern is crucial for this solution, as it enables systematically visiting and modifying cells related to the boundary cells.

Please note that the actual code given has a mistake in the usage of pairwise, which isn't actually defined in the standard Python library's context and is not suitable for the way directions are used. It would need to be corrected for the code to function as intended.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a 5x5 matrix as a small example to illustrate the solution approach:

In this matrix, 1 indicates land, and 0 represents sea. We want to find out the number of land cells that are completely surrounded by other land cells or the borders of the matrix and thus cannot reach the edge.

Following the solution approach:

We enumerate the boundary cells. These would be cells in the first and last rows and columns.
As we check these cells, we find 1s at (0,0), (0,4), (4,3), and (4,4)on the corners and some other on the edges. We know these cannot be enclosed as they are on the matrix edge.
We begin our DFS with each of these boundary 1s to mark the connected land cells as 0 (sea). Starting with (0,0), we find it's already on the edge and mark it as 0. We do the same with other boundary 1s.

The matrix after sinking the boundary land cells is:

All reachable cells have been "sunk". The cand cells at (1,0), (1,1), (1,2), (2,0), (2,2), (3,0), (3,1), and (3,2) remain as 1s. Now, we only count the 1s not on the boundary.
We iterate over the remaining cells to count the number of land cells that are enclosed. From our matrix above, the count is 8.

Through this DFS approach, we have effectively identified and eliminated any land cell connected to the boundary. The remaining land cells are the enclosed cells that we are interested in counting.

Solution Implementation

1class Solution:
2    def numEnclaves(self, grid: List[List[int]]) -> int:
3        # Helper function to perform depth-first search and mark visited land cells as water
4        def dfs(row, col):
5            grid[row][col] = 0  # Mark the current cell as visited by setting it to 0 (water)
6
7            # Loop through the four directions (up, right, down, left)
8            for direction in range(4):
9                new_row = row + d_row[direction]
10                new_col = col + d_col[direction]
11
12                # Check if the new cell is within the bounds of the grid and is land
13                if 0 <= new_row < num_rows and 0 <= new_col < num_cols and grid[new_row][new_col]:
14                    dfs(new_row, new_col)  # Recursively apply DFS to the new cell
15
16        num_rows, num_cols = len(grid), len(grid[0])  # Get the dimension of the grid
17
18        # Directions for upward, rightward, downward, and leftward movement
19        d_row = [-1, 0, 1, 0]
20        d_col = [0, 1, 0, -1]
21
22        # Start DFS for the boundary cells that are land (i.e., have a value of 1)
23        for row in range(num_rows):
24            for col in range(num_cols):
25                if grid[row][col] and (row == 0 or row == num_rows - 1 or col == 0 or col == num_cols - 1):
26                    dfs(row, col)  # Remove enclaves touching the boundary by DFS
27
28        # Count the remaining land cells that are enclaves (not touching the boundaries)
29        return sum(value for row in grid for value in row)
30

1class Solution {
2    private int rows; // Total number of rows in the grid
3    private int columns; // Total number of columns in the grid
4    private int[][] grid; // The grid representing the land and water
5
6    // This method calculates the number of enclaves.
7    public int numEnclaves(int[][] grid) {
8        this.grid = grid; // Assigns the input grid to the instance variable grid
9        rows = grid.length; // Sets the number of rows
10        columns = grid[0].length; // Sets the number of columns
11      
12        // Iterate over the boundary cells of the grid
13        for (int i = 0; i < rows; ++i) {
14            for (int j = 0; j < columns; ++j) {
15                // On finding a land cell on the boundary, initiate DFS
16                if (grid[i][j] == 1 && (i == 0 || i == rows - 1 || j == 0 || j == columns - 1)) {
17                    dfs(i, j); // Call DFS to mark the connected land as water (0)
18                }
19            }
20        }
21      
22        // Count the land cells (value 1) that are not connected to the boundary
23        int enclaveCount = 0;
24        for (int[] row : grid) {
25            for (int value : row) {
26                enclaveCount += value;
27            }
28        }
29        return enclaveCount; // Return the number of cells in enclaves
30    }
31
32    // DFS method to convert connected land cells to water cells
33    private void dfs(int i, int j) {
34        grid[i][j] = 0; // Mark the current cell as water
35        int[] directions = {-1, 0, 1, 0, -1}; // Array representing the 4 directions (up, right, down, left)
36      
37        // Explore all 4 possible directions
38        for (int k = 0; k < 4; ++k) {
39            int x = i + directions[k]; // Compute the next row number
40            int y = j + directions[k + 1]; // Compute the next column number
41            // Check if the next cell is within the grid and is a land cell
42            if (x >= 0 && x < rows && y >= 0 && y < columns && grid[x][y] == 1) {
43                dfs(x, y); // Continue DFS from the next cell
44            }
45        }
46    }
47}
48

1#include <vector>
2#include <functional> // Needed for std::function
3
4class Solution {
5public:
6    int numEnclaves(std::vector<std::vector<int>>& grid) {
7        int numRows = grid.size();    // Number of rows in grid
8        int numCols = grid[0].size(); // Number of columns in grid
9      
10        // Direction vectors for exploring adjacent cells.
11        int directions[5] = {-1, 0, 1, 0, -1};
12      
13        // DFS function to explore and flip land cells (1's) into water cells (0's)
14        std::function<void(int, int)> depthFirstSearch = [&](int i, int j) {
15            grid[i][j] = 0; // Flip the current cell to water
16            for (int k = 0; k < 4; ++k) { // Explore all four adjacent cells
17                int x = i + directions[k], y = j + directions[k + 1];
18                // Check for bounds of grid and if the cell is land
19                if (x >= 0 && x < numRows && y >= 0 && y < numCols && grid[x][y]) {
20                    depthFirstSearch(x, y); // Continue DFS if adjacent cell is land
21                }
22            }
23        };
24      
25        // First pass to remove all land regions touching the grid boundaries
26        for (int i = 0; i < numRows; ++i) {
27            for (int j = 0; j < numCols; ++j) {
28                // Check if the current cell is land and at the border, then start DFS
29                if (grid[i][j] && (i == 0 || i == numRows - 1 || j == 0 || j == numCols - 1)) {
30                    depthFirstSearch(i, j);
31                }
32            }
33        }
34      
35        // After removing enclaves touching the border, count remaining enclaved lands
36        int enclaveCount = 0;
37        for (auto& row : grid) {
38            for (auto& cell : row) {
39                enclaveCount += cell; // Cell will be 1 if it's land not touching the border
40            }
41        }
42      
43        return enclaveCount; // Return the final count of enclaved lands
44    }
45};
46

1function numEnclaves(grid: number[][]): number {
2    // Get the number of rows and columns in the grid.
3    const rows = grid.length;
4    const cols = grid[0].length;
5
6    // Directions array represents the four possible movements (up, right, down, left).
7    const directions = [-1, 0, 1, 0, -1];
8
9    // Depth-first search function to mark land (1's) connected to the borders as water (0's).
10    const dfs = (row: number, col: number) => {
11        // Mark the current land piece as visited by setting it to 0.
12        grid[row][col] = 0;
13
14        // Explore all four directions.
15        for (let k = 0; k < 4; ++k) {
16            const nextRow = row + directions[k];
17            const nextCol = col + directions[k + 1];
18
19            // Check if the new coordinates are in bounds and if there is land to visit.
20            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] === 1) {
21                dfs(nextRow, nextCol);
22            }
23        }
24    };
25
26    // Run the DFS for lands connected to the borders to eliminate those.
27    for (let row = 0; row < rows; ++row) {
28        for (let col = 0; col < cols; ++col) {
29            // If the cell is land and it's on the border, start the DFS.
30            if (grid[row][col] === 1 && (row === 0 || row === rows - 1 || col === 0 || col === cols - 1)) {
31                dfs(row, col);
32            }
33        }
34    }
35
36    // Count the number of enclaved land pieces remaining in the grid.
37    let enclaveCount = 0;
38    for (const row of grid) {
39        for (const cell of row) {
40            enclaveCount += cell;
41        }
42    }
43
44    // Return the count of enclaves, which are land pieces not connected to the border.
45    return enclaveCount;
46}
47

Time and Space Complexity

The given code performs a Depth-First Search (DFS) on a two-dimensional grid to find the number of enclaves, which are regions of '1's not connected to the grid's border.

Time Complexity:

The time complexity of the code is O(m * n) where m is the number of rows and n is the number of columns in the grid. Each cell in the grid is processed at most once. The DFS is started from each border cell that contains a '1' and marks all reachable '1's as '0's (meaning they're visited). Since each cell can be part of only one DFS call (once it has been visited, it's turned to '0' and won't be visited again), each cell contributes only a constant amount of time. Therefore, the time complexity is proportional to the total number of cells in the grid.

Space Complexity:

The space complexity of the DFS is O(m * n) in the worst case, which happens when the grid is filled with '1's, and hence the call stack can grow to the size of the entire grid in a worst-case scenario of having a single large enclave. However, the function modifies the grid in-place and does not use any additional space proportional to the grid size, except for the recursion call stack. Thus the space complexity is determined by the depth of the recursion, which is O(m * n) in this worst case.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know