Rotting oranges

Array Breadth-First Search Matrix

58.2% acceptance

Feb 25, 2026

14987

472

You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
    use std::collections::VecDeque;
    let (m, n) = (grid.len(), grid[0].len());
    let mut queue = VecDeque::new();
    let mut fresh = 0;
    for i in 0..m { for j in 0..n {
      match grid[i][j] { 2 => queue.push_back((i,j)), 1 => fresh += 1, _ => {} }
    }}
    let mut minutes = 0;
    while !queue.is_empty() && fresh > 0 {
      minutes += 1;
      for _ in 0..queue.len() {
        let (r, c) = queue.pop_front().unwrap();
        for (dr, dc) in [(!0usize,0usize),(1,0),(0,!0usize),(0,1)] {
          let (nr, nc) = (r.wrapping_add(dr), c.wrapping_add(dc));
          if nr < m && nc < n && grid[nr][nc] == 1 {
            grid[nr][nc] = 2; fresh -= 1; queue.push_back((nr, nc));
          }
        }
      }
    }
    if fresh > 0 { -1 } else { minutes }
  }
}