Minimum Number Of Days To Disconnect Island - Leetcode Solution

Problem Statement: Given a 2D grid consisting of 1s (land) and 0s (water). An island is a maximal 4-directionally connected group of 1s. The grid is said to be connected if we have exactly one island, otherwise is said disconnected. In one day, we are allowed to disconnect any single island by replacing any single 1 with 0. Return the minimum number of days to disconnect the island.

Solution approach: We can start with identifying the island by doing a DFS/BFS for finding consecutive 1 values and counting them as one island. After finding the island, we can iterate over each 1 within the island and try to remove it one by one and check if the island is still connected or not. To check this, we can again use the DFS/BFS approach to see if we have only one island after removing the 1. We will keep doing this process and keep track of the minimum number of days required to disconnect the island.

Solution Algorithm:

1. Start with iterating over the grid and when we encounter a 1, start DFS/BFS from that point and mark all the connected 1s as a single island.
2. Count the number of islands we found, if it is greater than 1, the grid is disconnected, so we return 0 as we don't need to do anything.
3. If there is only one island, we can start iterating over each 1 within the island and try to remove it and check if the island is still connected.
4. For checking connectivity, we will again use DFS/BFS.
5. We will keep track of the minimum number of days required to disconnect the island and keep removing the 1s one by one until we have a disconnected island.
6. Return the minimum number of days.

Pseudo Code: def dfs(grid, x, y, visited): # DFS for marking connected 1s as single island # Mark the current node as visited visited[x][y] = True # Check for all 4 directions for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nx, ny = x + dx, y + dy if not (0 <= nx < len(grid)) or not (0 <= ny < len(grid[0])): # Out of grid range continue if grid[nx][ny] == 0 or visited[nx][ny]: # Not a land cell or already visited continue dfs(grid, nx, ny, visited)

def minDays(grid: List[List[int]]) -> int: # Initialize variables rows, cols = len(grid), len(grid[0]) visited = [[False] * cols for _ in range(rows)] islands = 0 # Find connected components to identify island for i in range(rows): for j in range(cols): if grid[i][j] == 1 and not visited[i][j]: # Start DFS/BFS from this node dfs(grid, i, j, visited) islands += 1

# If the number of islands is greater than 1, return 0 as the grid is disconnected
if islands != 1:
    return 0

# Loop over each 1 in the grid and try to remove it and check if the island is still connected
for i in range(rows):
    for j in range(cols):
        if grid[i][j] == 1:
            grid[i][j] = 0
            visited = [[False] * cols for _ in range(rows)]
            islands = 0
            # Find connected components to identify island
            for x in range(rows):
                for y in range(cols):
                    if grid[x][y] == 1 and not visited[x][y]:
                        # Start DFS/BFS from this node
                        dfs(grid, x, y, visited)
                        islands += 1

            # If the number of islands is greater than 1, we have disconnected the island
            if islands != 1:
                return 1

            # If the island is still connected, try removing another 1
            grid[i][j] = 1

# All 1s can be removed one by one, so the island can be disconnected in this many days
return 2    

Time complexity: The dfs function for marking connected 1s is O(rows x cols). The overall algorithm is O(rows x cols x 4 x rows x cols) as we are iterating over the grid and DFS for each cell can take up to rows x cols time. So, the overall time complexity is O(rows^3 x cols^3).

Space complexity: We are using extra space for visited list and the function call stack for DFS. The space complexity is O(rows x cols).

1