Back to Problems

Rotting Oranges

Medium
BFS

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.

This is a multi-source BFS problem where we start from all rotten oranges simultaneously. The number of BFS levels equals the time needed.

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: Minute 0: Initial state with one rotten orange. Minute 4: All oranges are rotten.

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 reachable.

Example 3

Input: grid = [[0,2]]
Output: 0
Explanation: There are no fresh oranges, so 0 minutes are needed.

Constraints

  • •m == grid.length
  • •n == grid[i].length
  • •1 <= m, n <= 10
  • •grid[i][j] is 0, 1, or 2
Show Hints (4)
Hint 1: This is multi-source BFS - start with all rotten oranges in the queue at once.
Hint 2: Each level of BFS represents one minute passing.
Hint 3: Track the count of fresh oranges. If any remain after BFS, return -1.
Hint 4: The number of levels traversed (minus 1 since we start at level 0) is the answer.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?