Course4all
Join us on telegram
Home/dsa/Graphs/Rotting Oranges

Rotting Oranges

Master this topic with zero to advance depth.

Rotting Oranges

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.

Visual Representation

Minute 0: [[2,1,1],[1,1,0],[0,1,1]] Minute 1: [[2,2,1],[2,1,0],[0,1,1]] Minute 2: [[2,2,2],[2,2,0],[0,1,1]] Minute 3: [[2,2,2],[2,2,0],[0,2,1]] Minute 4: [[2,2,2],[2,2,0],[0,2,2]] Result: 4
Medium

Examples

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

Fresh oranges at (0,1), (0,2), (1,0), (1,1), (2,1), (2,2) rot in 4 minutes.

Approach 1

Level I: Brute Force (Simulation)

Intuition

Simulate the rotting process minute by minute. In each minute, look for fresh oranges that are adjacent to any rotten orange. Mark them to rot in the next minute. Repeat this until no new oranges rot.

Thought Process

  1. In a loop:
    • Check every cell. If it's fresh ('1') and has a rotten neighbor ('2'), mark it to rot.
    • Update the grid. Increment time.
    • If no orange rotted in this round, stop.
  2. After the loop, check if any fresh oranges remain.

Why it's inefficient

We iterate through the entire M×NM \times N grid multiple times (up to M×NM \times N times).

⏱ O((M * N)^2) - We may loop $M \times N$ times, each scanning the whole grid.💾 O(M * N) - To keep track of which oranges rot in the next step.

Detailed Dry Run

Grid: [[2,1,1],[0,1,1],[1,0,1]] Min 1: (0,0) rots (0,1). Grid: [[2,2,1],...] Min 2: (0,1) rots (0,2). Grid: [[2,2,2],...] ...

java
class Solution {
    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length, time = 0;
        while (true) {
            List<int[]> toRot = new ArrayList<>();
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    if (grid[r][c] == 1) {
                        if (hasRottenNeighbor(grid, r, c)) toRot.add(new int[]{r, c});
                    }
                }
            }
            if (toRot.isEmpty()) break;
            for (int[] cell : toRot) grid[cell[0]][cell[1]] = 2;
            time++;
        }
        for (int[] row : grid) for (int val : row) if (val == 1) return -1;
        return time;
    }
    private boolean hasRottenNeighbor(int[][] grid, int r, int c) {
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 2) return true;
        }
        return false;
    }
}
Approach 2

Level III: Optimal (Multi-source BFS)

Intuition

Rotting spreads like a wave. BFS is perfect for level-by-level spreading. Instead of one source, we start with all initial rotten oranges in the queue.

Thought Process

  1. Count fresh oranges and add all rotten orange coordinates to a Queue.
  2. While queue is not empty and fresh > 0:
    • For all oranges currently in the queue (this level/minute):
      • Poll an orange, visit its 4 neighbors.
      • If neighbor is fresh:
        • Mark it rotten, decrement fresh, add to queue.
    • Increment minutes after processing each level.
  3. Return minutes if fresh == 0, else -1.

Pattern: Multi-source BFS

⏱ O(M * N) - Each cell is visited once.💾 O(M * N) - Queue size in worst case.

Detailed Dry Run

Grid: [[2,1,1],[1,1,0],[0,1,1]]

  1. Queue: [(0,0)], Fresh: 6
  2. Min 1: Rot (0,1), (1,0). Queue: [(0,1),(1,0)], Fresh: 4
  3. Min 2: Rot (0,2), (1,1). Queue: [(0,2),(1,1)], Fresh: 2 ...
java
import java.util.*;

public class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> q = new LinkedList<>();
        int fresh = 0, R = grid.length, C = grid[0].length;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (grid[r][c] == 2) q.add(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }
        if (fresh == 0) return 0;
        int mins = 0;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        while (!q.isEmpty() && fresh > 0) {
            mins++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curr = q.poll();
                for (int[] d : dirs) {
                    int nr = curr[0] + d[0], nc = curr[1] + d[1];
                    if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; fresh--; q.add(new int[]{nr, nc});
                    }
                }
            }
        }
        return fresh == 0 ? mins : -1;
    }
}
← Previous QuestionPacific Atlantic Water Flow
Next Question →Course Schedule II