Solving Rotting Oranges in Go: Step-by-Step Guide

Introduction to the Rotting Oranges Problem

The Rotting Oranges problem is a classic graph traversal challenge frequently encountered in coding interviews and competitive programming. It models a real-world propagation scenario: given a grid of oranges where some are fresh and some are rotten, every minute a rotten orange causes its adjacent (up, down, left, right) fresh oranges to rot. The goal is to determine the minimum number of minutes required until no fresh orange remains — or return -1 if it is impossible.

This problem is a textbook application of Breadth-First Search (BFS) because the rotting process spreads outward in layers, level by level, exactly like a wave expanding from multiple sources. In this tutorial, we will walk through solving it in Go from scratch, covering the intuition, the algorithm, the full implementation, edge cases, and best practices.

Understanding the Problem Statement

You are given an m x n grid where each cell can be one of three values:

• 0 — an empty cell
• 1 — a fresh orange
• 2 — a rotten orange

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. You must return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible (some fresh orange can never be reached), return -1.

Why This Problem Matters

Beyond being a popular interview question, the Rotting Oranges problem models many real-world phenomena: virus spread, information diffusion in networks, wildfire propagation, and multi-source shortest-path calculations. Mastering it teaches you how to:

• Apply BFS on a 2D grid
• Handle multi-source BFS efficiently
• Track levels (time steps) during traversal
• Reason about reachability and connected components

Choosing the Right Algorithm

A naive approach might simulate each minute by scanning the entire grid repeatedly, rotting adjacent fresh oranges. This works but runs in O(k * m * n) time where k is the number of minutes — inefficient for large grids.

The optimal approach uses multi-source BFS. Instead of starting from a single node, we enqueue all initially rotten oranges at once. We then process the queue level by level, where each level corresponds to one minute of elapsed time. This guarantees we visit every reachable fresh orange in the minimum possible time, with overall complexity of O(m * n).

Key Insight: Level-Order Traversal

The trick is to process the queue in "waves." At each wave, we process every orange currently in the queue (those that became rotten at the previous minute), and for each one, we rot its fresh neighbors and add them to the queue. The number of waves we perform equals the number of minutes elapsed.

Step-by-Step Algorithm

Here is the high-level plan before we write any code:

• Iterate over the grid to find all rotten oranges and count all fresh oranges.
• Enqueue all rotten oranges as the starting frontier of the BFS.
• If there are no fresh oranges, return 0 immediately.
• While the queue is not empty and fresh oranges remain, process one level of the queue.
• For each rotten orange in the current level, inspect its four neighbors.
• If a neighbor is a fresh orange, rot it, decrement the fresh count, and enqueue it.
• After processing a full level, increment the elapsed time.
• When the loop ends, if any fresh oranges remain, return -1; otherwise return the elapsed time.

Implementing the Solution in Go

Now let's translate the algorithm into idiomatic Go. We will define a function orangesRotting that takes a 2D integer slice and returns an integer.

package main

import "fmt"

func orangesRotting(grid [][]int) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])

    // Queue holds coordinates of rotten oranges.
    type cell struct{ r, c int }
    queue := make([]cell, 0)

    freshCount := 0

    // Step 1: Find all rotten oranges and count fresh ones.
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 2 {
                queue = append(queue, cell{r, c})
            } else if grid[r][c] == 1 {
                freshCount++
            }
        }
    }

    // No fresh oranges means zero minutes needed.
    if freshCount == 0 {
        return 0
    }

    // Four directional moves: up, down, left, right.
    directions := []cell{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    minutes := 0

    // Step 2: Multi-source BFS, level by level.
    for len(queue) > 0 {
        levelSize := len(queue)
        rottedThisLevel := false

        for i := 0; i < levelSize; i++ {
            current := queue[0]
            queue = queue[1:]

            for _, d := range directions {
                nr := current.r + d.r
                nc := current.c + d.c

                // Check bounds and whether the neighbor is fresh.
                if nr >= 0 && nr < rows &&
                    nc >= 0 && nc < cols &&
                    grid[nr][nc] == 1 {

                    grid[nr][nc] = 2
                    freshCount--
                    rottedThisLevel = true
                    queue = append(queue, cell{nr, nc})
                }
            }
        }

        // Only increment time if we actually rotted new oranges.
        if rottedThisLevel {
            minutes++
        }
    }

    // Step 3: If fresh oranges remain, they are unreachable.
    if freshCount > 0 {
        return -1
    }

    return minutes
}

func main() {
    grid := [][]int{
        {2, 1, 1},
        {1, 1, 0},
        {0, 1, 1},
    }

    result := orangesRotting(grid)
    fmt.Printf("Minutes until all oranges rot: %d\n", result)
}

When you run this program with the sample grid, the output will be Minutes until all oranges rot: 4. The rot spreads outward from the top-left rotten orange, taking four minutes to reach the bottom-right corner.

Tracing Through an Example

To build intuition, let's trace the algorithm on the grid above:

Initial state:
2 1 1
1 1 0
0 1 1

Minute 1:
2 2 1
2 1 0
0 1 1

Minute 2:
2 2 2
2 2 0
0 1 1

Minute 3:
2 2 2
2 2 0
0 2 1

Minute 4:
2 2 2
2 2 0
0 2 2

Notice how the rot expands in concentric rings from the original source. This layered expansion is exactly what BFS captures naturally, and each layer corresponds to one minute of elapsed time.

Handling Edge Cases

Robust code must account for several edge cases:

• Empty grid: Return 0 since there is nothing to rot.
• No fresh oranges: Return 0 immediately; no time is needed.
• No rotten oranges but fresh oranges exist: The BFS queue starts empty, the loop never runs, and freshCount remains positive, so we correctly return -1.
• Isolated fresh orange: If a fresh orange is surrounded by empty cells, it can never be reached, and the function returns -1.
• Single-cell grid: If the cell is 2 or 0, return 0; if it is 1, return -1.

Optimizing the Queue Implementation

In the implementation above, we used queue = queue[1:] to dequeue elements. This is simple but causes the underlying array to grow indefinitely because Go slices do not shrink their backing array. For large grids, this wastes memory.

A more efficient approach uses a head index instead of reslicing:

queue := make([]cell, 0, rows*cols)
head := 0

// Enqueue:
queue = append(queue, cell{r, c})

// Dequeue:
current := queue[head]
head++

// Loop condition:
for head < len(queue) {
    levelSize := len(queue) - head
    for i := 0; i < levelSize; i++ {
        current := queue[head]
        head++
        // ... process current
    }
}

This avoids reslicing and keeps memory usage predictable. For production-grade code or very large inputs, this small change can make a meaningful difference.

Best Practices

1. Always Validate Inputs

Check for empty grids or grids with empty rows before accessing grid[0]. Defensive programming prevents panics and makes your function safer to reuse.

2. Avoid Mutating Input When Possible

The implementation above mutates the input grid to mark oranges as rotten. If callers need the original grid preserved, make a deep copy first:

func copyGrid(grid [][]int) [][]int {
    duplicate := make([][]int, len(grid))
    for i := range grid {
        duplicate[i] = append([]int(nil), grid[i]...)
    }
    return duplicate
}

3. Use a Visited Set for Complex Variants

In this problem, mutating the grid in place is acceptable because the only states are fresh, rotten, and empty. For more complex variants with additional states, consider using a separate visited boolean grid or a map to track processed cells explicitly.

4. Prefer BFS Over DFS for Shortest Path

DFS would explore one path deeply before backtracking, which does not naturally yield the minimum time. BFS explores all nodes at the current depth before moving deeper, guaranteeing the shortest path in an unweighted graph — exactly what we need here.

5. Test Thoroughly

Write unit tests covering the edge cases mentioned earlier. Go's testing package makes this straightforward:

package main

import "testing"

func TestOrangesRotting(t *testing.T) {
    tests := []struct {
        name string
        grid [][]int
        want int
    }{
        {"all rotten", [][]int{{2}}, 0},
        {"single fresh", [][]int{{1}}, -1},
        {"empty cell", [][]int{{0}}, 0},
        {"simple spread", [][]int{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}, 4},
        {"unreachable", [][]int{{2, 1, 1}, {0, 1, 1}, {1, 0, 1}}, -1},
        {"no rotten", [][]int{{1, 1}, {1, 1}}, -1},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            got := orangesRotting(tt.grid)
            if got != tt.want {
                t.Errorf("got %d, want %d", got, tt.want)
            }
        })
    }
}

Run the tests with go test -v to verify each scenario behaves as expected.

Complexity Analysis

Let m be the number of rows and n the number of columns.

• Time complexity: O(m * n). Each cell is enqueued and dequeued at most once, and we inspect each of its four neighbors a constant number of times.
• Space complexity: O(m * n) in the worst case, when every cell is rotten initially and all of them sit in the queue simultaneously.

This is asymptotically optimal because we must at least examine every cell once to determine the answer.

Common Mistakes to Avoid

• Incrementing time on every dequeue: Time should only increment once per level, not once per orange. Processing the queue level by level is essential.
• Forgetting to check bounds: Always verify that neighbor coordinates are within the grid before accessing them.
• Rotting already rotten oranges: Only enqueue fresh oranges. Re-enqueueing rotten ones causes infinite loops or incorrect counts.
• Returning time when fresh oranges remain: Always check freshCount at the end. The queue being empty does not guarantee all oranges rotted.

Conclusion

The Rotting Oranges problem is a beautiful demonstration of how multi-source BFS elegantly solves propagation problems on grids. By enqueuing all rotten oranges at once and processing the queue level by level, we naturally compute the minimum time for the rot to reach every reachable fresh orange. The Go implementation is concise, efficient, and idiomatic, leveraging slices for the queue and in-place mutation for tracking visited cells. By understanding the algorithm, handling edge cases carefully, optimizing the queue, and writing thorough tests, you now have a complete, production-ready solution that you can adapt to similar problems such as walls-and-gates, shortest path in binary matrices, or any scenario involving layered expansion from multiple sources.