Rotting Oranges medium

Problem Statement

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
• 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 initial coordinates of rotten oranges.
   • Create a variable minutes to track the elapsed time, initialized to 0.
   • Create a variable freshCount to count the number of fresh oranges initially present.

2. Breadth-First Search (BFS):

   • While the queue is not empty, process each rotten orange:
     • Dequeue the coordinates (row, col) of a rotten orange.
     • For each of its four adjacent cells:
       • If the cell contains a fresh orange (value 1):
         • Change the cell's value to 2 (rotten).
         • Decrement freshCount.
         • Enqueue the coordinates of the newly rotten orange.
     • If the queue is empty after processing a level (all oranges that could rot at that time have rotted), increment minutes.

3. Check for Fresh Oranges:

   • If freshCount is 0, it means all fresh oranges have rotted. Return minutes.
   • Otherwise, there are still fresh oranges that cannot be reached, so return -1.

Explanation

The solution uses Breadth-First Search (BFS) to simulate the rotting process. BFS guarantees that we process oranges level by level, finding the minimum time to rot all oranges. The freshCount variable efficiently tracks the number of fresh oranges, avoiding unnecessary iterations. If freshCount remains greater than 0 after the BFS completes, it indicates there are unreachable fresh oranges, resulting in a -1 return value.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int OrangesRotting(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        Queue<(int, int)> queue = new Queue<(int, int)>();
        int freshCount = 0;

        // Find initial rotten oranges and count fresh oranges
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.Enqueue((i, j));
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }

        int minutes = 0;
        int[] dr = { -1, 1, 0, 0 };
        int[] dc = { 0, 0, -1, 1 };

        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                (int row, int col) = queue.Dequeue();
                for (int j = 0; j < 4; j++) {
                    int newRow = row + dr[j];
                    int newCol = col + dc[j];
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 2;
                        freshCount--;
                        queue.Enqueue((newRow, newCol));
                    }
                }
            }
            if (queue.Count > 0) minutes++;
        }

        return freshCount == 0 ? minutes : -1;
    }
}

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, when all oranges are initially rotten and the queue stores all the cells. In the best case, it's O(1) if there are no rotten oranges.