Rotting Oranges

Medium

The problem

grid has 0 for an empty cell, 1 for a fresh orange and 2 for a rotten orange. Every minute, each fresh orange that is next to a rotten one (up, down, left or right) becomes rotten. Return the number of minutes until no fresh orange is left, or -1 if some fresh orange can never rot. If there are no fresh oranges at the start, the answer is 0.

Example 1
Input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
Output: 4
The rot spreads outward from the top-left corner. The bottom-right orange is the last to rot, after 4 minutes.
Example 2
Input: grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]
Output: -1
The orange at the bottom-left is cut off by empty cells and never rots.
Example 3
Input: grid = [[0, 2]]
Output: 0
There are no fresh oranges, so nothing has to rot.

Limits

1 ≤ rows, columns ≤ 300
Each cell is 0, 1 or 2

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

All rotten oranges spread at the same time. Each minute is one ring of spreading outward.

The idea

Multi-source BFS from all rotten oranges, counting layers; at the end if any fresh orange remains return −1.

Target: O(m·n) time

Go function shape

func orangesRotting(grid [][]int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// OrangesRotting returns the minutes until no fresh orange is left, or -1 if one can never rot.
// All rotten oranges spread at the same moment, so each BFS layer is one minute.
func OrangesRotting(grid [][]int) int {
	type cell struct{ r, c int }
	var queue []cell
	fresh := 0
	for r := range grid {
		for c := range grid[r] {
			switch grid[r][c] {
			case 2:
				queue = append(queue, cell{r, c})
			case 1:
				fresh++
			}
		}
	}
	minutes := 0
	for len(queue) > 0 && fresh > 0 {
		minutes++
		for size := len(queue); size > 0; size-- { // one layer = one minute
			cur := queue[0]
			queue = queue[1:]
			for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
				r, c := cur.r+d[0], cur.c+d[1]
				if r >= 0 && c >= 0 && r < len(grid) && c < len(grid[0]) && grid[r][c] == 1 {
					grid[r][c] = 2
					fresh--
					queue = append(queue, cell{r, c})
				}
			}
		}
	}
	if fresh > 0 {
		return -1
	}
	return minutes
}

Read the lesson: Graphs: BFS / DFS / Topological Sort