1568. Minimum Number of Days to Disconnect Island
Problem Description
You are presented with a grid, which is a 2D array, where the value 1 represents land and the value 0 represents water. An island is a group of 1s that are connected horizontally or vertically. The entire grid is considered connected if there is exactly one island in it. If there are no islands or more than one island, the grid is disconnected.
You are given the ability to convert one land cell (1) into a water cell (0) each day. The task is to find out the minimum number of days required to make the grid disconnected, meaning there are either zero islands or multiple islands.
Intuition
To solve this problem, the first step is to determine whether the grid is already disconnected. If there is more than one island or none at all, it is disconnected, and we can return 0 because we don't need any days to make it disconnected.
If the grid is connected, the next step is to check if we can make it disconnected by changing just one land cell into water. We attempt this by iterating through each land cell, temporarily converting it to water, and checking if this action results in a disconnected grid. If the conversion of any single land cell leads to a disconnected state, the answer is 1, which means we need only one day to disconnect the grid.
Finally, if none of these cases holds, it means that by removing any single land cell, the grid remains connected. In this scenario, we can conclude that a minimum of two days is required to disconnect the grid. The reasoning behind this is that any grid that is connected but doesn't get disconnected by the removal of any single land cell must have a structure that requires at least two removals to break apart.
The count function within the solution is a helper function that uses depth-first search (DFS) to count the number of islands in the grid. Whenever it finds a land cell, it marks not only that cell but also all connected land cells recursively as part of the same island (here marked with the value 2). After counting the islands, it resets the marked cells back to land to ensure the grid is restored to its original state before the function exit.
Learn more about Depth-First Search and Breadth-First Search patterns.
Which data structure is used in a depth first search?
Solution Approach
The solution is implemented using a depth-first search (DFS) algorithm and a pattern of checking adjacent cells in a grid.
minDays is the main function that returns the minimum number of days required to disconnect the grid.
-
We first check whether the grid is already disconnected by calling the
countfunction. If the count function returns a number different from1, it means we have either no islands or more than one island, in which case we return0days as the grid is already disconnected. -
If the grid is connected, we loop through each cell in the grid using a nested for loop. We are looking for land cells (
1) as water cells will not affect the connectivity. -
When we encounter a land cell, we temporarily change it to water (
0) and call thecountfunction again. If the count is not equal to1, which means the grid is disconnected by removing that single land cell, we restore the cell to land and return1day as the result. -
If we have gone through all the cells without disconnecting the grid, we conclude that it will take a minimum of
2days to disconnect it, since it wasn't possible to disconnect with a single cell change.
The count function implements the DFS algorithm:
-
It uses an auxiliary function called
dfsto conduct the depth-first search.dfsis invoked for every land cell (1) and marks all reachable land cells as part of the same island by setting them to2. -
It checks all four possible directions (left, right, up, down) around the current cell. This is done by iterating over the list of directions
[[0, -1], [0, 1], [1, 0], [-1, 0]], which represent the coordinate changes for the adjacent cells. -
Any cell found to be land (
1) during the DFS is recursively marked, effectively performing a flood fill of that island. -
Once all reachable parts of the island are marked with a
2, the recursive calls return. -
After marking an island, the
countfunction increments the island counter (cnt) and continues to search for other islands in the grid. -
Once done with counting, a further loop resets all the cells from
2back to1to restore the grid to its original state before exiting the function.
The use of DFS allows us to accurately determine the number of islands in the grid which is critical to deciding how many days are needed to disconnect the grid. This approach without additional memory saves space as we modify the grid in place and restore it after counting.
Which of the following uses divide and conquer strategy?
Example Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we have the following 2D grid:
11 1 0 21 0 1 30 1 1
Here, 1 represents land, and 0 represents water. We can see that currently there's a string of connected land forming a single island.
-
We first call the
countfunction to check if the grid is already disconnected. In our case, since there's only one island, thecountfunction will return1. This means the grid is connected and not already disconnected. -
Since the grid is connected, we then iterate over each cell looking for land cells. Let's start from the top-left and move right and down:
- The first cell
[0,0]is land. We temporarily convert it to water and call thecountfunction:
10 1 0 21 0 1 30 1 1The
countreturns2which indicates that the grid is now disconnected (two separate islands). We restore[0,0]back to land and conclude that changing this single land cell results in a disconnected grid. Therefore, we would need1day to disconnect the grid.- Even though we have already found the solution, for the sake of completeness, the procedure would be to continue iterating through the remaining land cells and test them in a similar fashion. However, since we're looking for the minimum number of days, we can stop the process as soon as we find that a single change can lead to a disconnected grid.
- The first cell
Our solution would return 1, as we have found that it is possible to disconnect the grid in a minimum of 1 day.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minDays(self, grid: List[List[int]]) -> int:
5 # If the number of islands is not one, return 0 as removing any cell is unnecessary.
6 if self.count_islands(grid) != 1:
7 return 0
8
9 # Get the dimensions of the grid
10 num_rows, num_cols = len(grid), len(grid[0])
11
12 # Iterate through each cell in the grid
13 for row in range(num_rows):
14 for col in range(num_cols):
15 # Checking if changing the land cell to water changes the number of islands
16 if grid[row][col] == 1:
17 # Change the land cell to water
18 grid[row][col] = 0
19 # If the number of islands is not one, return 1 as we have split the grid
20 if self.count_islands(grid) != 1:
21 return 1
22 # Change the cell back to land for further exploration
23 grid[row][col] = 1
24
25 # If we haven't returned before, it means changing any one cell won't split the grid
26 # Thus, we need to change at least two cells, hence return 2
27 return 2
28
29 def count_islands(self, grid: List[List[int]]) -> int:
30 # Helper function to perform Depth-First Search (DFS) to count the number of islands
31 def dfs(row: int, col: int):
32 grid[row][col] = 2 # Mark the currently visited land cell with a temporary marker
33 # Define the four possible directions to move (left, right, up, down)
34 directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]
35 # Explore the neighboring cells using the possible directions
36 for delta_row, delta_col in directions:
37 next_row, next_col = row + delta_row, col + delta_col
38 # Check if the next position is within bounds and is land
39 if 0 <= next_row < num_rows and 0 <= next_col < num_cols and grid[next_row][next_col] == 1:
40 dfs(next_row, next_col) # Continue DFS from this land cell
41
42 # Get the dimensions of the grid
43 num_rows, num_cols = len(grid), len(grid[0])
44 island_count = 0 # Counter for the number of islands
45
46 # Iterate through each cell in the grid and count the islands
47 for row in range(num_rows):
48 for col in range(num_cols):
49 if grid[row][col] == 1: # If a land cell is found
50 dfs(row, col) # Run DFS to mark the entire island
51 island_count += 1 # Increment the island count
52
53 # Revert the temporary markers back to original land cells
54 for row in range(num_rows):
55 for col in range(num_cols):
56 if grid[row][col] == 2:
57 grid[row][col] = 1
58
59 # Return the total number of islands found
60 return island_count
61
62# The code can be used like this:
63# solution = Solution()
64# result = solution.minDays([[0, 1, 1], [1, 1, 0], [0, 0, 0]])
65# print(result) # Output the result
661class Solution {
2 // Directions array for the 4 possible moves (up, right, down, left).
3 private static final int[] DIRS = new int[] { -1, 0, 1, 0, -1 };
4
5 // Instance variables for the grid and its dimensions.
6 private int[][] grid;
7 private int numRows;
8 private int numCols;
9
10 public int minDays(int[][] grid) {
11 this.grid = grid;
12 numRows = grid.length;
13 numCols = grid[0].length;
14
15 // If there are not exactly one island, return 0.
16 if (countIslands() != 1) {
17 return 0;
18 }
19
20 // Check each cell in the grid.
21 for (int i = 0; i < numRows; ++i) {
22 for (int j = 0; j < numCols; ++j) {
23 // If the current cell is land, remove it and count islands.
24 if (grid[i][j] == 1) {
25 grid[i][j] = 0;
26 if (countIslands() != 1) {
27 return 1; // If not exactly one island, return 1
28 }
29 // Revert the grid to its original state.
30 grid[i][j] = 1;
31 }
32 }
33 }
34
35 // If removing one land cell does not increase the number of islands,
36 // then it must take at least 2 days to break the structure.
37 return 2;
38 }
39
40 // Utility method to count the number of islands.
41 private int countIslands() {
42 int count = 0;
43 for (int i = 0; i < numRows; ++i) {
44 for (int j = 0; j < numCols; ++j) {
45 // If the cell is land, start DFS and increment island count.
46 if (grid[i][j] == 1) {
47 dfs(i, j);
48 ++count;
49 }
50 }
51 }
52
53 // Reset modified land cells (marked as 2 during DFS) back to 1.
54 for (int i = 0; i < numRows; ++i) {
55 for (int j = 0; j < numCols; ++j) {
56 if (grid[i][j] == 2) {
57 grid[i][j] = 1;
58 }
59 }
60 }
61 return count;
62 }
63
64 // Helper method to perform DFS and mark visited land cells.
65 private void dfs(int row, int col) {
66 grid[row][col] = 2; // Mark the current cell as visited.
67 // Explore all 4 directions from the current cell.
68 for (int k = 0; k < 4; ++k) {
69 int newRow = row + DIRS[k], newCol = col + DIRS[k + 1];
70 // Within the grid bounds and the cell is land.
71 if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && grid[newRow][newCol] == 1) {
72 dfs(newRow, newCol); // Continue DFS.
73 }
74 }
75 }
76}
771class Solution {
2public:
3 // Direction array to facilitate grid traversal.
4 const vector<int> directions = {-1, 0, 1, 0, -1};
5 // Variables to store grid dimensions.
6 int rows, cols;
7
8 // Function that returns the minimum number of days to isolate part of the grid.
9 int minDays(vector<vector<int>>& grid) {
10 // Initialize the dimensions.
11 rows = grid.size();
12 cols = grid[0].size();
13
14 // Check if the grid is already disconnected or not connected at all.
15 if (countIslands(grid) != 1) {
16 return 0; // A 0 will indicate no day required to isolate.
17 }
18
19 // Attempt removing each land piece to check if it can isolate an area.
20 for (int i = 0; i < rows; ++i) {
21 for (int j = 0; j < cols; ++j) {
22 // If the current cell is land.
23 if (grid[i][j] == 1) {
24 grid[i][j] = 0; // Temporarily remove the land piece.
25 // Check if removing this piece disconnects the grid.
26 if (countIslands(grid) != 1) {
27 return 1; // Returning 1 day required to isolate.
28 }
29 grid[i][j] = 1; // Restore the land piece.
30 }
31 }
32 }
33
34 // If no single piece removal leads to isolation, return 2 days.
35 return 2; //
36 }
37
38 // Helper function to count the number of islands (distinct connected components).
39 int countIslands(vector<vector<int>>& grid) {
40 int islandCount = 0;
41 // Iterate over the grid to find starting points of islands.
42 for (int i = 0; i < rows; ++i) {
43 for (int j = 0; j < cols; ++j) {
44 // If a cell is land, start DFS.
45 if (grid[i][j] == 1) {
46 dfs(i, j, grid);
47 ++islandCount; // Increment island count after a full DFS.
48 }
49 }
50 }
51 // Reset the grid to its original state after counting.
52 for (int i = 0; i < rows; ++i) {
53 for (int j = 0; j < cols; ++j) {
54 if (grid[i][j] == 2) {
55 grid[i][j] = 1; // Reset the state from temporary 2 to land (1).
56 }
57 }
58 }
59 return islandCount; // Return the total count of islands.
60 }
61
62 // Depth-first search to mark all cells of a single connected component.
63 void dfs(int row, int col, vector<vector<int>>& grid) {
64 grid[row][col] = 2; // Temporarily mark the cell as part of an island.
65 // Explore all four adjacent directions.
66 for (int k = 0; k < 4; ++k) {
67 int newRow = row + directions[k], newCol = col + directions[k + 1];
68 // If adjacent cell is in bounds and land, continue the DFS.
69 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == 1) {
70 dfs(newRow, newCol, grid);
71 }
72 }
73 }
74};
751// Direction array to facilitate grid traversal — 4 connected directions.
2const directions: number[] = [-1, 0, 1, 0, -1];
3
4// Variables to store grid dimensions.
5let rows: number;
6let cols: number;
7
8// Function that returns the minimum number of days to isolate part of the grid.
9function minDays(grid: number[][]): number {
10 // Initialize the dimensions.
11 rows = grid.length;
12 cols = grid[0].length;
13
14 // Check if the grid is already disconnected or not connected at all.
15 if (countIslands(grid) !== 1) {
16 return 0; // No day required to isolate if the grid is originally not connected.
17 }
18
19 // Attempt removing each land piece to check if it can isolate an area.
20 for (let i = 0; i < rows; i++) {
21 for (let j = 0; j < cols; j++) {
22 // If the current cell is land.
23 if (grid[i][j] === 1) {
24 grid[i][j] = 0; // Temporarily remove the land piece.
25 // Check if removing this piece results in disconnection.
26 if (countIslands(grid) !== 1) {
27 return 1; // Only 1 day required to isolate.
28 }
29 grid[i][j] = 1; // Restore the land piece after check.
30 }
31 }
32 }
33
34 // If no single piece removal leads to isolation, return 2 days.
35 return 2;
36}
37
38// Helper function to count the number of islands (distinct connected components).
39function countIslands(grid: number[][]): number {
40 let islandCount = 0;
41 // Iterate over the grid to find starting points of islands.
42 for (let i = 0; i < rows; i++) {
43 for (let j = 0; j < cols; j++) {
44 // If a cell is land, start DFS.
45 if (grid[i][j] === 1) {
46 dfs(i, j, grid);
47 islandCount++; // Increment island count after a complete DFS.
48 }
49 }
50 }
51 // Reset the grid to its original state after counting.
52 for (let i = 0; i < rows; i++) {
53 for (let j = 0; j < cols; j++) {
54 if (grid[i][j] === 2) {
55 grid[i][j] = 1; // Reset from temporary state (2) back to land (1).
56 }
57 }
58 }
59 return islandCount; // Return the total count of islands.
60}
61
62// Depth-first search to mark all cells of a single connected component.
63function dfs(row: number, col: number, grid: number[][]): void {
64 grid[row][col] = 2; // Temporarily mark the cell as part of this island.
65 // Explore all four connected directions.
66 for (let k = 0; k < 4; k++) {
67 let newRow = row + directions[k];
68 let newCol = col + directions[k + 1];
69
70 // If the adjacent cell is within bounds and is land, continue DFS.
71 if (
72 newRow >= 0 && newRow < rows &&
73 newCol >= 0 && newCol < cols &&
74 grid[newRow][newCol] === 1
75 ) {
76 dfs(newRow, newCol, grid);
77 }
78 }
79}
80Which of these properties could exist for a graph but not a tree?
Time and Space Complexity
Time Complexity
The minDays function includes a nested loop that iterates over every element in the grid once, and a call to the count function which performs a Depth-First Search (DFS). The nested loop has a time complexity of O(m*n) where m is the number of rows and n is the number of columns in the grid. Every time a 1 is encountered, a DFS is initiated by the count function.
The count function's DFS further goes through all elements in the grid potentially multiple times. In the worst-case scenario where the entire grid is filled with 1's, the DFS will visit every node once, leading to a time complexity of O(m*n) for each DFS execution.
However, since in the worst case, DFS is being invoked multiple times for each element in the grid (dependent on the number of separate islands or groups of 1s), the worst-case time complexity can be approximated to O((m*n)*(m*n)) or O(m^2 * n^2).
Space Complexity
The space complexity of the minDays function is dominated by the recursive calls of the DFS. In the worst-case scenario, the recursion stack can grow as deep as the number of 1 elements in the grid.
In the worst case, the entire grid could be an island (all 1's), which means that the recursion could call itself up to m*n times, leading to a space complexity of O(m*n) due to the stack space used by DFS.
Therefore, the total space complexity is O(m*n) for the DFS call stack.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended 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
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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.