5. Rotting Oranges

Description

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.

Example 1:

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

Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: 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.

Approach

• We will have a queue that will have all the rotten col and row then also maintain the fresh count
• Now we go through rotten col and row then expand in all 4 to check if there any fresh that we can turn bad if yes then reduce one from fresh list and add this to rotten queue
• If we turned at least one then add to the minutes at then end
• the for loop in while we can think as first we go through the queue then by the time we are done we must have added new then we go through the list again and keep doing that till we finish
• Time: O(m*n), Space: O(m*n)

class Solution {
    public int orangesRotting(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        //check all directions around
        int[][] directions = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
        Queue<int[]> rot = new LinkedList<>();
        
        int fresh = 0; //first we collect all fresh then by the end it should reach 0
        for (int i = 0; i < row; i++) {
            for (int j= 0; j < col; j++) {
                if (grid[i][j] == 2) {
                    rot.offer(new int[]{i,j}); // rotten col and row
                } else if (grid[i][j] == 1) {
                    fresh++; // fresh count
                }
            }
        }
        //all the oranges are rotten from the start
        if (fresh == 0)
            return 0;
        //for the answer
        int minutes = 0;
        while (!rot.isEmpty()) {
            boolean rotted = false; //if in all 4 there is any fresh then turn rotted and add minutes
            for (int i = rot.size(); i > 0; i--) {
                int[] ora = rot.poll();
                for(int[] dir: directions) {
                    int r = ora[0] + dir[0];
                    int c = ora[1] + dir[1];
                    if (r >= 0 && r < row && c >= 0 && c < col && grid[r][c] == 1) {
                        grid[r][c] = 2; //turn rotten
                        rot.offer(new int[]{r,c}); //add newly rotten in the queue
                        fresh--; //now rotted
                        rotted = true; //we have turned atleast one rotten
                    }
                }
            }
            if (rotted) //since we turn rotted we need to add minute
                minutes++;
        }
 
        return (fresh == 0) ? minutes : -1;
    }
}

Approach 1: Brute Force (Grid Scanning / Simulation)

Intuition

Repeatedly scan the entire grid minute by minute. In each pass, identify all fresh oranges adjacent to rotten ones, mark them to rot, and update the grid. Continue until a full pass results in no new rotted oranges.

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int minutes = 0;
        boolean changed = true;
 
        while (changed) {
            changed = false;
            // Temporary flag array to mark oranges that will rot at the END of this minute
            boolean[][] willRot = new boolean[rows][cols];
 
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 2) {
                        // Check 4 directions
                        if (r > 0 && grid[r - 1][c] == 1) willRot[r - 1][c] = true;
                        if (r < rows - 1 && grid[r + 1][c] == 1) willRot[r + 1][c] = true;
                        if (c > 0 && grid[r][c - 1] == 1) willRot[r][c - 1] = true;
                        if (c < cols - 1 && grid[r][c + 1] == 1) willRot[r][c + 1] = true;
                    }
                }
            }
 
            // Apply rotting for this minute
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (willRot[r][c]) {
                        grid[r][c] = 2;
                        changed = true;
                    }
                }
            }
 
            if (changed) minutes++;
        }
 
        // Check if any fresh orange remains
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) return -1;
            }
        }
 
        return minutes;
    }
}
 

Complexity

• Time Complexity: $O((m\times n{)}^2)$ — In the worst-case (a long snake-like line of oranges), rotting takes up to $O(m\times n)$ minutes, and each minute requires rescanning all $m\times n$ cells.
• Space Complexity: $O(m\times n)$ — For the boolean tracking array.

---

Approach 2: Optimal (Multi-Source BFS)

Intuition

Instead of scanning the whole grid repeatedly, keep track of rotten orange positions in a Queue. Process oranges in waves level by level, visiting each cell at most once.

import java.util.LinkedList;
import java.util.Queue;
 
class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
 
        // 1. Collect initial rotten oranges 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 (freshCount == 0) return 0;
 
        int minutes = 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        // 2. Multi-source BFS expansion
        while (!queue.isEmpty() && freshCount > 0) {
            int size = queue.size();
            minutes++;
 
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int r = curr[0];
                int c = curr[1];
 
                for (int[] dir : directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];
 
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        freshCount--;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }
 
        return freshCount == 0 ? minutes : -1;
    }
}
 

Complexity

• Time Complexity: $O(m\times n)$ — Each cell is added and removed from the queue at most once.
• Space Complexity: $O(m\times n)$ — Space used by the Queue in the worst case.