22. Rotten Oranges

✅ GFG solution to the Rotten Oranges problem: find minimum time for all oranges to rot using multi-source BFS level-by-level traversal. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given a matrix mat[][] where each cell has one of three values:

• 0 — Empty cell

• 1 — Cell with a fresh orange

• 2 — Cell with a rotten orange

A rotten orange at index (i, j) can rot adjacent fresh oranges at (i-1, j), (i+1, j), (i, j-1), (i, j+1) in one unit of time.

Your task is to determine the minimum time required so that all the oranges become rotten. If it is impossible to rot every orange, return -1.

📘 Examples

Example 1

Input: mat[][] = [[2, 1, 0, 2, 1],
                  [1, 0, 1, 2, 1],
                  [1, 0, 0, 2, 1]]
Output: 2
Explanation: Oranges at (0,0), (0,3), (1,3), and (2,3) rot adjacent fresh oranges in successive 
time frames. All fresh oranges become rotten after 2 units of time.

Example 2

Input: mat[][] = [[2, 1, 0, 2, 1],
                  [0, 0, 1, 2, 1],
                  [1, 0, 0, 2, 1]]
Output: -1
Explanation: The fresh orange at (2,0) can never be reached by any rotten orange, 
so not all oranges can rot.

🔒 Constraints

• $1 \le \text{mat.size()} \le 500$

• $1 \le \text{mat[0].size()} \le 500$

• $\text{mat}[i][j] \in {0, 1, 2}$

✅ My Approach

The optimal approach uses Multi-Source BFS (Breadth-First Search) — treating all initially rotten oranges as simultaneous BFS starting points and spreading rot level by level:

Multi-Source BFS (Level-Order Traversal)

1. Initialize:

   • Scan the entire matrix. Push all rotten orange positions (i, j) into the queue and count all fresh oranges.

   • If fresh == 0 initially, return 0 immediately.

2. BFS Level by Level:

   • Each BFS level represents one unit of time.

   • For every rotten orange in the current level, try to rot all 4 adjacent fresh neighbors.

   • Mark newly rotted oranges as 2, decrement fresh, and push them into the queue for the next level.

3. Early Exit:

   • The outer while loop has condition !q.empty() && fresh > 0, so BFS stops as soon as all fresh oranges are rotted — no unnecessary iterations.

4. Final Check:

   • If fresh > 0 after BFS completes, isolated fresh oranges exist — return -1.

   • Otherwise return time (number of BFS levels processed).

📝 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n × m), as every cell in the matrix is visited at most once during the BFS traversal, where n and m are the number of rows and columns respectively.

• Expected Auxiliary Space Complexity: O(n × m), as the BFS queue can hold at most all cells of the matrix in the worst case when all oranges are initially rotten.

🖥️ Code (C)

typedef struct {
    int x, y;
} Point;

int orangesRotting(int** mat, int n, int m) {
    Point q[n * m];
    int front = 0, back = 0, fresh = 0, time = 0;
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 2) q[back++] = (Point){i, j};
            else if (mat[i][j] == 1) fresh++;
        }
    while (front < back && fresh) {
        time++;
        int sz = back - front;
        while (sz--) {
            Point p = q[front++];
            for (int d = 0; d < 4; d++) {
                int nx = p.x+dx[d], ny = p.y+dy[d];
                if (nx>=0 && nx<n && ny>=0 && ny<m && mat[nx][ny]==1)
                    mat[nx][ny] = 2, fresh--, q[back++] = (Point){nx, ny};
            }
        }
    }
    return fresh ? -1 : time;
}

🧑‍💻 Code (C++)

class Solution {
public:
    int orangesRot(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size(), fresh = 0, time = 0;
        queue<pair<int,int>> q;
        int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2) q.push({i, j});
                else if (mat[i][j] == 1) fresh++;
            }
        while (!q.empty() && fresh) {
            time++;
            for (int sz = q.size(); sz--;) {
                auto [x, y] = q.front(); q.pop();
                for (int d = 0; d < 4; d++) {
                    int nx = x+dx[d], ny = y+dy[d];
                    if (nx>=0 && nx<n && ny>=0 && ny<m && mat[nx][ny]==1)
                        mat[nx][ny] = 2, fresh--, q.push({nx, ny});
                }
            }
        }
        return fresh ? -1 : time;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ BFS Without Modifying Input (Distance Array)

💡 Algorithm Steps:

1. Allocate a dist[][] grid initialized to -1 to track earliest rot time for each cell, leaving the original matrix untouched.

2. Push all initially rotten positions into the queue and set their dist to 0.

3. Standard BFS: for each dequeued cell, attempt to rot all 4 unvisited fresh neighbors, setting dist[nx][ny] = dist[x][y] + 1.

4. Track the maximum distance seen. If fresh is still non-zero after BFS, return -1.

class Solution {
public:
    int orangesRot(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size(), fresh = 0, ans = 0;
        vector<vector<int>> dist(n, vector<int>(m, -1));
        queue<pair<int,int>> q;
        int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2) { dist[i][j] = 0; q.push({i,j}); }
                else if (mat[i][j] == 1) fresh++;
            }
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int d = 0; d < 4; d++) {
                int nx = x+dx[d], ny = y+dy[d];
                if (nx>=0 && nx<n && ny>=0 && ny<m && mat[nx][ny]==1 && dist[nx][ny]==-1) {
                    dist[nx][ny] = dist[x][y]+1;
                    ans = max(ans, dist[nx][ny]);
                    fresh--;
                    q.push({nx, ny});
                }
            }
        }
        return fresh ? -1 : ans;
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(n × m) — Each cell is enqueued and dequeued at most once

• Auxiliary Space: 💾 O(n × m) — Extra distance grid plus the BFS queue

✅ Why This Approach?

• Completely non-destructive — the original matrix is never modified

• The distance grid is useful when you need to know when each cell rotted

• Cleaner separation between input data and BFS state

---

📊 3️⃣ BFS Using Index Encoding (No Pair Overhead)

💡 Algorithm Steps:

1. Encode cell (i, j) as a single integer i*m + j to store in a plain integer queue, avoiding pair or struct allocation.

2. During BFS, decode with x = encoded / m, y = encoded % m for neighbor computation.

3. Track fresh count and BFS levels identically to the main approach.

4. Return -1 if fresh remains, else return the number of levels elapsed.

class Solution {
public:
    int orangesRot(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size(), fresh = 0, time = 0;
        queue<int> q;
        int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2) q.push(i*m+j);
                else if (mat[i][j] == 1) fresh++;
            }
        while (!q.empty() && fresh) {
            time++;
            for (int sz = q.size(); sz--;) {
                int x = q.front()/m, y = q.front()%m; q.pop();
                for (int d = 0; d < 4; d++) {
                    int nx = x+dx[d], ny = y+dy[d];
                    if (nx>=0 && nx<n && ny>=0 && ny<m && mat[nx][ny]==1)
                        mat[nx][ny]=2, fresh--, q.push(nx*m+ny);
                }
            }
        }
        return fresh ? -1 : time;
    }
};

📝 Complexity Analysis:

• Time: ⏱️ O(n × m) — Single complete BFS pass

• Auxiliary Space: 💾 O(n × m) — Integer queue can hold at most all cells

✅ Why This Approach?

• Integer queue is more cache-friendly than a pair queue — each element is 4 bytes vs 8 bytes

• Compact encoding reduces queue memory footprint by half

• Preferred in competitive programming where constant factors matter

---

🆚 🔍 Comparison of Approaches

🚀 Approach	⏱️ Time	💾 Space	✅ Pros	⚠️ Cons
🏷️ Fresh-Count BFS (Main)	🟢 O(n×m)	🟢 O(n×m)	🚀 Early exit, clean logic	🔧 Mutates input matrix
🗺️ Distance Array BFS	🟢 O(n×m)	🟡 O(n×m) extra	📖 Non-destructive, debug-friendly	💾 Extra distance grid needed
🔢 Index-Encoded BFS	🟢 O(n×m)	🟢 O(n×m)	⭐ Cache-friendly, minimal overhead	🔧 Manual encode/decode logic

🏆 Best Choice Recommendation

🎯 Scenario	🎖️ Recommended	🔥 Rating
🏅 General / Interviews	🥇 Fresh-Count BFS	★★★★★
🔒 Read-only input constraint	🥈 Distance Array BFS	★★★★☆
⚡ Competitive / Tight memory	🥉 Index-Encoded BFS	★★★★☆

☕ Code (Java)

class Solution {
    public int orangesRot(int[][] mat) {
        int n = mat.length, m = mat[0].length, fresh = 0, time = 0;
        Queue<int[]> q = new ArrayDeque<>();
        int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2) q.add(new int[]{i, j});
                else if (mat[i][j] == 1) fresh++;
            }
        while (!q.isEmpty() && fresh > 0) {
            time++;
            for (int sz = q.size(); sz-- > 0;) {
                int[] p = q.poll();
                for (int d = 0; d < 4; d++) {
                    int nx = p[0]+dx[d], ny = p[1]+dy[d];
                    if (nx>=0 && nx<n && ny>=0 && ny<m && mat[nx][ny]==1) {
                        mat[nx][ny] = 2; fresh--; q.add(new int[]{nx, ny});
                    }
                }
            }
        }
        return fresh > 0 ? -1 : time;
    }
}

🐍 Code (Python)

class Solution:
    def orangesRot(self, mat):
        from collections import deque
        n, m = len(mat), len(mat[0])
        q, fresh = deque(), 0
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 2: q.append((i, j))
                elif mat[i][j] == 1: fresh += 1
        time, dirs = 0, [(0,1),(0,-1),(1,0),(-1,0)]
        while q and fresh:
            time += 1
            for _ in range(len(q)):
                x, y = q.popleft()
                for dx, dy in dirs:
                    nx, ny = x+dx, y+dy
                    if 0<=nx<n and 0<=ny<m and mat[nx][ny]==1:
                        mat[nx][ny] = 2; fresh -= 1; q.append((nx, ny))
        return -1 if fresh else time

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count

Visitor counter