DSA Tracker

Visualize

Minimum Number of Days to Disconnect Island

Model the island as a graph, then try removing one land cell at a time

time O((m * n)^2)space O(m * n)

Turn the grid into a graph first: one node per land cell, one edge between every pair of orthogonally adjacent land cells. Disconnecting the island is now just about REMOVING NODES from that graph. It only ever takes at most 2 removals to disconnect any grid island, so the whole problem collapses into three checks in increasing order: is it already not one piece (0)? Does removing any single cell split it (1)? If neither, the answer is 2. This 2x2 block of land is a 4-node cycle, where every node has exactly two neighbours — the textbook case where one removal is never enough.

Details

Animated on: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]] — each day one land cell (1) can be turned to water (0). What is the minimum number of days until the land is no longer a single connected island?

Problem:Minimum Number of Days to Disconnect IslandHard

Model the island as a graph, then try removing one land cell at a time

step 1 / 8

The island as a graph

Each land cell becomes a node; an edge joins two nodes only when their grid cells are orthogonally adjacent. This 2x2 block of land turns into a 4-node cycle — every cell has exactly two neighbours, which is exactly the shape that resists being split by removing just one of them.

Pseudocode
1FUNCTION minDays(grid):
2  comps <- COUNT_COMPONENTS(grid, NONE)
3  IF comps != 1
4    RETURN 0
5  FOR EACH land cell (r, c) IN grid
6    comps <- COUNT_COMPONENTS(grid, REMOVE (r, c))
7    IF comps = 1
8      CONTINUE
9    RETURN 1
10  RETURN 2

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Each land cell becomes a node; an edge joins two nodes only when their grid cells are orthogonally adjacent. This 2x2 block of land turns into a 4-node cycle — every cell has exactly two neighbours, which is exactly the shape that resists being split by removing just one of them.
  2. A single BFS starting at 0-1 reaches all 4 land cells, so COUNT_COMPONENTS(grid, NONE) = 1. That count is already 1 — an island in one piece is not the disconnected state we're looking for, so day 0 cannot be the answer and we must start removing cells.
  3. Turning 0-1 to water still leaves one connected piece of 3 cells (0-2, 1-2, 1-1) — its two remaining neighbours in the cycle still link up, so this single cell cannot be the answer.
  4. Turning 0-2 to water still leaves one connected piece of 3 cells (0-1, 1-1, 1-2) — its two remaining neighbours in the cycle still link up, so this single cell cannot be the answer.
  5. Turning 1-1 to water still leaves one connected piece of 3 cells (0-1, 0-2, 1-2) — its two remaining neighbours in the cycle still link up, so this single cell cannot be the answer.
  6. Turning 1-2 to water still leaves one connected piece of 3 cells (0-1, 1-1, 0-2) — its two remaining neighbours in the cycle still link up, so this single cell cannot be the answer.
  7. All 4 land cells were tried alone and every single one left the rest connected. This problem's own bound says the answer is never more than 2 — removing any two non-adjacent-through-nothing-else cells finishes the job — so with day 1 ruled out, RETURN 2.
  8. As proof: removing the two opposite corners 0-1 and 1-2 together (they share no edge, so nothing connects them) leaves {0-2} and {1-1} — 2 disconnected pieces from just 2 removals, confirming the answer.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Number of Days to Disconnect Island in the editorAll Graph problemsBack to roadmap