FastPrep
Problem · Array

Minimum Time to Rot All Oranges

Learn this problem
● MediumMicrosoft logoMicrosoftFULLTIMEONSITE INTERVIEW
See Microsoft hiring insights

Problem statement

You are given a rectangular grid where each cell contains one of these values:

  • 0: empty;
  • 1: a fresh orange;
  • 2: a rotten orange.

Every minute, each fresh orange that is orthogonally adjacent to a rotten orange becomes rotten. Rotting within the same minute happens simultaneously.

Return the minimum number of minutes until no fresh orange remains. Return -1 if some fresh orange can never rot. If there is no fresh orange initially, return 0.

Function

orangesRotting(grid: int[][]) → int

Examples

Example 1

grid = [[2,1,1],[1,1,0],[0,1,1]]return = 4

The infection frontier reaches the final fresh orange after four minute layers.

Example 2

grid = [[2,1,1],[0,1,1],[1,0,1]]return = -1

The fresh orange in the lower-left corner is separated from every rotten orange.

Constraints

  • 1 <= grid.length, grid[row].length <= 500
  • Every row has the same length.
  • grid[row][column] is 0, 1, or 2.

More Microsoft problems

drafts saved locally
public int orangesRotting(int[][] grid) {
    // Write your code here.
}
grid[[2,1,1],[1,1,0],[0,1,1]]
expected4
checking account