Skip to content
AI360Xpert
Back to Graphs
Medium

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`.

Examples

Input:grid = [[2,1,1],[1,1,0],[0,1,1]]
Output:4
Minute 0: Rotten orange is at (0, 0). Minute 1: Oranges at (0, 1) and (1, 0) rot. Minute 2: Oranges at (0, 2) and (1, 1) rot. Minute 3: Orange at (1, 2) rots. Note that (2, 1) is adjacent to (1, 1) but not directly affected until the next step if we had more. Wait, let's trace properly: Minute 0: [(0,0)] Minute 1: [(0,1), (1,0)] Minute 2: [(0,2), (1,1)] Minute 3: [(1,2), (2,1)] Minute 4: [(2,2)] Total time is 4 minutes.
Input:grid = [[2,1,1],[0,1,1],[1,0,1]]
Output:-1
The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Input:grid = [[0,2]]
Output:0
Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.

Breadth-First Search (BFS)

Approach

Since we want to find the *minimum* time for a spreading process, BFS is the ideal choice. We first scan the grid to find all initially rotten oranges and add them to a queue. We also count the number of fresh oranges. Then, we process the queue level by level (minute by minute). For each rotten orange, we rot its adjacent fresh oranges, add them to the queue, and decrement the fresh count. If the queue is empty but there are still fresh oranges left, we return -1. Otherwise, we return the total minutes elapsed.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(m * n)

We process each cell in the grid at most twice. First during the initial scan, and then once during the BFS. The space complexity is bounded by the size of the queue, which can contain at most O(m * n) elements.

Solution.java
class Solution {    public int orangesRotting(int[][] grid) {        if (grid == null || grid.length == 0) return 0;                int rows = grid.length;        int cols = grid[0].length;        Queue<int[]> queue = new LinkedList<>();        int freshCount = 0;                // Step 1: Add all rotten oranges to queue and count fresh ones        for (int r = 0; r < rows; r++) {            for (int c = 0; c < cols; c++) {                if (grid[r][c] == 2) {                    queue.offer(new int[]{r, c});                } else if (grid[r][c] == 1) {                    freshCount++;                }            }        }                // If there are no fresh oranges, no time is needed        if (freshCount == 0) return 0;                int minutes = 0;        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};                // Step 2: BFS traversal        while (!queue.isEmpty() && freshCount > 0) {            int size = queue.size();            minutes++;                        // Process all oranges at the current minute level            for (int i = 0; i < size; i++) {                int[] curr = queue.poll();                                for (int[] dir : dirs) {                    int r = curr[0] + dir[0];                    int c = curr[1] + dir[1];                                        // If adjacent is fresh, rot it                    if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1) {                        grid[r][c] = 2; // Mark as rotten                        freshCount--;                        queue.offer(new int[]{r, c});                    }                }            }        }                return freshCount == 0 ? minutes : -1;    }}