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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Days to Disconnect Island

Difficulty: Hard

Problem Description

You are given an m x n binary grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1's. The grid is said to be connected if we have exactly one island; otherwise, it is said to be disconnected. In one day, we are allowed to change any single land cell (1) into a water cell (0). Return the minimum number of days to disconnect the grid.

Key Insights

  • An island is defined as a group of connected land cells (1's).
  • The goal is to ensure that the grid has more than one island, which is achieved by converting specific land cells to water cells.
  • If the grid already has no land (all cells are water), it's already disconnected.
  • The minimum number of days required to disconnect the grid can vary based on the initial configuration of land cells.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve the problem, we can utilize Depth-First Search (DFS) to traverse the grid and count the number of islands. The approach is as follows:

  1. Count the number of islands in the grid using DFS. If there are already 0 or 2 or more islands, we return 0 or 1 days respectively.
  2. If there is exactly 1 island, we need to check the configurations:
    • If the island consists of only one cell, it will take 1 day to disconnect.
    • If the island consists of more than one cell, we can disconnect it in 2 days by strategically turning two land cells into water cells.

The algorithm checks for connected components in the grid while keeping track of the number of islands.

Code Solutions

def minDays(grid):
    def dfs(r, c):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0:
            return
        grid[r][c] = 0
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    islands = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                dfs(r, c)
                islands += 1

    if islands == 0:
        return 0
    if islands > 1:
        return 0
    return 1 if sum(row.count(1) for row in grid) == 1 else 2
← Back to All Questions