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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Rotting Oranges and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →