We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Days to Disconnect Island

Number: 1691

Difficulty: Hard

Paid? No

Companies: Amazon, Meta

Problem Description

Given an m x n binary grid where 1 represents land and 0 represents water, an island is defined as a maximal 4-directionally connected group of 1's. The grid is "connected" if there is exactly one island; otherwise, it is "disconnected". In one day, you can convert a single land cell into water. The task is to return the minimum number of days required to disconnect the grid.

Key Insights

  • First, determine if the grid is already disconnected by counting islands using DFS/BFS.
  • If there is not exactly one island, return 0 (either already disconnected or completely water).
  • For a grid with exactly one island, simulate the removal of each land cell one by one. For each removal, check if the island becomes disconnected.
  • If any removal causes a disconnection, return 1.
  • If no single removal disconnects the island, then the answer must be 2.
  • Using DFS/BFS allows you to explore connected components efficiently.

Space and Time Complexity

Time Complexity: O((m * n)^2) in the worst-case scenario, as for each cell removal, a full DFS/BFS traversal (O(m * n)) is done. Space Complexity: O(m * n) due to recursion/auxiliary space for DFS/BFS and the visited tracking.

Solution

The solution begins by performing a DFS (or BFS) to count the number of islands in the grid. If the grid is already disconnected (i.e., the number of islands is not 1), return 0. Next, iterate over every land cell and temporarily change it to water. For each modified grid, perform another DFS/BFS to see if the connected component is broken. If you find a removal that leads to a disconnected grid, return 1. If none of the single removals disconnect the island, then return 2. This works because in the worst case, two removals are sufficient to disconnect the island.

Code Solutions

# Python solution with DFS

def minDays(grid):
    m, n = len(grid), len(grid[0])
    # Directions for moving up, down, left, right
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # DFS function to mark the connected land cells
    def dfs(i, j, visited):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0 or (i, j) in visited:
            return
        visited.add((i, j))
        for di, dj in directions:
            dfs(i + di, j + dj, visited)
    
    # Function to count islands using DFS
    def countIslands():
        visited = set()
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and (i, j) not in visited:
                    dfs(i, j, visited)
                    count += 1
        return count

    # If the grid is already disconnected, return 0.
    if countIslands() != 1:
        return 0

    # Try removing one land cell at a time to check if disconnecting the grid is possible.
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                grid[i][j] = 0  # Remove the cell
                if countIslands() != 1:
                    return 1
                grid[i][j] = 1  # Revert the change

    return 2

# Example usage:
grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
print(minDays(grid))
← Back to All Questions