Rotting Oranges

LeetCode 994 · View on LeetCode

Problem

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

0 — empty cell
1 — fresh orange
2 — rotten orange

Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes until no fresh orange remains. If impossible, return -1.

Example

Input:  [[2,1,1],
         [1,1,0],
         [0,1,1]]

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

Output: 4

Approach

Multi-source BFS. Start from ALL rotten oranges simultaneously (enqueue them all at time 0). Each BFS level = one minute. The grid mutation (1 → 2) acts as the visited marker.

Solution

package main

import "fmt"

func orangesRotting(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	queue := [][]int{}
	fresh := 0

	// Collect all initial rotten oranges and count fresh ones
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if grid[i][j] == 2 {
				queue = append(queue, []int{i, j})
			} else if grid[i][j] == 1 {
				fresh++
			}
		}
	}

	minutes := 0
	dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

	// BFS level by level — each level = one minute
	for len(queue) > 0 && fresh > 0 {
		size := len(queue)
		for k := 0; k < size; k++ {
			cell := queue[0]
			queue = queue[1:]
			for _, d := range dirs {
				r, c := cell[0]+d[0], cell[1]+d[1]
				if r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1 {
					grid[r][c] = 2 // rot it (also marks visited)
					fresh--
					queue = append(queue, []int{r, c})
				}
			}
		}
		minutes++
	}

	if fresh > 0 {
		return -1 // some oranges unreachable
	}
	return minutes
}

func main() {
	grid := [][]int{
		{2, 1, 1},
		{1, 1, 0},
		{0, 1, 1},
	}
	fmt.Println(orangesRotting(grid)) // 4
}

Complexity

Time: O(m × n) — each cell enqueued at most once
Space: O(m × n) — queue can hold all cells in worst case