Skip to main content

994. Rotting Oranges

medium

Each minute, rotten oranges in a grid infect their 4-neighbor fresh oranges. Return the minutes until none are fresh, or -1 if impossible. The textbook multi-source BFS problem — push every rotten cell into the queue at once.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Constraints

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

Examples

Example 1

Input
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output
4

Example 2

Input
grid = [[2,1,1],[0,1,1],[1,0,1]]
Output
-1

Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3

Input
grid = [[0,2]]
Output
0

Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Picture rot spreading outward from every rotten cell simultaneously. Which traversal naturally captures 'all sources expand one step at a time'?

Hint 2

Multi-source BFS. Push every initially-rotten cell into the queue (all at minute 0), then process the queue one level at a time.

Hint 3

Also count fresh oranges up front. After BFS finishes, if fresh > 0 some cell was unreachable — return -1. Otherwise return the number of completed levels.

Solution approach

Reveal approach

First pass: scan the grid, push every cell with value 2 into a queue (the BFS frontier) and count cells with value 1 (fresh remaining). Then run a level-order BFS: each iteration pops the entire current level, and for each rotten cell, attempts to rot its 4 in-bounds neighbors that are fresh — flip them to 2, decrement fresh, push them as next-level frontier. After each level that actually rotted something, increment the minute counter. Stop when the queue is empty. If fresh > 0 at the end, some orange was unreachable — return -1. Otherwise return the minute counter. The 'don't increment the counter on the level that doesn't rot anything' detail handles the all-rotten-from-start case (output 0). O(m*n) time, O(m*n) space.

Complexity

Time
O(m*n)
Space
O(m*n)

Related patterns

  • graph-bfs
  • multi-source-bfs
  • matrix

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

More Graphs practice problems

See all Graphs problems →