Back

Rotting Oranges

medium

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,
  • 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.

Test Cases

Copy an input into the main harness and Run to verify
Input
grid = [[2,1,1],[1,1,0],[0,1,1]]
Expected Output
4
Input
grid = [[2,1,1],[0,1,1],[1,0,1]]
Expected Output
-1

Explanation: The orange in the bottom left is never reached.

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

Explanation: There are no fresh oranges, so the answer is 0.

Constraints

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

Hints

Hint 1 — click to reveal

Rot spreads to all neighbours simultaneously — that is breadth-first search, not depth-first.

Hint 2 — click to reveal

Start the BFS with every rotten orange already in the queue, then process the queue one level per minute.

Java Compiler

Powered by OneCompiler. Starter code loads automatically — edit and hit Run.