1020. Number of Enclaves
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.
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.
Which of the following shows the order of node visit in a Breadth-first Search?
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
dfsfunction, 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
dfsfunction, the current land cell is first "sunk" by settinggrid[i][j]to0. -
The function then iterates over the adjacent cells in the 4 cardinal directions using a tuple
dirsthat contains the relative coordinates to move up, down, left, and right. Thepairwisepattern (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 topairwise(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 indirs, something akin to(dirs[i], dirs[i + 1])foriin 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
mandn. -
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.
Depth first search is equivalent to which of the tree traversal order?
Example Walkthrough
Let's consider a 5x5 matrix as a small example to illustrate the solution approach:
11 0 0 0 1 21 1 1 0 1 31 0 1 0 0 41 1 1 0 1 51 0 0 1 1
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 as0(sea). Starting with(0,0), we find it's already on the edge and mark it as0. We do the same with other boundary1s.
The matrix after sinking the boundary land cells is:
10 0 0 0 0 21 1 1 0 0 31 0 1 0 0 41 1 1 0 0 51 0 0 0 0
-
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 as1s. Now, we only count the1s 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)
301class 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}
481#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};
461function 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}
47What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.