Making A Large Island

Problem statement

You have an n × n binary grid (1 = land, 0 = water). You may change at most one 0 into a 1. After that optional flip, return the size of the largest connected island (four-direction connectivity). If the grid is already all land, return n².

Example:

Input:

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

Expected output:

3

Why: flipping either 0 joins the two lands into an island of size 3.

Practice on LeetCode: Making A Large Island

Golang Solution

  1. DFS-label every island with a unique id (≥ 2) and record its size.
  2. For each water cell, look at distinct neighboring island ids, sum those sizes, add 1 for the flipped cell, and track the maximum.
  3. If there was no water, the answer is already the biggest labeled island (the full grid).

Time: O(n²) — labeling and the flip scan each visit every cell a constant number of times
Space: O(n²) — recursion / maps in the worst case (grid is mutated in place for labels)

func largestIsland(grid [][]int) int {
	n := len(grid)

	// islandSize[id] = number of cells in that island
	islandSize := make(map[int]int)

	id := 2

	// Step 1: Label every island with a unique ID
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				size := dfs(grid, i, j, id)
				islandSize[id] = size
				id++
			}
		}
	}

	// If there was no water, the whole grid is already one island.
	maxIsland := 0

	for _, size := range islandSize {
		if size > maxIsland {
			maxIsland = size
		}
	}

	// Step 2: Try converting every 0 into 1
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {

			if grid[i][j] != 0 {
				continue
			}

			// Store neighboring island IDs so we don't
			// count the same island twice.
			seen := make(map[int]bool)

			size := 1 // The current 0 becomes land.

			for _, dir := range directions {
				ni := i + dir[0]
				nj := j + dir[1]

				if ni < 0 || ni >= n || nj < 0 || nj >= n {
					continue
				}

				neighborID := grid[ni][nj]

				if neighborID > 1 && !seen[neighborID] {
					size += islandSize[neighborID]
					seen[neighborID] = true
				}
			}

			if size > maxIsland {
				maxIsland = size
			}
		}
	}

	return maxIsland
}

var directions = [][]int{
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1},
}

func dfs(grid [][]int, i, j, id int) int {
	n := len(grid)

	// Boundary check
	if i < 0 || i >= n || j < 0 || j >= n {
		return 0
	}

	// Only visit cells belonging to this island.
	if grid[i][j] != 1 {
		return 0
	}

	// Mark this cell with the island ID.
	grid[i][j] = id

	size := 1

	for _, dir := range directions {
		ni := i + dir[0]
		nj := j + dir[1]

		size += dfs(grid, ni, nj, id)
	}

	return size
}