584. Rotting Oranges
You are given an m x n grid grid describing a crate of oranges. Each cell holds one of three values:
0— an empty cell,1— a fresh orange,2— a rotten orange.
Once per minute, every fresh orange that shares an edge (up, down, left, or right) with a rotten orange turns rotten too. Rot spreads from all rotten oranges simultaneously.
Return the number of minutes that pass until no fresh orange remains. If the crate starts with no fresh oranges at all, that takes 0 minutes. If some fresh orange can never be reached by the rot, return -1.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: The rot starts in the top-left corner and spreads one edge per minute. The orange in the bottom-right corner is the farthest away and rots at minute 4.
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom-left corner touches only empty cells, so the rot can never reach it. It stays fresh forever.
Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: There are no fresh oranges to begin with, so zero minutes pass.
Constraints:
- 1 ≤ m, n ≤ 10
- grid[i][j] is 0, 1, or 2.
Hints:
This is a shortest-distance question in disguise: each fresh orange rots at a time equal to its grid distance from the nearest rotten orange. What traversal computes distances layer by layer?
Seed a queue with every rotten orange at time 0 (multi-source BFS). Pop cells in order, rot fresh neighbors at time t + 1, and track how many fresh oranges remain — if any survive the flood, return -1.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Expected output: 4