Given a grid of fresh and rotten oranges, determine how many minutes it takes for all fresh oranges to rot as rot spreads to adjacent cells each minute.
You are given an grid representing a box of oranges. Each cell contains one of three values:
0— empty cell1— fresh orange2— rotten orange
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes needed for all oranges to become rotten.
If it is impossible for some fresh oranges to rot, return -1.
The process happens simultaneously each minute, so newly rotten oranges can only affect other oranges in the next minute.
Input Format
- A 2D integer grid
gridof sizem x n grid[i][j]is one of0,1, or2
Output Format
- Return an integer: the minimum minutes needed for all fresh oranges to rot, or
-1if impossible.
Constraints
- Cell values are limited to
0,1, and2 - Rot spreads only in 4 directions: up, down, left, right
Example 1
Input
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output
4
Explanation
Minute 0: the top-left orange is rotten. Minute 1: its adjacent fresh oranges rot. Minute 2 and onward: the rot continues spreading until all fresh oranges are rotten after 4 minutes.
Example 2
Input
grid = [[2,1,1],[0,1,1],[1,0,1]]
Output
-1
Explanation
Some fresh oranges are isolated by empty cells and can never be reached by rot.
Show 1 more example
Example 3
Input
grid = [[0,2]]
Output
0
Explanation
There are no fresh oranges to rot, so the answer is 0.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.