1568. Minimum Number of Days to Disconnect Island

leetcode

Problem

Given a 2D grid consists of 0s (water) and 1s (land), an island is a maximal 4-directionally (horizontal or vertical) connected group of 1s. The grid is said to be connected if we have exactly one island, otherwise, it is disconnected. We want to find the minimum number of days to disconnect the island.

Example:

1 1 0 1 1
1 1 0 1 1
0 0 1 0 0

Output: 2

Solution Description

To implement the solution, we need to approach it with the following steps:

Identify if the island is already disconnected: If the grid has more than one island initially, return 0.
Simulate removal of one land cell: Iterate through each land cell in the grid, temporarily remove it, and check if the resulting grid is disconnected.
Simulate removal of two land cells: If removing one cell does not disconnect the island, check by removing a pair of cells and see if that results in disconnection.
Return the minimum days required: Since the grid size is small, the solution can afford to perform these checks efficiently.

We will use Depth-First Search (DFS) to count the number of connected components in the grid upon each removal simulation. The time complexity of this approach will be O(n*m*(n*m)) and the space complexity is O(n*m), where n and m are the dimensions of the grid.

Example

Grid:

[[1, 1, 0, 1, 1],
 [1, 1, 0, 1, 1],
 [0, 0, 1, 0, 0]]

Start by checking initial connectivity: One island or multiple islands? => One island.
Try removing each cell and check connectivity with DFS.
If not disconnected, try pairs of cells and check again.
Return the number of days based on the minimum attempts required.

References

The solution can be built using DFS to verify the connected components at each step.

Solution

/**
 * Main solution function to determine the minimum number of days to disconnect the island.
 * @param {number[][]} grid - The 2D grid of 0s and 1s.
 * @return {number} - Minimum number of days to disconnect the island.
 */
function minimumDaysToDisconnect(grid) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger!== 'undefined' ? () => {} : console.table;

    console.log();

    // Temporarily return a dummy value.
    return -1;
}

// Test cases
const testCases = [
    { grid: [[1, 1, 0, 1, 1], [1, 1, 0, 1, 1], [0, 0, 1, 0, 0]], expected: 2 },
    { grid: [[1, 1]], expected: 0 },
    { grid: [[1, 0, 1]], expected: 0 },
    { grid: [[1, 1, 0, 0, 1]], expected: 1 },
    { grid: [[0, 0]], expected: 0 },
];

testCases.forEach((test, index) => {
    const result = minimumDaysToDisconnect(test.grid);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});