Jobs

Interviews

Discussions

Minimum Number of Days to Disconnect Island

Hard

Asked by:

10 views

Topics:

Graphs

You are given an m x n binary grid 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 is said 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.

Example 1:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.

Example 2:

Input: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] is either 0 or 1.

Try coding it in LeetCode

Minimum Number of Days to Disconnect Island

Hard

Asked by:

10 views

Topics:

Graphs

You are given an m x n binary grid 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 is said 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.

Example 1:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.

Example 2:

Input: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] is either 0 or 1.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what are the maximum possible values for rows and columns?
Can the grid contain any values other than 0 and 1, representing water and land respectively?
If the island is already disconnected (e.g., the grid is all water or empty), what should I return?
Is there guaranteed to be at least one land cell in the grid to begin with, or could it be all water?
If multiple solutions exist (multiple sets of removals disconnect the island in the minimum number of days), is any one of them acceptable?

Brute Force Solution

Approach

The brute force strategy involves checking every possible action we can take to disconnect the island. We try removing each land cell, one at a time, and see if that disconnects the island. If not, we try removing pairs of land cells, one at a time, to see if that disconnects the island.

Here's how the algorithm would work step-by-step:

First, determine if the initial grid represents a connected island. If not, we already know the answer is zero because the island is already disconnected.
Next, go through each land cell one at a time. For each cell, temporarily remove it from the grid.
After removing each land cell, check if the remaining land cells form a disconnected island (meaning the island has now been split into two or more separate islands).
If removing a single land cell disconnects the island, then the answer is one, and we're done. Return one.
If no single land cell removal disconnects the island, then we go through every possible pair of land cells.
For each pair, temporarily remove both cells from the grid.
Check if the remaining land cells now form a disconnected island.
If removing any pair disconnects the island, then the answer is two, and we're done. Return two.
If after checking every single land cell and every pair of land cells, we still haven't disconnected the island, then we would need to remove more than two cells which isn't an option, and it is always possible to disconnect an island by removing any two land cells if the initial island was initially connected, thus the answer would be 2.
The maximum number of land cells that must be removed to disconnect the island is at most 2, as the problem constraints specify.

Code Implementation

def min_days_to_disconnect(grid):
    rows = len(grid)
    cols = len(grid[0])

    def count_islands(current_grid):
        visited = set()
        island_count = 0

        def dfs(row, col):
            if (row < 0 or row >= rows or col < 0 or col >= cols or
                (row, col) in visited or current_grid[row][col] == 0):
                return

            visited.add((row, col))
            dfs(row + 1, col)
            dfs(row - 1, col)
            dfs(row, col + 1)
            dfs(row, col - 1)

        for row in range(rows):
            for col in range(cols):
                if current_grid[row][col] == 1 and (row, col) not in visited:
                    dfs(row, col)
                    island_count += 1

        return island_count

    initial_islands = count_islands(grid)
    if initial_islands != 1:
        return 0

    land_cells = []
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                land_cells.append((row, col))

    # Check removing one land cell
    for row_to_remove, col_to_remove in land_cells:
        temp_grid = [row[:] for row in grid]
        temp_grid[row_to_remove][col_to_remove] = 0
        if count_islands(temp_grid) != 1:
            return 1

    # Check removing two land cells
    for i in range(len(land_cells)):
        for j in range(i + 1, len(land_cells)):
            first_row_remove, first_col_remove = land_cells[i]
            second_row_remove, second_col_remove = land_cells[j]

            temp_grid = [row[:] for row in grid]
            temp_grid[first_row_remove][first_col_remove] = 0
            temp_grid[second_row_remove][second_col_remove] = 0
            if count_islands(temp_grid) != 1:
                return 2

    # If no single or double removal disconnects, return 2
    return 2

Big(O) Analysis

Time Complexity

O(n^4) – Let n be the number of cells in the grid. The algorithm first checks if the initial grid is connected, which can be done in O(n) time using Depth First Search (DFS) or Breadth First Search (BFS). Then, it iterates through each land cell (at most n), temporarily removing it and checking connectivity again using DFS/BFS in O(n) time. This gives O(n * n) complexity for single cell removals. Next, the algorithm iterates through all pairs of land cells (at most n^2 pairs), removing each pair and checking connectivity, again in O(n) time with DFS/BFS. Therefore, the overall time complexity is O(n * n) + O(n^2 * n), which simplifies to O(n^3). However, to find the land cells to begin with requires us to iterate through the grid. The grid is assumed to be a nxn grid for simplicity in this response (though the question has nothing that indicates this so this assumption is used for explaining the Big O), so the total complexity can be interpreted as O(n^4).

Space Complexity

O(N) – The algorithm utilizes a depth-first search (DFS) or breadth-first search (BFS) within the island connectivity check. This search employs a 'visited' set or matrix to keep track of explored cells, which in the worst case, could be the size of the entire grid (N), where N is the number of cells in the grid. Also, the implicit recursion stack, if DFS is implemented recursively, can grow up to the maximum depth of the grid size N in the worst-case scenario where all cells are connected. Thus, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The key is to recognize that we only need to disconnect the island, not find the absolute fewest moves. Therefore, we check for edge cases first, then use a clever connectivity test to determine the minimum days needed.

Here's how the algorithm would work step-by-step:

First, count the number of land cells in the grid. If there are zero or only one land cell, then it already takes zero days to disconnect the island, since it is already disconnected or doesn't exist.
Next, check if the island is already disconnected. If it is, then it takes zero days.
Now, check if removing just one land cell can disconnect the island. Try removing each land cell one at a time. After removing each land cell, check if the remaining grid is disconnected. If it is, return one day.
If removing any single land cell did not disconnect the island, we know it will take at least two days to disconnect the island, since we have to remove at least two land cells. Therefore, return two days.

Code Implementation

def minimum_days_to_disconnect_island(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    def count_islands(current_grid):
        number_of_islands = 0
        visited = set()

        def depth_first_search(row, column):
            if (row < 0 or row >= number_of_rows or
                column < 0 or column >= number_of_columns or
                (row, column) in visited or current_grid[row][column] == 0):
                return

            visited.add((row, column))
            depth_first_search(row + 1, column)
            depth_first_search(row - 1, column)
            depth_first_search(row, column + 1)
            depth_first_search(row, column - 1)

        for row in range(number_of_rows):
            for column in range(number_of_columns):
                if current_grid[row][column] == 1 and (row, column) not in visited:
                    depth_first_search(row, column)
                    number_of_islands += 1

        return number_of_islands

    number_of_land_cells = sum(sum(row) for row in grid)

    # Handle edge cases with zero or one land cell
    if number_of_land_cells <= 1:
        return 0

    # If island is already disconnected, return 0
    if count_islands(grid) != 1:
        return 0

    # Check if removing one land cell disconnects the island
    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1:
                temp_grid = [row[:] for row in grid]
                temp_grid[row][column] = 0

                # Count the number of islands after removal
                if count_islands(temp_grid) != 1:
                    return 1

    # If one removal doesn't disconnect, return 2
    return 2

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of rows and m be the number of columns in the grid. First, counting land cells takes O(n*m) time. Checking if the island is initially disconnected involves a depth-first search (DFS) or breadth-first search (BFS), which also takes O(n*m) time. The most expensive operation is iterating through each land cell, which at most could be n*m cells, and then performing another DFS/BFS after virtually removing the cell, which takes O(n*m) time for each removal. Therefore, the overall time complexity is O(n*m) * O(n*m) which simplifies to O((n*m)^2). However, we can improve this, instead of visiting every cell, we can just visit the land cells. The number of land cells are fewer than n*m, let this value be `k`. Visiting land cells now become k * O(n*m) which is still O((n*m)^2). However, since k <= n*m, in worst case the number of land cells is n*m. But, in best case there is only a constant number of land cells. Since the DFS operation is an upperbound for all operations, the time complexity can be stated to be at worst O(n*m).

Space Complexity

O(N) – The space complexity is determined by the connectivity check performed after potentially removing a land cell. This check often involves either Depth-First Search (DFS) or Breadth-First Search (BFS). In the worst-case scenario, these algorithms will visit all land cells, requiring a visited set (or a modified grid) to track visited cells, which would grow linearly with the number of land cells. Since the number of land cells can be at most the number of cells in the grid, N, the auxiliary space becomes O(N) in the worst case, where N is the total number of cells in the grid (rows * cols).

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately, as there's no island to disconnect.
Grid with only one cell (1x1)	Return 1 if the cell is land (1), 0 otherwise, since removing it disconnects the (non-existent) island.
Grid with two cells, both representing land	Return 1, as removing either cell disconnects the island.
Grid represents a single connected island (no bridges needed)	Check if the island is already disconnected; if not, find articulation points and return 1 if found, or 2 if no articulation points exist.
Grid represents multiple disconnected islands	Return 0, since the island is already disconnected.
Large grid (potential stack overflow with DFS)	Use iterative DFS (stack-based) or BFS to avoid recursion depth limits.
Grid filled entirely with water (all 0s)	Return 0, as there's no island to disconnect.
Grid filled entirely with land (all 1s)	Check for articulation points; if none, return 2 (need to remove two land cells to disconnect).

Null or empty grid

How to Handle:

Return 0 immediately, as there's no island to disconnect.

Grid with only one cell (1x1)

How to Handle:

Return 1 if the cell is land (1), 0 otherwise, since removing it disconnects the (non-existent) island.

Grid with two cells, both representing land

How to Handle:

Return 1, as removing either cell disconnects the island.

Grid represents a single connected island (no bridges needed)

How to Handle:

Check if the island is already disconnected; if not, find articulation points and return 1 if found, or 2 if no articulation points exist.

Grid represents multiple disconnected islands

How to Handle:

Return 0, since the island is already disconnected.

Large grid (potential stack overflow with DFS)

How to Handle:

Use iterative DFS (stack-based) or BFS to avoid recursion depth limits.

Grid filled entirely with water (all 0s)

How to Handle:

Return 0, as there's no island to disconnect.

Grid filled entirely with land (all 1s)

How to Handle:

Check for articulation points; if none, return 2 (need to remove two land cells to disconnect).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what are the maximum possible values for rows and columns?
Can the grid contain any values other than 0 and 1, representing water and land respectively?
If the island is already disconnected (e.g., the grid is all water or empty), what should I return?
Is there guaranteed to be at least one land cell in the grid to begin with, or could it be all water?
If multiple solutions exist (multiple sets of removals disconnect the island in the minimum number of days), is any one of them acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, determine if the initial grid represents a connected island. If not, we already know the answer is zero because the island is already disconnected.
Next, go through each land cell one at a time. For each cell, temporarily remove it from the grid.
After removing each land cell, check if the remaining land cells form a disconnected island (meaning the island has now been split into two or more separate islands).
If removing a single land cell disconnects the island, then the answer is one, and we're done. Return one.
If no single land cell removal disconnects the island, then we go through every possible pair of land cells.
For each pair, temporarily remove both cells from the grid.
Check if the remaining land cells now form a disconnected island.
If removing any pair disconnects the island, then the answer is two, and we're done. Return two.
If after checking every single land cell and every pair of land cells, we still haven't disconnected the island, then we would need to remove more than two cells which isn't an option, and it is always possible to disconnect an island by removing any two land cells if the initial island was initially connected, thus the answer would be 2.
The maximum number of land cells that must be removed to disconnect the island is at most 2, as the problem constraints specify.

Code Implementation

def min_days_to_disconnect(grid):
    rows = len(grid)
    cols = len(grid[0])

    def count_islands(current_grid):
        visited = set()
        island_count = 0

        def dfs(row, col):
            if (row < 0 or row >= rows or col < 0 or col >= cols or
                (row, col) in visited or current_grid[row][col] == 0):
                return

            visited.add((row, col))
            dfs(row + 1, col)
            dfs(row - 1, col)
            dfs(row, col + 1)
            dfs(row, col - 1)

        for row in range(rows):
            for col in range(cols):
                if current_grid[row][col] == 1 and (row, col) not in visited:
                    dfs(row, col)
                    island_count += 1

        return island_count

    initial_islands = count_islands(grid)
    if initial_islands != 1:
        return 0

    land_cells = []
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                land_cells.append((row, col))

    # Check removing one land cell
    for row_to_remove, col_to_remove in land_cells:
        temp_grid = [row[:] for row in grid]
        temp_grid[row_to_remove][col_to_remove] = 0
        if count_islands(temp_grid) != 1:
            return 1

    # Check removing two land cells
    for i in range(len(land_cells)):
        for j in range(i + 1, len(land_cells)):
            first_row_remove, first_col_remove = land_cells[i]
            second_row_remove, second_col_remove = land_cells[j]

            temp_grid = [row[:] for row in grid]
            temp_grid[first_row_remove][first_col_remove] = 0
            temp_grid[second_row_remove][second_col_remove] = 0
            if count_islands(temp_grid) != 1:
                return 2

    # If no single or double removal disconnects, return 2
    return 2

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count the number of land cells in the grid. If there are zero or only one land cell, then it already takes zero days to disconnect the island, since it is already disconnected or doesn't exist.
Next, check if the island is already disconnected. If it is, then it takes zero days.
Now, check if removing just one land cell can disconnect the island. Try removing each land cell one at a time. After removing each land cell, check if the remaining grid is disconnected. If it is, return one day.
If removing any single land cell did not disconnect the island, we know it will take at least two days to disconnect the island, since we have to remove at least two land cells. Therefore, return two days.

Code Implementation

def minimum_days_to_disconnect_island(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])

    def count_islands(current_grid):
        number_of_islands = 0
        visited = set()

        def depth_first_search(row, column):
            if (row < 0 or row >= number_of_rows or
                column < 0 or column >= number_of_columns or
                (row, column) in visited or current_grid[row][column] == 0):
                return

            visited.add((row, column))
            depth_first_search(row + 1, column)
            depth_first_search(row - 1, column)
            depth_first_search(row, column + 1)
            depth_first_search(row, column - 1)

        for row in range(number_of_rows):
            for column in range(number_of_columns):
                if current_grid[row][column] == 1 and (row, column) not in visited:
                    depth_first_search(row, column)
                    number_of_islands += 1

        return number_of_islands

    number_of_land_cells = sum(sum(row) for row in grid)

    # Handle edge cases with zero or one land cell
    if number_of_land_cells <= 1:
        return 0

    # If island is already disconnected, return 0
    if count_islands(grid) != 1:
        return 0

    # Check if removing one land cell disconnects the island
    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1:
                temp_grid = [row[:] for row in grid]
                temp_grid[row][column] = 0

                # Count the number of islands after removal
                if count_islands(temp_grid) != 1:
                    return 1

    # If one removal doesn't disconnect, return 2
    return 2

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately, as there's no island to disconnect.
Grid with only one cell (1x1)	Return 1 if the cell is land (1), 0 otherwise, since removing it disconnects the (non-existent) island.
Grid with two cells, both representing land	Return 1, as removing either cell disconnects the island.
Grid represents a single connected island (no bridges needed)	Check if the island is already disconnected; if not, find articulation points and return 1 if found, or 2 if no articulation points exist.
Grid represents multiple disconnected islands	Return 0, since the island is already disconnected.
Large grid (potential stack overflow with DFS)	Use iterative DFS (stack-based) or BFS to avoid recursion depth limits.
Grid filled entirely with water (all 0s)	Return 0, as there's no island to disconnect.
Grid filled entirely with land (all 1s)	Check for articulation points; if none, return 2 (need to remove two land cells to disconnect).

Null or empty grid

How to Handle:

Return 0 immediately, as there's no island to disconnect.

Grid with only one cell (1x1)

How to Handle:

Return 1 if the cell is land (1), 0 otherwise, since removing it disconnects the (non-existent) island.

Grid with two cells, both representing land

How to Handle:

Return 1, as removing either cell disconnects the island.

Grid represents a single connected island (no bridges needed)

How to Handle:

Check if the island is already disconnected; if not, find articulation points and return 1 if found, or 2 if no articulation points exist.

Grid represents multiple disconnected islands

How to Handle:

Return 0, since the island is already disconnected.

Large grid (potential stack overflow with DFS)

How to Handle:

Use iterative DFS (stack-based) or BFS to avoid recursion depth limits.

Grid filled entirely with water (all 0s)

How to Handle:

Return 0, as there's no island to disconnect.

Grid filled entirely with land (all 1s)

How to Handle:

Check for articulation points; if none, return 2 (need to remove two land cells to disconnect).