LESSON 573 OF 679 · GRAPHS

Rotting Oranges

Practice O(m · n)

You get a grid grid that shows a crate of oranges. It is an array of m rows, and each row is an array of n integers. Each cell is:

0: empty,
1: a fresh orange,
2: a rotten orange.

Return how many minutes pass until no fresh orange is left. Return -1 if some fresh orange never rots.

Every minute, each fresh orange with a rotten neighbor turns rotten. A neighbor is the cell directly above, below, left or right. Diagonal cells are not neighbors.

Example 1:

Input: grid = [
  [2, 1, 1, 1],
  [1, 1, 0, 1],
  [0, 1, 1, 2]
]
Output: 2
Explanation: The two rotten oranges spread the rot at the same time:
  start        minute 1     minute 2
  2 1 1 1      2 2 1 1      2 2 2 2
  1 1 0 1      2 1 0 2      2 2 0 2
  0 1 1 2      0 1 2 2      0 2 2 2
After minute 2 every orange is rotten.

Example 2:

Input: grid = [[2, 1, 0, 1]]
Output: -1
Explanation: The empty cell cuts off the orange at the right end.
That orange stays fresh forever.

Example 3:

Input: grid = [[0, 0, 0]]
Output: 0
Explanation: There are no oranges at all, so there is nothing to wait for.

Constraints:

1 to 300 rows.
1 to 300 columns.
All rows have the same length.
Every cell is 0, 1 or 2.

Note:

Your algorithm should run in O(m · n) time and use O(m · n) extra space.

You could replay the grid minute by minute, with a scan of every cell each minute. That can cost O((m · n)²). Think of a long winding line of oranges that the rot creeps along one cell per minute. The tutorial uses a BFS that starts from all the rotten oranges at once. The BFS in 01 Matrix starts from all the zeros in the same way. The BFS goes level by level. The oranges that rot in minute 1 are the first level. The oranges they rot are the second level, and so on. So the number of levels is the number of minutes. A count of the fresh oranges goes down each time one rots. At the end, it tells whether some orange never rotted. Each cell joins the queue at most once.

STEP 1 OF 25

Guided

Ctrl + Enter to check