G-10. Rotten Oranges (Graph - Data Structures & Algorithms)

1. Problem Statement & Grid Representation

We are given an $N \times M$ 2D matrix (grid) representing a basket of oranges. Each cell in the grid can contain one of three integer values:

• 0: An empty cell (no orange present).
• 1: A fresh orange.
• 2: A rotten orange.

The Core Objective

Determine the minimum time (in seconds/units) required to rot all fresh oranges.

• A rotten orange at index (i, j) can rot its adjacent fresh neighbors (Up, Down, Left, Right) in exactly 1 unit of time.
• If it is impossible to rot every single fresh orange in the grid, we must return -1.

2. Core Mental Model & The BFS Intuition

Why Breadth-First Search (BFS)?

At first glance, one might wonder whether to use Depth-First Search (DFS) or Breadth-First Search (BFS).

• The Trap of DFS: DFS explores as deep as possible down one path before backtracking. If we used DFS, oranges would rot sequentially down a single branch rather than spreading out simultaneously across all directions at an equal pace. This would lead to incorrect, suboptimal (higher) time calculations.
• The Power of BFS: BFS explores level by level (wave by wave). In our problem, all initially rotten oranges act as independent sources spreading rot simultaneously. At $t = 1$, all immediate neighbors of all rotten oranges rot at the same time. At $t = 2$, the newly rotten oranges spread their rot. This level-order propagation maps directly to the mechanics of a Queue-based BFS traversal.

3. Step-by-Step Evolution of the Algorithm

To simulate this multi-source simultaneous rot propagation, we require:

1. A Queue (std::queue or Queue in Java): Stores a triplet or pair structure containing the current row, column, and the time elapsed when that specific orange became rotten.
2. A Visited Matrix (visited[N][M]): Tracks which cells have already been processed or marked as rotten to prevent infinite loops and redundant work. (Note: While some approaches mutate the input grid directly, industry best practices dictate keeping the original data pristine and using a separate tracking structure).
3. Delta Arrays (drow, dcol): Cleanly handle checking the 4 directional neighbors (Up, Right, Down, Left) without writing repetitive conditional code.

4. Direction Vectors (Delta Arrays) for 4-Way Neighborhood

To navigate to the 4 adjacent cells (Up, Right, Down, Left) from any given cell (row, col), we use Delta arrays:

// Delta arrays for 4-directional traversal
int drow[] = {-1,  0, +1,  0}; // Top, Right, Bottom, Left
int dcol[] = { 0, +1,  0, -1}; // Top, Right, Bottom, Left

Neighbor coordinate calculations:

• Top: row - 1, col + 0
• Right: row + 0, col + 1
• Bottom: row + 1, col + 0
• Left: row + 0, col - 1

5. Complete Algorithm Walkthrough

1. Initialization Phase:

   • Traverse the entire $N \times M$ grid.
   • For every cell where grid[i][j] == 2, push its coordinates (i, j) and initial time 0 into the Queue. Also, mark visited[i][j] = 2.
   • For every cell where grid[i][j] == 1, keep track that a fresh orange exists.

2. BFS Traversal Phase:

   • While the queue is not empty:
     • Pop the front element containing (row, col, time).
     • Update our tracking variable maxTime = max(maxTime, time).
     • Loop through the 4 directions using drow and dcol.
     • For each neighbor (nrow, ncol):
       • Check if the neighbor coordinates are valid (within grid boundaries: $0 \le nrow < N$ and $0 \le ncol < M$).
       • Check if the neighbor is a fresh orange (grid[nrow][ncol] == 1) and not yet visited (visited[nrow][ncol] != 2).
       • If valid and fresh, mark visited[nrow][ncol] = 2 and push (nrow, ncol, time + 1) into the Queue.

3. Validation Phase:

   • After the queue is exhausted, check if all fresh oranges were successfully rotten.
   • Iterate through the grid and visited matrix: if any cell has grid[i][j] == 1 but visited[i][j] != 2, it means that particular fresh orange was unreachable. Return -1.
   • Otherwise, return maxTime.

6. Complete Code Implementation (C++ & Java)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();

        // Queue stores: { {row, col}, time }
        queue<pair<pair<int, int>, int>> q;
        vector<vector<int>> visited(n, vector<int>(m, 0));

        // Step 1: Push all initially rotten oranges into queue & mark visited
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    q.push({{i, j}, 0});
                    visited[i][j] = 2;
                }
            }
        }

        int maxTime = 0;
        // Delta arrays for Top, Right, Bottom, Left
        int drow[] = {-1, 0, +1, 0};
        int dcol[] = {0, +1, 0, -1};

        // Step 2: BFS traversal
        while (!q.empty()) {
            int r = q.front().first.first;
            int c = q.front().first.second;
            int t = q.front().second;
            q.pop();

            maxTime = max(maxTime, t);

            for (int i = 0; i < 4; i++) {
                int nrow = r + drow[i];
                int ncol = c + dcol[i];

                // Check boundary, if it's a fresh orange and not yet visited
                if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m &&
                    grid[nrow][ncol] == 1 && visited[nrow][ncol] != 2) {
                    visited[nrow][ncol] = 2;
                    q.push({{nrow, ncol}, t + 1});
                }
            }
        }

        // Step 3: Check if all fresh oranges were rotted
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && visited[i][j] != 2) {
                    return -1;
                }
            }
        }

        return maxTime;
    }
};

Java Implementation (Conceptual Equivalent)

import java.util.*;

class Pair {
    int row;
    int col;
    int time;
    Pair(int row, int col, int time) {
        this.row = row;
        this.col = col;
        this.time = time;
    }
}

class Solution {
    public int orangesRotting(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        Queue<Pair> q = new LinkedList<>();
        int[][] visited = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    q.add(new Pair(i, j, 0));
                    visited[i][j] = 2;
                }
            }
        }

        int maxTime = 0;
        int[] drow = {-1, 0, +1, 0};
        int[] dcol = {0, +1, 0, -1};

        while (!q.isEmpty()) {
            int r = q.peek().row;
            int c = q.peek().col;
            int t = q.peek().time;
            q.remove();

            maxTime = Math.max(maxTime, t);

            for (int i = 0; i < 4; i++) {
                int nrow = r + drow[i];
                int ncol = c + dcol[i];

                if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m &&
                    grid[nrow][ncol] == 1 && visited[nrow][ncol] != 2) {
                    visited[nrow][ncol] = 2;
                    q.add(new Pair(nrow, ncol, t + 1));
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && visited[i][j] != 2) {
                    return -1;
                }
            }
        }

        return maxTime;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Multi-Source BFS: When multiple starting points trigger simultaneous propagation across a grid or graph, seed all starting points into the BFS queue simultaneously at time $t = 0$.
• Level-Order Processing: BFS guarantees that nodes at distance $k$ are processed before nodes at distance $k+1$, making it the definitive algorithm for minimum time/shortest path problems on unweighted grids.
• Why DFS Fails Here: Depth-First Search explores paths sequentially rather than concurrently, resulting in incorrect, inflated time measurements.
• Delta Arrays: Using drow and dcol arrays simplifies 4-way or 8-way directional exploration without cluttered conditional statements.
• Immutability Principle: Avoid altering input reference data when running graph algorithms in production environments; allocate auxiliary tracking data structures (like visited) instead.
• Unreachable Verification: Always include a post-traversal validation check to ensure no target nodes (fresh oranges) were left behind, returning -1 if any remain untouched.