Minimum Number of Days to Disconnect Island

2 min readUpdated 17 June 2025

Problem Statement

In this problem, you're presented with a binary grid where the value 1 indicates land and the value 0 indicates water. We define an island as a group of adjacent land cells connected either horizontally or vertically. The grid is considered connected if there is exactly one such group of 1s forming a single island.

Your task is to determine the minimum number of days required to turn this connected island grid into a disconnected one. On each day, you can change one land cell (1) into a water cell (0). The grid is deemed disconnected when there are either no islands left or multiple disconnected islands.

Examples

Example 1

Input:

EXAMPLE_ENTITY

grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

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:

EXAMPLE_ENTITY

grid = [[1,1]]

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

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.

Approach and Intuition

To tackle this problem, consider a few key observations:

Immediate Disconnections: If the grid itself starts with no 1s or distinct naturally disconnected islands, it's already in a disconnected state requiring zero days.
Single Changes: For grids that have connected islands, investigate how making single changes in strategic locations might disconnect the island. Often, changing a cell on a thin bridge between two larger parts of an island might be enough.
Grid Edges and Corners: Generally, islands touching the grid borders need careful examination since changes here might have a deeper impact on connectivity due to fewer neighboring cells.
Minimum Cuts: Think in terms of graph theory where islands are interconnected nodes. Your task might reduce to finding the minimum "cut" in this connectivity, essentially how to remove the least nodes (or cells, in this context) to break apart the island.
Computational Bounds: Given the grid’s maximum dimensions (30x30), solutions involving examining each cell multiple times (like BFS/DFS for each cell) are computationally feasible.

Based on these observations, a plausible approach could involve:

Using depth-first search (DFS) or breadth-first search (BFS) to identify the exact structure and connections of the current island.
Identifying critical points or bridges within the island—cells whose removal leads to a disconnected state.
Iteratively simulate the removal of each potentially critical cell to see if it results in a split, thereby counting the minimum number of days required.

In essence, the challenge involves transforming a connected physical structure into a disconnected one by strategically removing minimal structural components (land cells). Understanding and manipulating the connectivity efficiently is key to solving the problem optimally.

Solutions

CPP
class GridAnalysis {
private:
    // Directions: right, down, left, up
    const vector<vector<int>> MOVE_SET = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    struct CriticalPointDetails {
        bool foundCriticalPoint;
        int visitTime;
    
        CriticalPointDetails(bool found, int time)
            : foundCriticalPoint(found), visitTime(time) {}
    };
    
public:
    int disconnectDays(vector<vector<int>>& matrix) {
        int rowCount = matrix.size(), colCount = matrix[0].size();
        CriticalPointDetails critPoint(false, 0);
        int totalLand = 0, numIslands = 0;
    
        // Visitation and ancestry tracking for DFS
        vector<vector<int>> visitTimestamp(
            rowCount,
            vector<int>(colCount, -1));
        vector<vector<int>> lowEndpoint(
            rowCount,
            vector<int>(colCount, -1));
        vector<vector<int>> dfsParent(
            rowCount, vector<int>(colCount, -1));
    
        // Explore the matrix for connectivity and critical points
        for (int r = 0; r < rowCount; r++) {
            for (int c = 0; c < colCount; c++) {
                if (matrix[r][c] == 1) {
                    totalLand++;
                    if (visitTimestamp[r][c] == -1) {
                        exploreCriticalPoints(matrix, r, c, visitTimestamp,
                                              lowEndpoint, dfsParent, critPoint);
                        numIslands++;
                    }
                }
            }
        }
    
        // Evaluate disconnection scenario
        if (numIslands == 0 || numIslands > 1)
            return 0;
        if (totalLand == 1) return 1;
        if (critPoint.foundCriticalPoint)
            return 1;
        return 2;
    }
    
private:
    void exploreCriticalPoints(vector<vector<int>>& matrix, int r, int c,
                               vector<vector<int>>& visitTimestamp,
                               vector<vector<int>>& lowEndpoint,
                               vector<vector<int>>& dfsParent,
                               CriticalPointDetails& critDetails) {
        int rowCount = matrix.size(), colCount = matrix[0].size();
        visitTimestamp[r][c] = critDetails.visitTime;
        critDetails.visitTime++;
        lowEndpoint[r][c] = visitTimestamp[r][c];
        int childCnt = 0;
    
        // Check adjacent cells
        for (const auto& move : MOVE_SET) {
            int nextR = r + move[0];
            int nextC = c + move[1];
            if (isLandCellValid(matrix, nextR, nextC)) {
                if (visitTimestamp[nextR][nextC] == -1) {
                    childCnt++;
                    dfsParent[nextR][nextC] = r * colCount + c;
                    exploreCriticalPoints(matrix, nextR, nextC, visitTimestamp,
                                          lowEndpoint, dfsParent, critDetails);
    
                    // Check and update low times
                    lowEndpoint[r][c] = min(lowEndpoint[r][c],
                                            lowEndpoint[nextR][nextC]);
    
                    // Articulation condition
                    if (lowEndpoint[nextR][nextC] >= visitTimestamp[r][c] &&
                        dfsParent[r][c] != -1) {
                        critDetails.foundCriticalPoint = true;
                    }
                } else if (nextR * colCount + nextC != dfsParent[r][c]) {
                    lowEndpoint[r][c] = min(lowEndpoint[r][c],
                                            visitTimestamp[nextR][nextC]);
                }
            }
        }
    
        // Root condition
        if (dfsParent[r][c] == -1 && childCnt > 1) {
            critDetails.foundCriticalPoint = true;
        }
    }
    
    // Validate land cell
    bool isLandCellValid(const vector<vector<int>>& matrix, int r, int c) {
        int rowCount = matrix.size(), colCount = matrix[0].size();
        return (r >= 0 && c >= 0 && r < rowCount && c < colCount &&
                matrix[r][c] == 1);
    }
};
Powered by Vultr AgentBeta

This solution explores how to determine the minimum number of days required to disconnect all land in a grid, where 1 represents land and 0 represents water. The implementation uses Depth-First Search (DFS) in C++ to analyze the number of disconnected sections or islands and to identify critical points or articulation points in the grid.

The main functionality is encapsulated in the disconnectDays method, which first calculates the total number of land cells and the number of initially disconnected islands. It employs a DFS approach to:

Track visitation times and low link values.
Identify articulation points that, if removed, increase the number of disconnected islands.

Key points of the implementation include:

Initialization: Arrays for visit timestamps, low endpoints, and DFS parent tracking are set up. These are critical for the DFS traversal and articulation point identification.
DFS Exploration: The exploreCriticalPoints helper method is invoked recursively to traverse the grid. Through this traversal, the method checks adjacent cells (right, down, left, up) for connectivity and updates low endpoints.
Articulation Point Check: During the DFS traversal, if a node meets certain conditions, it is marked as a critical point. This involves checking if any child node can connect to an ancestor node directly or through other children nodes.
Edge Cases Handling:
- If no islands exist or if there are multiple unconnected islands from the start, the function returns 0, as they are already disconnected or in isolation.
- If there is only one land cell (total land count is 1), disconnecting it necessitates removing it, which can be done in 1 day.
- If an articulation point exists (indicating a critical connection point among the land cells), the minimum days to disconnect the island are 1.
- Otherwise, if no articulation points exist in a connected mass of land, then at least 2 days are required, implying the need for more complex maneuvers to create disconnections.

This approach relies heavily on understanding the structure of the grid and uses classical graph theory techniques (like articulation points) efficiently in the context of a 2D matrix. The algorithm's correctness across various topographical complexities in the grid makes it robust and reliable for solving the given problem.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Minimum Number of Days to Disconnect Island

2 min readUpdated 17 June 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

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:

EXAMPLE_ENTITY

grid = [[1,1]]

Output:

EXAMPLE_ENTITY

Explanation:

EXAMPLE_ENTITY

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.

Approach and Intuition

To tackle this problem, consider a few key observations:

Immediate Disconnections: If the grid itself starts with no 1s or distinct naturally disconnected islands, it's already in a disconnected state requiring zero days.
Single Changes: For grids that have connected islands, investigate how making single changes in strategic locations might disconnect the island. Often, changing a cell on a thin bridge between two larger parts of an island might be enough.
Grid Edges and Corners: Generally, islands touching the grid borders need careful examination since changes here might have a deeper impact on connectivity due to fewer neighboring cells.
Minimum Cuts: Think in terms of graph theory where islands are interconnected nodes. Your task might reduce to finding the minimum "cut" in this connectivity, essentially how to remove the least nodes (or cells, in this context) to break apart the island.
Computational Bounds: Given the grid’s maximum dimensions (30x30), solutions involving examining each cell multiple times (like BFS/DFS for each cell) are computationally feasible.

Based on these observations, a plausible approach could involve:

Using depth-first search (DFS) or breadth-first search (BFS) to identify the exact structure and connections of the current island.
Identifying critical points or bridges within the island—cells whose removal leads to a disconnected state.
Iteratively simulate the removal of each potentially critical cell to see if it results in a split, thereby counting the minimum number of days required.

Solutions

CPP
class GridAnalysis {
private:
    // Directions: right, down, left, up
    const vector<vector<int>> MOVE_SET = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    struct CriticalPointDetails {
        bool foundCriticalPoint;
        int visitTime;
    
        CriticalPointDetails(bool found, int time)
            : foundCriticalPoint(found), visitTime(time) {}
    };
    
public:
    int disconnectDays(vector<vector<int>>& matrix) {
        int rowCount = matrix.size(), colCount = matrix[0].size();
        CriticalPointDetails critPoint(false, 0);
        int totalLand = 0, numIslands = 0;
    
        // Visitation and ancestry tracking for DFS
        vector<vector<int>> visitTimestamp(
            rowCount,
            vector<int>(colCount, -1));
        vector<vector<int>> lowEndpoint(
            rowCount,
            vector<int>(colCount, -1));
        vector<vector<int>> dfsParent(
            rowCount, vector<int>(colCount, -1));
    
        // Explore the matrix for connectivity and critical points
        for (int r = 0; r < rowCount; r++) {
            for (int c = 0; c < colCount; c++) {
                if (matrix[r][c] == 1) {
                    totalLand++;
                    if (visitTimestamp[r][c] == -1) {
                        exploreCriticalPoints(matrix, r, c, visitTimestamp,
                                              lowEndpoint, dfsParent, critPoint);
                        numIslands++;
                    }
                }
            }
        }
    
        // Evaluate disconnection scenario
        if (numIslands == 0 || numIslands > 1)
            return 0;
        if (totalLand == 1) return 1;
        if (critPoint.foundCriticalPoint)
            return 1;
        return 2;
    }
    
private:
    void exploreCriticalPoints(vector<vector<int>>& matrix, int r, int c,
                               vector<vector<int>>& visitTimestamp,
                               vector<vector<int>>& lowEndpoint,
                               vector<vector<int>>& dfsParent,
                               CriticalPointDetails& critDetails) {
        int rowCount = matrix.size(), colCount = matrix[0].size();
        visitTimestamp[r][c] = critDetails.visitTime;
        critDetails.visitTime++;
        lowEndpoint[r][c] = visitTimestamp[r][c];
        int childCnt = 0;
    
        // Check adjacent cells
        for (const auto& move : MOVE_SET) {
            int nextR = r + move[0];
            int nextC = c + move[1];
            if (isLandCellValid(matrix, nextR, nextC)) {
                if (visitTimestamp[nextR][nextC] == -1) {
                    childCnt++;
                    dfsParent[nextR][nextC] = r * colCount + c;
                    exploreCriticalPoints(matrix, nextR, nextC, visitTimestamp,
                                          lowEndpoint, dfsParent, critDetails);
    
                    // Check and update low times
                    lowEndpoint[r][c] = min(lowEndpoint[r][c],
                                            lowEndpoint[nextR][nextC]);
    
                    // Articulation condition
                    if (lowEndpoint[nextR][nextC] >= visitTimestamp[r][c] &&
                        dfsParent[r][c] != -1) {
                        critDetails.foundCriticalPoint = true;
                    }
                } else if (nextR * colCount + nextC != dfsParent[r][c]) {
                    lowEndpoint[r][c] = min(lowEndpoint[r][c],
                                            visitTimestamp[nextR][nextC]);
                }
            }
        }
    
        // Root condition
        if (dfsParent[r][c] == -1 && childCnt > 1) {
            critDetails.foundCriticalPoint = true;
        }
    }
    
    // Validate land cell
    bool isLandCellValid(const vector<vector<int>>& matrix, int r, int c) {
        int rowCount = matrix.size(), colCount = matrix[0].size();
        return (r >= 0 && c >= 0 && r < rowCount && c < colCount &&
                matrix[r][c] == 1);
    }
};
Powered by Vultr AgentBeta

Track visitation times and low link values.
Identify articulation points that, if removed, increase the number of disconnected islands.

Key points of the implementation include:

Initialization: Arrays for visit timestamps, low endpoints, and DFS parent tracking are set up. These are critical for the DFS traversal and articulation point identification.
DFS Exploration: The exploreCriticalPoints helper method is invoked recursively to traverse the grid. Through this traversal, the method checks adjacent cells (right, down, left, up) for connectivity and updates low endpoints.
Articulation Point Check: During the DFS traversal, if a node meets certain conditions, it is marked as a critical point. This involves checking if any child node can connect to an ancestor node directly or through other children nodes.
Edge Cases Handling:
- If no islands exist or if there are multiple unconnected islands from the start, the function returns 0, as they are already disconnected or in isolation.
- If there is only one land cell (total land count is 1), disconnecting it necessitates removing it, which can be done in 1 day.
- If an articulation point exists (indicating a critical connection point among the land cells), the minimum days to disconnect the island are 1.
- Otherwise, if no articulation points exist in a connected mass of land, then at least 2 days are required, implying the need for more complex maneuvers to create disconnections.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.