DSA Tracker

Visualize

Making A Large Island

Label every island once, then let each water cell add up its neighbours

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

Trying every flip and re-measuring its island from scratch is wasted work, because most flips reuse the same two or three islands over and over. Label each island once instead — a flood fill per unlabelled land cell, tagging every cell it reaches with that island's id — and store each island's area against its label. Now a water cell's best possible flip is arithmetic: look at its up-to-four land neighbours, collect the DISTINCT island labels among them (a cell can touch the same island twice through two different neighbours, and that must only count once), and add 1 for the cell itself to the sum of those islands' areas. The largest such sum, or the largest island already on the board if no flip helps, is the answer.

Details

Animated on: grid = [[1,1,0],[0,0,1],[0,1,1]] — flip exactly one water cell to land to make the largest possible island.

Problem:Making A Large IslandHard

Label every island once, then let each water cell add up its neighbours

step 1 / 11

3x3 grid, drawn as one vertex per cell

9 cells, 5 of them land. Exactly one water cell may flip to land — the question is which flip merges the most area, so every water cell's land neighbours matter, not just the islands on their own.

Pseudocode
1FUNCTION largestIsland(grid):
2  label <- 2
3  area <- EMPTY MAP
4  FOR EACH CELL (r, c) IN grid
5    IF grid[r][c] = 1 AND labelOf[r][c] = 0
6      area[label] <- FLOODFILL(r, c, label)
7      label <- label + 1
8  best <- MAX(area VALUES) OR 0
9  FOR EACH CELL (r, c) IN grid
10    IF grid[r][c] = 0
11      seen <- DISTINCT LABELS OF NEIGHBOURS(r, c)
12      best <- MAX(best, 1 + SUM(area[l] FOR l IN seen))
13  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 9 cells, 5 of them land. Exactly one water cell may flip to land — the question is which flip merges the most area, so every water cell's land neighbours matter, not just the islands on their own.
  2. (0,0) is land with no label yet, so start a flood fill from it and call this island 2.
  3. The fill claims (0,0), (0,1) — island 2 has area 2.
  4. (1,2) is land with no label yet, so start a flood fill from it and call this island 3.
  5. The fill claims (1,2), (2,2), (2,1) — island 3 has area 3.
  6. Every land cell is labelled. best-so-far — what we'd have with no flip at all — is the largest existing island, 3.
  7. (0,2) touches islands 3 and 2: flipping it gives 1 + 3 + 2 = 6. That is the new best.
  8. (1,0) touches island 2: flipping it gives 1 + 2 = 3. Not enough to beat 6.
  9. (1,1) touches islands 2 and 3: flipping it gives 1 + 2 + 3 = 6. Not enough to beat 6.
  10. (2,0) touches island 3: flipping it gives 1 + 3 = 4. Not enough to beat 6.
  11. Every water cell has been tried. The best possible island after exactly one flip is 6, reached by flipping (0,2) or (1,1). RETURN 6.

Now solve it yourself

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

Solve Making A Large Island in the editorAll Graph problemsBack to roadmap