How do you approach Rotting Oranges?

This is a multi-source BFS: every rotten orange starts at time 0.

What are common mistakes on Rotting Oranges?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Rotting Oranges

MediumAlgorithms

Description

In a grid, each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

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

Example 1

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

Output: 4

Explanation: After 4 minutes every reachable fresh orange is rotten.

Example 2

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

Output: -1

Explanation: The bottom-left orange is never reached.

Constraints

- m == grid.length - n == grid[i].length - 1 <= m, n <= 10 - grid[i][j] is 0, 1, or 2

Rotting Oranges: approach, complexity and pitfalls

A medium graphs problem, graded against 5 test cases (3 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

If you are stuck

Show the 3-step hint ladder

This is a multi-source BFS: every rotten orange starts at time 0.
Process the queue one level (minute) at a time and count fresh oranges remaining.
If fresh oranges remain after BFS finishes, return -1.

The optimal approach

Show the approach: The approach

Multi-source BFS. Seed the queue with every rotten orange and count fresh ones. Each BFS level is one minute; rot adjacent fresh oranges and decrement the fresh count. If any fresh remain, it is unreachable -> -1.

Time: O(m·n). Space: O(m·n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.