Largest Island

Tags

Largest Island

Category

Graphs

Difficulty

Hard

Problem Statement

Given a binary matrix where 1 represents land and 0 represents water, find the size of the largest island you can create by changing at most one 0 to a 1. An island is a group of 1s connected 4-directionally (up, down, left, right).

Intuition

Rather than flipping each 0 and running a full BFS/DFS to measure the resulting island (O(n^2) per flip, O(n^4) total), we can precompute island sizes. First, label each connected component with a unique ID and record its size. Then, for each 0 cell, look at the IDs of its 4-directional neighbors, sum the sizes of the distinct neighboring islands, and add 1 (for the flipped cell itself). The largest such sum is the answer.

Approach

  1. Traverse the grid. For each unvisited land cell, run BFS/DFS to label the entire connected component with a unique islandId and compute its size. Store sizes in a map islandId -> size.
  2. For each water cell (r, c):
    • Collect the unique island IDs from its 4 neighbors.
    • Sum their sizes and add 1.
    • Track the maximum.
  3. If there are no water cells, the answer is the total grid size (the entire grid is one island).
  4. Return the maximum.

Pseudocode

function largestIsland(grid):
    rows = length(grid)
    cols = length(grid[0])
    islandId = 2     // start labeling from 2 to avoid confusion with 0 and 1
    sizeMap = {}

    // Step 1: Label islands
    for r from 0 to rows-1:
        for c from 0 to cols-1:
            if grid[r][c] == 1:
                size = bfs(grid, r, c, islandId)
                sizeMap[islandId] = size
                islandId += 1

    // Step 2: Evaluate each 0-cell flip
    maxSize = max value in sizeMap (or 0)
    for r from 0 to rows-1:
        for c from 0 to cols-1:
            if grid[r][c] == 0:
                neighborIds = set()
                for (nr, nc) in 4-directional neighbors of (r, c):
                    if inBounds(nr, nc) and grid[nr][nc] > 1:
                        neighborIds.add(grid[nr][nc])
                total = 1 + sum(sizeMap[id] for id in neighborIds)
                maxSize = max(maxSize, total)

    return maxSize

function bfs(grid, r, c, id):
    queue = [(r, c)]
    grid[r][c] = id
    size = 0
    while queue not empty:
        (cr, cc) = queue.dequeue()
        size += 1
        for (nr, nc) in 4-directional neighbors:
            if inBounds(nr, nc) and grid[nr][nc] == 1:
                grid[nr][nc] = id
                queue.enqueue((nr, nc))
    return size

Time & Space Complexity

MeasureComplexityJustification
TimeO(R * C)Each cell is visited once during labeling and once during evaluation
SpaceO(R * C)For the BFS queue and the size map (in the worst case, many small islands)

Key Insights

  • Labeling islands in-place (overwriting 1s with island IDs starting from 2) avoids needing a separate visited matrix.
  • Using a set for neighbor IDs prevents double-counting when two neighbors belong to the same island.
  • If the grid is entirely land, no 0 exists to flip — the answer is R * C.
  • This problem is also known as Making A Large Island (LeetCode 827).

Edge Cases

  • All 1s: no water to flip; answer is the total grid size.
  • All 0s: flipping one cell creates an island of size 1.
  • Single cell grid: if 0, answer is 1; if 1, answer is 1.
  • Flipping a 0 that bridges two large islands: the algorithm correctly sums both island sizes plus 1.
  • Multiple neighbors from the same island: the set deduplication prevents overcounting.

Linked mentions