Rotting Oranges
Medium · Graphs
You are given a grid of integers representing a box of oranges, where each cell is 0 for empty, 1 for a fresh orange, or 2 for a rotten orange. Every minute, any fresh orange that is orthogonally adjacent to a rotten orange also becomes rotten. Return the minimum number of minutes that must pass until no cell has a fresh orange left, or -1 if that can never happen.
Examples
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Why: Rot spreads outward one step per minute from the single rotten orange at the corner; it takes 4 minutes to reach every fresh orange.Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Why: The orange in the bottom-left corner is isolated by empty cells so it can never rot.Input: grid = [[0,2]]
Output: 0
Why: There are no fresh oranges to begin with, so no time needs to pass.Constraints
1 <= grid.length, grid[0].length <= 10, each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange)
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Rotting Oranges. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.