Rotting Oranges

In this page, we will solve the Rotting Oranges problem using two different approaches: Breadth First Search and Depth First Search technique. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description

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.

Examples

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

Example 3:

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

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

---

Solution for Rotting Oranges Problem

Intuition and Approach

The idea is that for each rotten orange, we will find how many fresh oranges there are in its 4 directions. If we find any fresh orange we will make it into a rotten orange. One rotten orange can rotten up to 4 fresh oranges present in its 4 directions. For this problem, First we will be using the BFS ( Breadth-First Search ) technique and Then will be using the DFS ( Depth-First Search ) technique.

• Breadth First Search
• Depth First Search

Approach 1: Breadth First Search

First of all we will create a Queue data structure to store coordinate of Rotten Oranges

We will also have variables as:

Total_oranges - It will store total number of oranges in the grid ( Rotten + Fresh ) Count - It will store the total number of oranges rotten by us . Total_time - total time taken to rotten. -> After this, we will traverse the whole grid and count the total number of oranges in the grid and store it in Total_oranges. Then we will also push the rotten oranges in the Queue data structure as well.

-> Now while our queue is not empty, we will pick up each Rotten Orange and check in all its 4 directions whether a Fresh orange is present or not. If it is present we will make it rotten and push it in our queue data structure and pop out the Rotten Orange which we took up as its work is done now.

-> Also we will keep track of the count of rotten oranges we are getting.

-> If we rotten some oranges, then obviously our queue will not be empty. In that case, we will increase our total time. This goes on until our queue becomes empty.

-> After it becomes empty, We will check whether the total number of oranges initially is equal to the current count of oranges. If yes, we will return the total time taken, else will return -1 because some fresh oranges are still left and can’t be made rotten.

Codes in Different Languages

JavaScript

Written by @aryan-1309

 function twoSum(nums, target) {
 var orangesRotting = function(grid) {
  let fresh = 0,
         rott = 0,
         m = grid.length,
         n = grid[0].length;
     const q = [];

     for (let i = 0; i < m; i++) {
         for (let j = 0; j < n; j++) {
             if (grid[i][j] === 2) {
                 q.push([i, j]);
             }

             if (grid[i][j] === 1) fresh++;
         }
     }

     if (fresh === 0) return 0;

     console.log(fresh);

     const dr = [1, 0, -1, 0];
     const dc = [0, 1, 0, -1];
     let cnt = -1;

     while (q.length > 0) {
         let size = q.length;
         while (size--) {
             const [x, y] = q.shift();
             for (let i = 0; i < 4; i++) {
                 const row = x + dr[i];
                 const col = y + dc[i];

                 if (
                     row >= 0 &&
                     row < m &&
                     col >= 0 &&
                     col < n &&
                     grid[row][col] === 1
                 ) {
                     q.push([row, col]);
                     grid[row][col] = 2;
                     rott++;
                 }
             }
         }
         cnt++;
     }

     console.log(rott);

     return fresh === rott ? cnt : -1;
 };

TypeScript

Written by @aryan-1309

 function orangesRotting(grid: number[][]): number {
 let fresh = 0,
         rott = 0,
         m = grid.length,
         n = grid[0].length;
     const q: [number, number][] = [];

     for (let i = 0; i < m; i++) {
         for (let j = 0; j < n; j++) {
             if (grid[i][j] === 2) {
                 q.push([i, j]);
             }

             if (grid[i][j] === 1) fresh++;
         }
     }

     if (fresh === 0) return 0;

     let dr = [+1, 0, -1, 0];
     let dc = [0, +1, 0, -1];
     let cnt = -1;

     while (q.length > 0) {
         let size = q.length;
         while (size--) {
             let [x, y] = q.shift()!;
             for (let i = 0; i < 4; i++) {
                 let row = x + dr[i];
                 let col = y + dc[i];

                 if (
                     row >= 0 &&
                     row < m &&
                     col >= 0 &&
                     col < n &&
                     grid[row][col] === 1
                 ) {
                     q.push([row, col]);
                     grid[row][col] = 2;
                     rott++;
                 }
             }
         }
         cnt++;
     }

     return fresh === rott ? cnt : -1;
 };

Python

Written by @aryan-1309

 from collections import deque

 class Solution(object):
 def orangesRotting(self, grid):
     """
     :type grid: List[List[int]]
     :rtype: int
     """
     fresh = 0
     rott = 0
     m = len(grid)
     n = len(grid[0])
     q = deque()

     for i in range(m):
         for j in range(n):
             if grid[i][j] == 2:
                 q.append((i, j))
             if grid[i][j] == 1:
                 fresh += 1

     if fresh == 0:
         return 0

     dr = [1, 0, -1, 0]
     dc = [0, 1, 0, -1]
     cnt = -1

     while q:
         size = len(q)
         while size > 0:
             x, y = q.popleft()

             for i in range(4):
                 row = x + dr[i]
                 col = y + dc[i]

                 if 0 <= row < m and 0 <= col < n and grid[row][col] == 1:
                     q.append((row, col))
                     grid[row][col] = 2
                     rott += 1
             size -= 1
         cnt += 1 

     return cnt if fresh == rott else -1

Java

Written by @aryan-1309

 import java.util.LinkedList;
 import java.util.Queue;

 class Solution {
     public int orangesRotting(int[][] grid) {
         int fresh = 0, rott = 0, m = grid.length, n = grid[0].length;
         Queue<int[]> q = new LinkedList<>();

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

                 if (grid[i][j] == 1) fresh++;
             }
         }

         if (fresh == 0) return 0;

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

         while (!q.isEmpty()) {
             int size = q.size();
             while (size-- > 0) {
                 int[] curr = q.poll();
                 int x = curr[0];
                 int y = curr[1];

                 for (int i = 0; i < 4; i++) {
                     int row = x + dr[i];
                     int col = y + dc[i];

                     if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == 1) {
                         q.add(new int[]{row, col});
                         grid[row][col] = 2;
                         rott++;
                     }
                 }
             }
             cnt++;
         }

         return fresh == rott ? cnt : -1;
     }
 }

C++

Written by @aryan-1309

 class Solution {
 public:
     int orangesRotting(vector<vector<int>>& grid) {
         
         int fresh=0, rott=0, m=grid.size(), n=grid[0].size();
         queue<pair<int,int>> q;

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

                 if(grid[i][j]==1) fresh++;
             }
         }

         if(fresh==0) return 0;

         cout<< fresh << endl;
         
         int dr[4] = {+1,0,-1,0};
         int dc[4] = {0,+1,0,-1};
         int cnt = -1;

         while(!q.empty()){
             int size = q.size();
             while(size--){
             int x = q.front().first;
             int y = q.front().second;
             q.pop();

             for(int i=0 ; i<4 ; i++){
                 int row = x + dr[i];
                 int col = y + dc[i];

                 if(row>=0 && row<m && col>=0 && col<n && grid[row][col]==1){
                     q.push({row,col});
                     grid[row][col] = 2;
                     rott++;
                 }
             }
             }
             cnt++; 
         }

         cout << rott ;

         return fresh==rott ? cnt : -1;
     }
 };

Complexity Analysis

• Time Complexity: $O(m*n)$
• Space Complexity: $O(m*n)$
• Where m is the number of rows of the input matrix grid.
• Where n is the number of columns of the input matrix grid.

References

• LeetCode Problem: LeetCode Problem
• Solution Link: Two Sum Solution on LeetCode