Rotting Oranges medium

Problem Statement

You are given an m x n grid representing a matrix 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 adjacent (4-directionally) 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

Steps

1. Initialization:

   • Create a queue to store the coordinates of rotten oranges.
   • Count the total number of fresh oranges.
   • Add the coordinates of all initial rotten oranges to the queue.

2. BFS Traversal:

   • While the queue is not empty:
     • Get the size of the queue (number of oranges to process in this minute).
     • Iterate size times:
       • Dequeue a rotten orange (row, col).
       • Explore its four neighbors:
         • If a neighbor is a fresh orange (value 1):
           • Change its value to 2 (rotten).
           • Decrement the count of fresh oranges.
           • Enqueue its coordinates.
     • Increment the time counter (minutes elapsed).

3. Result:

   • If the count of fresh oranges is 0, return the time.
   • Otherwise, return -1 (impossible to rot all oranges).

Explanation

The solution uses Breadth-First Search (BFS) to simulate the rotting process. BFS ensures that we process oranges in the order of their minimum distance from the initial rotten oranges. We keep track of the number of fresh oranges to efficiently determine when all oranges have rotted. If, after the BFS, there are still fresh oranges left, it means some oranges are unreachable, hence -1 is returned.

Code

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 freshOranges = 0;

        // Initialize queue and count fresh oranges
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    freshOranges++;
                }
            }
        }

        // BFS traversal
        int time = 0;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int row = curr[0];
                int col = curr[1];
                for (int[] dir : directions) {
                    int newRow = row + dir[0];
                    int newCol = col + dir[1];
                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 2;
                        freshOranges--;
                        queue.offer(new int[]{newRow, newCol});
                    }
                }
            }
            time++;
        }

        // Result
        return freshOranges == 0 ? time -1 : (freshOranges > 0 ? -1 : 0); //Adjust for edge case of no fresh oranges initially
    }
}

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the grid. We visit each cell at most once.
• Space Complexity: O(M * N) in the worst case, to store the queue (all cells could be rotten oranges).