Rotting Oranges — Medium Coding Interview Question

You are given an m×n grid where each cell can have: 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange adjacent (4-connected) to a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange exists, or -1 if impossible.

Example

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Constraints

• 1 ≤ m, n ≤ 10
• grid[i][j] is 0, 1, or 2

Topics & Companies

Topics: graphs, arrays

Asked by: Amazon, Google, Meta, Microsoft, Bloomberg

Optimal Solution Complexity

Time complexity: O(m×n). Space complexity: O(m×n).

Practice more

• All DSA Problems
• DSA Patterns