Zero To DSAZero To DSA
Privacy Policy
Course ScheduleWord Ladder

Rotting Oranges

medium
Time: O(m * n)
Space: O(m * n)

You are given an m×n grid where 0 = empty, 1 = fresh orange, 2 = rotten orange. Each minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum minutes until no fresh orange remains, or -1 if impossible.

Constraints

  • m, n <= 10

Examples

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Input: grid = [[0,2]]
Output: 0
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1