1568. Minimum Number of Days to Disconnect Island

HardDepth-First SearchBreadth-First SearchArrayMatrixStrongly Connected Component

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.

Flowchart Walkthrough

To analyze LeetCode problem 1568. Minimum Number of Days to Disconnect Island using the Flowchart, let's go through the decision-making steps.

Is it a graph?

Yes: The problem considers a 2D grid where each water or land cell can be thought of as a node connected with its adjacent cells.

Is it a tree?

No: The grid may form multiple connected components or cycles, and it's typically a complex map, so it does not have the hierarchical structure of a tree.

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

No: This problem deals with a grid involving connectivity and potential removal of areas, not acyclic graph properties.

Is the problem related to shortest paths?

No: The goal is to calculate the minimum number of days to disconnect all lands, which is unrelated to finding shortest paths.

Does the problem involve connectivity?

Yes: A key aspect is to assess and modify the connectivity among the land pieces in the grid.

Since the problem involves connectivity but not shortest distances or paths:

Is the graph weighted?
- No: All cells are treated equally, without different weights assigned to pass from one cell to another.

Conclusion: The flowchart suggests utilizing Depth-First Search (DFS) to manipulate and assess the connectivity of lands effectively within the grid, allowing us to determine the number of disconnections needed over days. DFS is optimal here for exploring and modifying the structure of the connected components in the grid.

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.

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 count function. If the count function returns a number different from 1, it means we have either no islands or more than one island, in which case we return 0 days 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 the count function again. If the count is not equal to 1, which means the grid is disconnected by removing that single land cell, we restore the cell to land and return 1 day as the result.
If we have gone through all the cells without disconnecting the grid, we conclude that it will take a minimum of 2 days 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 dfs to conduct the depth-first search. dfs is invoked for every land cell (1) and marks all reachable land cells as part of the same island by setting them to 2.
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 count function 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 2 back to 1 to 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.

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 walk through a small example to illustrate the solution approach.

Suppose we have the following 2D grid:

1 1 0
1 0 1
0 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 count function to check if the grid is already disconnected. In our case, since there's only one island, the count function will return 1. 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 the count function:
```
0 1 0
1 0 1
0 1 1
```
The count returns 2 which 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 need 1 day 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.

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
66

1class 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}
77

1class 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};
75

1// 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}
80

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.

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

Question 1 out of 10

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don’t know