Posted on by Kalkicode
Code Probability

Minimum time required to rot all oranges

The problem of determining the minimum time required to rot all oranges involves finding the shortest time it takes for all the oranges in a given grid to become rotten. In this article, we will provide a step-by-step explanation of the problem and present a Java implementation that solves it efficiently. This solution utilizes a breadth-first search (BFS) algorithm to determine the minimum time required.

Problem Statement:

Given a grid representing a storage area containing fresh oranges (denoted by 1) and rotten oranges (denoted by 2), the task is to find the minimum time it takes for all the fresh oranges to become rotten. Oranges can rot in four directions: up, down, left, and right. Each minute, all the fresh oranges adjacent to the rotten ones will also become rotten. If it is not possible to rot all the fresh oranges, the algorithm should return -1.

Approach and Algorithm:

To solve this problem, we can use a BFS-based approach, which explores the grid in a breadth-first manner. The steps of the algorithm are as follows:

  1. Create a queue to store the positions of the rotten oranges.
  2. Initialize variables for size, time, and temporary row and column values.
  3. Iterate through the grid and add the coordinates of the rotten oranges to the queue.
  4. Execute a loop until the queue is empty:
    • Get the current size of the queue.
    • Set a flag variable (result) to false.
    • Process each orange in the queue by following these steps:
      • Get the position of the current orange from the front of the queue.
      • Check the adjacent oranges in all four directions (up, down, left, right).
      • If an adjacent orange is fresh (denoted by 1), add it to the queue, change its state to rotten (denoted by 2), and set the result flag to true.
    • If the result flag is true, increment the time variable.
  5. After the loop ends, check if there are any remaining fresh oranges in the grid. If so, return -1 (indicating that it is not possible to rot all oranges).
  6. Otherwise, return the total time taken to rot all oranges.

Code Solution

/*
       Java Program for
       Minimum time required to rot all oranges
   */
   
   import java.util.LinkedList;
   
   import java.util.Queue;
   
   class Position
   {
       public int row;
       public int col;
       public Position(int row, int col)
       {
           this.row = row;
           this.col = col;
       }
   }
   public class Timing
   {
       public int minTimeToRot(int[][] mat)
       {
           // Number of row
           int n = mat.length;
           // Number of columns
           int m = mat[0].length;
   
           Queue < Position > queue = new LinkedList <Position> ();
           
           // Define some auxliary variables
           int size = 0;
           int time = 0;
           int tempRow = 0;
           int tempCol = 0;
           boolean result = true;
           
           // Add cordinate of rot oranges
           for (int i = 0; i < n; i++)
           {
               for (int j = 0; j < m; j++)
               {
                   if (mat[i][j] == 2)
                   {
                       queue.add(new Position(i, j));
                   }
               }
           }
           // Execute this loop unit when queue not empty and result is true
           while (!queue.isEmpty() && result == true)
           {
               // Get the size of queue
               size = queue.size();
   
               // Change result
               result = false;
        
   
               // Check of all 4 Direction of rot orange
               // Note size is based on queue size
               for (int i = 0; i < size; i++)
               {
                   // Get queue element
                   Position curr = queue.peek();
   
                
                   // Remove queue element
                   queue.remove();
               
   
                   // Up element adjustment 
                   // Get the position of row and columns
                   tempRow = curr.row - 1;
                   tempCol = curr.col; 
   
                   if ((tempRow >= 0 && tempRow < n) && 
                       (tempCol >= 0 && tempCol < m) && 
                         mat[tempRow][tempCol] == 1)
                   {
                   
                       // Add change coordinate
                       queue.add(new Position(tempRow, tempCol));
   
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       
                       // When change orange
                       result = true;
                
                   }
               
                   // Change row
                   tempRow = curr.row + 1;
                   tempCol = curr.col; 
                   // Down element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       
                       // Change right orange
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
   
                       // Add change cordinate
                       queue.add(new Position(tempRow, tempCol));
                       // When change orange
                       result = true;
                     
                   }
         
                   // Change columns
                   tempRow = curr.row ;
                   tempCol = curr.col + 1;
                   // Right element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.add(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   
                   }
                   // Change row
                   tempRow = curr.row;
                   // Change columns
                   tempCol = curr.col - 1;
                   // Left element
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       
                       // Add change coordinate
                       queue.add(new Position(tempRow, tempCol));
                       // change orange 1 to 2
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                       
                   }
               }
               
               if (result) 
               {
                   time++;
               }
              
           }
   
           for (int i = 0; i < n; i++)
           {
               for (int j = 0; j < m; j++)
               {
                   if (mat[i][j] == 1) 
                   {
                       // In case when orange are not rot
                       return -1;
                   }
               }
           }
           return time;
       }
       public static void main(String[] args)
       {
           Timing t = new Timing();
      
           int [][]mat1 = 
           {
               {
                   0 , 1 , 1, 2
               },
               {
                   0 , 1 , 0, 0
               },
               {
                   0 , 0 , 1, 0
               },
               {
                   0 , 1 , 2, 0
               }
           };
           int [][]mat2 =
           {
               {
                   1 , 0 , 1, 0
               },
               {
                   2 , 0 , 2, 1
               },
               {
                   1 , 0 , 0, 0
               }
           };
           int [][]mat3 =
           {
               {
                   1 , 0 , 1 
               },
               {
                   0 , 2 , 0
               },
               {
                   1 , 0 , 1
               }
           };
           System.out.println("Result mat1 : "+t.minTimeToRot(mat1));
           System.out.println("Result mat2 : "+t.minTimeToRot(mat2));
           System.out.println("Result mat3 : "+t.minTimeToRot(mat3));
       }
   }

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1
// Include header file
   #include <iostream>
   #include <queue>
   #include <vector>
   using namespace std;
   
   class Position
   {
       public: int row;
       int col;
       Position(int row, int col)
       {
           this->row = row;
           this->col = col;
       }
   };
   class Timing
   {
       public: int minTimeToRot(vector<vector<int>> &mat)
       {
           // Number of row
           int n = mat.size();
           // Number of columns
           int m = mat[0].size();
           queue < Position *> queue;
           // Define some auxliary variables
           int size = 0;
           int time = 0;
           int tempRow = 0;
           int tempCol = 0;
           bool result = true;
           // Add cordinate of rot oranges
           for (int i = 0; i < n; i++)
           {
               for (int j = 0; j < m; j++)
               {
                   if (mat[i][j] == 2)
                   {
                       queue.push(new Position(i, j));
                   }
               }
           }
           // Execute this loop unit when queue not empty and result is true
           while (!queue.empty() && result == true)
           {
               // Get the size of queue
               size = queue.size();
               // Change result
               result = false;
               // Check of all 4 Direction of rot orange
               // Note size is based on queue size
               for (int i = 0; i < size; i++)
               {
                   // Get queue element
                   Position *curr = queue.front();
                   // Remove queue element
                   queue.pop();
                   // Up element adjustment 
                   // Get the position of row and columns
                   tempRow = curr->row - 1;
                   tempCol = curr->col;
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.push(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr->row + 1;
                   tempCol = curr->col;
                   // Down element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Change right orange
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // Add change cordinate
                       queue.push(new Position(tempRow, tempCol));
                       // When change orange
                       result = true;
                   }
                   // Change columns
                   tempRow = curr->row;
                   tempCol = curr->col + 1;
                   // Right element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.push(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr->row;
                   // Change columns
                   tempCol = curr->col - 1;
                   // Left element
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.push(new Position(tempRow, tempCol));
                       // change orange 1 to 2
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
               }
               if (result)
               {
                   time++;
               }
           }
           for (int i = 0; i < n; i++)
           {
               for (int j = 0; j < m; j++)
               {
                   if (mat[i][j] == 1)
                   {
                       // In case when orange are not rot
                       return -1;
                   }
               }
           }
           return time;
       }
   };
   int main()
   {
       Timing *t = new Timing();
       vector<vector<int>> mat1{
           {
               0 , 1 , 1 , 2
           } , {
               0 , 1 , 0 , 0
           } , {
               0 , 0 , 1 , 0
           } , {
               0 , 1 , 2 , 0
           }
       };
       vector<vector<int>> mat2{
           {
               1 , 0 , 1 , 0
           } , {
               2 , 0 , 2 , 1
           } , {
               1 , 0 , 0 , 0
           }
       };
       vector<vector<int>> mat3{
           {
               1 , 0 , 1
           } , {
               0 , 2 , 0
           } , {
               1 , 0 , 1
           }
       };
       cout << "Result mat1 : " << t->minTimeToRot(mat1) << endl;
       cout << "Result mat2 : " << t->minTimeToRot(mat2) << endl;
       cout << "Result mat3 : " << t->minTimeToRot(mat3) << endl;
       return 0;
   }

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1
// Include namespace system
   using System;
   using System.Collections.Generic;
   public class Position
   {
       public int row;
       public int col;
       public Position(int row, int col)
       {
           this.row = row;
           this.col = col;
       }
   }
   public class Timing
   {
       public int minTimeToRot(int[,] mat)
       {
           // Number of row
           int n = mat.GetLength(0);
           // Number of columns
           int m = mat.GetLength(1);
           Queue < Position > queue = new Queue < Position > ();
           // Define some auxliary variables
           int size = 0;
           int time = 0;
           int tempRow = 0;
           int tempCol = 0;
           Boolean result = true;
           // Add cordinate of rot oranges
           for (int i = 0; i < n; i++)
           {
               for (int j = 0; j < m; j++)
               {
                   if (mat[i,j] == 2)
                   {
                       queue.Enqueue(new Position(i, j));
                   }
               }
           }
           // Execute this loop unit when queue not empty and result is true
           while ((queue.Count != 0) && result == true)
           {
               // Get the size of queue
               size = queue.Count;
               // Change result
               result = false;
               // Check of all 4 Direction of rot orange
               // Note size is based on queue size
               for (int i = 0; i < size; i++)
               {
                   // Get queue element
                   Position curr = queue.Peek();
                   // Remove queue element
                   queue.Dequeue();
                   // Up element adjustment 
                   // Get the position of row and columns
                   tempRow = curr.row - 1;
                   tempCol = curr.col;
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow,tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.Enqueue(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow,tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row + 1;
                   tempCol = curr.col;
                   // Down element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow,tempCol] == 1)
                   {
                       // Change right orange
                       // Fresh orange to rot orange  
                       mat[tempRow,tempCol] = 2;
                       // Add change cordinate
                       queue.Enqueue(new Position(tempRow, tempCol));
                       // When change orange
                       result = true;
                   }
                   // Change columns
                   tempRow = curr.row;
                   tempCol = curr.col + 1;
                   // Right element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow,tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.Enqueue(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow,tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row;
                   // Change columns
                   tempCol = curr.col - 1;
                   // Left element
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow,tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.Enqueue(new Position(tempRow, tempCol));
                       // change orange 1 to 2
                       // Fresh orange to rot orange  
                       mat[tempRow,tempCol] = 2;
                       // When change orange
                       result = true;
                   }
               }
               if (result)
               {
                   time++;
               }
           }
           for (int i = 0; i < n; i++)
           {
               for (int j = 0; j < m; j++)
               {
                   if (mat[i,j] == 1)
                   {
                       // In case when orange are not rot
                       return -1;
                   }
               }
           }
           return time;
       }
       public static void Main(String[] args)
       {
           Timing t = new Timing();
           int[,] mat1 = {
               {
                   0 , 1 , 1 , 2
               },
               {
                   0 , 1 , 0 , 0
               },
               {
                   0 , 0 , 1 , 0
               },
               {
                   0 , 1 , 2 , 0
               }
           };
           int[,] mat2 = {
               {
                   1 , 0 , 1 , 0
               },
               {
                   2 , 0 , 2 , 1
               },
               {
                   1 , 0 , 0 , 0
               }
           };
           int[,] mat3 = {
               {
                   1 , 0 , 1
               },
               {
                   0 , 2 , 0
               },
               {
                   1 , 0 , 1
               }
           };
           Console.WriteLine("Result mat1 : " + t.minTimeToRot(mat1));
           Console.WriteLine("Result mat2 : " + t.minTimeToRot(mat2));
           Console.WriteLine("Result mat3 : " + t.minTimeToRot(mat3));
       }
   }

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1
<?php
   /*
       Php Program for
       Minimum time required to rot all oranges
   */
   class Position
   {
       public $row;
       public $col;
       public	function __construct($row, $col)
       {
           $this->row = $row;
           $this->col = $col;
       }
   }
   class Timing
   {
       public	function minTimeToRot($mat)
       {
           // Number of row
           $n = count($mat);
           // Number of columns
           $m = count($mat[0]);
           $queue = array();
           // Define some auxliary variables
           $size = 0;
           $time = 0;
           $tempRow = 0;
           $tempCol = 0;
           $result = true;
           // Add cordinate of rot oranges
           for ($i = 0; $i < $n; $i++)
           {
               for ($j = 0; $j < $m; $j++)
               {
                   if ($mat[$i][$j] == 2)
                   {
                       array_unshift($queue, new Position($i, $j));
                   }
               }
           }
           // Execute this loop unit when queue not empty and result is true
           while ((count($queue) > 0) && $result == true)
           {
               // Get the size of queue
               $size = count($queue);
               // Change result
               $result = false;
               // Check of all 4 Direction of rot orange
               // Note size is based on queue size
               for ($i = 0; $i < $size; $i++)
               {
                   // Get queue element
                   $curr = end($queue);
                   // Remove queue element
                   array_pop($queue);
                   // Up element adjustment 
                   // Get the position of row and columns
                   $tempRow = $curr->row - 1;
                   $tempCol = $curr->col;
                   if (($tempRow >= 0 && $tempRow < $n) 
                       && ($tempCol >= 0 && $tempCol < $m) 
                       && $mat[$tempRow][$tempCol] == 1)
                   {
                       // Add change coordinate
                       array_unshift($queue, new Position($tempRow, $tempCol));
                       // Fresh orange to rot orange  
                       $mat[$tempRow][$tempCol] = 2;
                       // When change orange
                       $result = true;
                   }
                   // Change row
                   $tempRow = $curr->row + 1;
                   $tempCol = $curr->col;
                   // Down element adjustment 
                   if (($tempRow >= 0 && $tempRow < $n) 
                       && ($tempCol >= 0 && $tempCol < $m) 
                       && $mat[$tempRow][$tempCol] == 1)
                   {
                       // Change right orange
                       // Fresh orange to rot orange  
                       $mat[$tempRow][$tempCol] = 2;
                       // Add change cordinate
                       array_unshift($queue, new Position($tempRow, $tempCol));
                       // When change orange
                       $result = true;
                   }
                   // Change columns
                   $tempRow = $curr->row;
                   $tempCol = $curr->col + 1;
                   // Right element adjustment 
                   if (($tempRow >= 0 && $tempRow < $n) 
                       && ($tempCol >= 0 && $tempCol < $m) 
                       && $mat[$tempRow][$tempCol] == 1)
                   {
                       // Add change coordinate
                       array_unshift($queue, new Position($tempRow, $tempCol));
                       // Fresh orange to rot orange  
                       $mat[$tempRow][$tempCol] = 2;
                       // When change orange
                       $result = true;
                   }
                   // Change row
                   $tempRow = $curr->row;
                   // Change columns
                   $tempCol = $curr->col - 1;
                   // Left element
                   if (($tempRow >= 0 && $tempRow < $n) 
                       && ($tempCol >= 0 && $tempCol < $m) 
                       && $mat[$tempRow][$tempCol] == 1)
                   {
                       // Add change coordinate
                       array_unshift($queue, new Position($tempRow, $tempCol));
                       // change orange 1 to 2
                       // Fresh orange to rot orange  
                       $mat[$tempRow][$tempCol] = 2;
                       // When change orange
                       $result = true;
                   }
               }
               if ($result)
               {
                   $time++;
               }
           }
           for ($i = 0; $i < $n; $i++)
           {
               for ($j = 0; $j < $m; $j++)
               {
                   if ($mat[$i][$j] == 1)
                   {
                       // In case when orange are not rot
                       return -1;
                   }
               }
           }
           return $time;
       }
   }
   
   function main()
   {
       $t = new Timing();
       $mat1 = array(
         array(0, 1, 1, 2), 
         array(0, 1, 0, 0), 
         array(0, 0, 1, 0), 
         array(0, 1, 2, 0)
       );
       $mat2 = array(
         array(1, 0, 1, 0), 
         array(2, 0, 2, 1), 
         array(1, 0, 0, 0)
       );
       $mat3 = array(
         array(1, 0, 1), 
         array(0, 2, 0),
         array(1, 0, 1)
       );
       echo("Result mat1 : ".$t->minTimeToRot($mat1).
           "\n");
       echo("Result mat2 : ".$t->minTimeToRot($mat2).
           "\n");
       echo("Result mat3 : ".$t->minTimeToRot($mat3).
           "\n");
   }
   main();

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1
class Position
   {
       constructor(row, col)
       {
           this.row = row;
           this.col = col;
       }
   }
   class Timing
   {
       minTimeToRot(mat)
       {
           // Number of row
           var n = mat.length;
           // Number of columns
           var m = mat[0].length;
           var queue = [];
           // Define some auxliary variables
           var size = 0;
           var time = 0;
           var tempRow = 0;
           var tempCol = 0;
           var result = true;
           // Add cordinate of rot oranges
           for (var i = 0; i < n; i++)
           {
               for (var j = 0; j < m; j++)
               {
                   if (mat[i][j] == 2)
                   {
                       queue.push(new Position(i, j));
                   }
               }
           }
           // Execute this loop unit when queue not empty and result is true
           while ((queue.length > 0) && result == true)
           {
               // Get the size of queue
               size = queue.length;
               // Change result
               result = false;
               // Check of all 4 Direction of rot orange
               // Note size is based on queue size
               for (var i = 0; i < size; i++)
               {
                   // Get queue element
                   var curr = queue[0];
                   // Remove queue element
                   queue.shift();
                   // Up element adjustment 
                   // Get the position of row and columns
                   tempRow = curr.row - 1;
                   tempCol = curr.col;
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.push(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row + 1;
                   tempCol = curr.col;
                   // Down element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Change right orange
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // Add change cordinate
                       queue.push(new Position(tempRow, tempCol));
                       // When change orange
                       result = true;
                   }
                   // Change columns
                   tempRow = curr.row;
                   tempCol = curr.col + 1;
                   // Right element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.push(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row;
                   // Change columns
                   tempCol = curr.col - 1;
                   // Left element
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.push(new Position(tempRow, tempCol));
                       // change orange 1 to 2
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
               }
               if (result)
               {
                   time++;
               }
           }
           for (var i = 0; i < n; i++)
           {
               for (var j = 0; j < m; j++)
               {
                   if (mat[i][j] == 1)
                   {
                       // In case when orange are not rot
                       return -1;
                   }
               }
           }
           return time;
       }
   }
   
   function main()
   {
       var t = new Timing();
       var mat1 = [
           [0, 1, 1, 2],
           [0, 1, 0, 0],
           [0, 0, 1, 0],
           [0, 1, 2, 0]
       ];
       var mat2 = [
           [1, 0, 1, 0],
           [2, 0, 2, 1],
           [1, 0, 0, 0]
       ];
       var mat3 = [
           [1, 0, 1],
           [0, 2, 0],
           [1, 0, 1]
       ];
       console.log("Result mat1 : " + t.minTimeToRot(mat1));
       console.log("Result mat2 : " + t.minTimeToRot(mat2));
       console.log("Result mat3 : " + t.minTimeToRot(mat3));
   }
   main();

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1
#    Python 3 Program for
   #    Minimum time required to rot all oranges
   class Position :
       def __init__(self, row, col) :
           self.row = row
           self.col = col
   
   class Timing :
       def minTimeToRot(self, mat) :
           #  Number of row
           n = len(mat)
           #  Number of columns
           m = len(mat[0])
           queue = []
           #  Define some auxliary variables
           size = 0
           time = 0
           tempRow = 0
           tempCol = 0
           result = True
           i = 0
           #  Add cordinate of rot oranges
           while (i < n) :
               j = 0
               while (j < m) :
                   if (mat[i][j] == 2) :
                       queue.append(Position(i, j))
                   
                   j += 1
               
               i += 1
           
           #  Execute this loop unit when queue not empty and result is true
           while ((len(queue) > 0) and result == True) :
               #  Get the size of queue
               size = len(queue)
               #  Change result
               result = False
               i = 0
               #  Check of all 4 Direction of rot orange
               #  Note size is based on queue size
               while (i < size and len(queue) > 0) :
                   #  Get queue element
                   curr = queue[0]
                   #  Remove queue element
                   queue.pop(0)
                   #  Up element adjustment 
                   #  Get the position of row and columns
                   tempRow = curr.row - 1
                   tempCol = curr.col
                   if ((tempRow >= 0 and tempRow < n) and 
                       (tempCol >= 0 and tempCol < m) and 
                       mat[tempRow][tempCol] == 1) :
                       #  Add change coordinate
                       queue.append(Position(tempRow, tempCol))
                       #  Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2
                       #  When change orange
                       result = True
                   
                   #  Change row
                   tempRow = curr.row + 1
                   tempCol = curr.col
                   #  Down element adjustment 
                   if ((tempRow >= 0 and tempRow < n) and 
                       (tempCol >= 0 and tempCol < m) and 
                       mat[tempRow][tempCol] == 1) :
                       #  Change right orange
                       #  Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2
                       #  Add change cordinate
                       queue.append(Position(tempRow, tempCol))
                       #  When change orange
                       result = True
                   
                   #  Change columns
                   tempRow = curr.row
                   tempCol = curr.col + 1
                   #  Right element adjustment 
                   if ((tempRow >= 0 and tempRow < n) and 
                       (tempCol >= 0 and tempCol < m) and 
                       mat[tempRow][tempCol] == 1) :
                       #  Add change coordinate
                       queue.append(Position(tempRow, tempCol))
                       #  Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2
                       #  When change orange
                       result = True
                   
                   #  Change row
                   tempRow = curr.row
                   #  Change columns
                   tempCol = curr.col - 1
                   #  Left element
                   if ((tempRow >= 0 and tempRow < n) and 
                       (tempCol >= 0 and tempCol < m) and 
                       mat[tempRow][tempCol] == 1) :
                       #  Add change coordinate
                       queue.append(Position(tempRow, tempCol))
                       #  change orange 1 to 2
                       #  Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2
                       #  When change orange
                       result = True
                   
                   i += 1
               
               if (result) :
                   time += 1
               
           
           i = 0
           while (i < n) :
               j = 0
               while (j < m) :
                   if (mat[i][j] == 1) :
                       #  In case when orange are not rot
                       return -1
                   
                   j += 1
               
               i += 1
           
           return time
       
   
   def main() :
       t = Timing()
       mat1 = [
           [0, 1, 1, 2],
           [0, 1, 0, 0],
           [0, 0, 1, 0],
           [0, 1, 2, 0]
       ]
       mat2 = [
           [1, 0, 1, 0],
           [2, 0, 2, 1],
           [1, 0, 0, 0]
       ]
       mat3 = [
           [1, 0, 1],
           [0, 2, 0],
           [1, 0, 1]
       ]
       print("Result mat1 : ", t.minTimeToRot(mat1))
       print("Result mat2 : ", t.minTimeToRot(mat2))
       print("Result mat3 : ", t.minTimeToRot(mat3))
   
   if __name__ == "__main__": main()

Output

Result mat1 :  3
   Result mat2 :  1
   Result mat3 :  -1
#    Ruby Program for
   #    Minimum time required to rot all oranges
   class Position 
       # Define the accessor and reader of class Position
       attr_reader :row, :col
       attr_accessor :row, :col
       def initialize(row, col) 
           self.row = row
           self.col = col
       end
   end
   
   class Timing 
       def minTimeToRot(mat) 
           #  Number of row
           n = mat.length
           #  Number of columns
           m = mat[0].length
   
           record = []
           #  Define some auxliary variables
           size = 0
           times = 0
           tempRow = 0
           tempCol = 0
           result = true
           i = 0
           #  Add cordinate of rot oranges
           while (i < n) 
               j = 0
               while (j < m) 
                   if (mat[i][j] == 2) 
                       record.push(Position.new(i, j))
                   end
   
                   j += 1
               end
   
               i += 1
           end
   
           #  Execute this loop unit when record not empty and result is true
           while ((record.length > 0) && result == true) 
               #  Get the size of record
               size = record.length
   
               #  Change result
               result = false
               i = 0
               #  Check of all 4 Direction of rot orange
               #  Note size is based on record size
               while (i < size && record.length > 0) 
                   #  Get record element
                   curr = record.first()
                   x = curr.row
                   y = curr.col
                   #  Remove record element
                   record = record.drop(1)
                   #  Up element adjustment 
                   #  Get the position of row and columns
                   tempRow = x - 1
                   tempCol = y
                   if ((tempRow >= 0 && tempRow < n)  && 
                       (tempCol >= 0 && tempCol < m) && 
                       (mat[tempRow][tempCol] == 1)) 
                       #  Add change coordinate
                       record.push(Position.new(tempRow, tempCol))
                       #  Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2
                       #  When change orange
                       result = true
                   end
   
                   #  Change row
                   tempRow = x + 1
                   tempCol = y
                   #  Down element adjustment 
                   if ((tempRow >= 0 && tempRow < n) &&  
                       (tempCol >= 0 && tempCol < m) && 
                       (mat[tempRow][tempCol] == 1) ) 
                       #  Change right orange
                       #  Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2
                       #  Add change cordinate
                       record.push(Position.new(tempRow, tempCol))
                       #  When change orange
                       result = true
                   end
   
                   #  Change columns
                   tempRow = x
                   tempCol = y + 1
                   #  Right element adjustment 
                   if ((tempRow >= 0 && tempRow < n) &&  
                       (tempCol >= 0 && tempCol < m) && 
                       (mat[tempRow][tempCol] == 1) ) 
                       #  Add change coordinate
                       record.push(Position.new(tempRow, tempCol))
                       #  Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2
                       #  When change orange
                       result = true
                   end
   
                   #  Change row
                   tempRow = x
                   #  Change columns
                   tempCol = y - 1
                   #  Left element
                   if ((tempRow >= 0 && tempRow < n) && 
                       (mat[tempRow][tempCol] == 1) && 
                       (tempCol >= 0 && tempCol < m) ) 
                       #  Add change coordinate
                       record.push(Position.new(tempRow, tempCol))
                       #  change orange 1 to 2
                       #  Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2
                       #  When change orange
                       result = true
                   end
   
                   i += 1
               end
   
               if (result) 
                   times = times + 1
               end
   
           end
   
           i = 0
           while (i < n) 
               j = 0
               while (j < m) 
                   if (mat[i][j] == 1) 
                       #  In case when orange are not rot
                       return -1
                   end
   
                   j += 1
               end
   
               i += 1
           end
   
           return times
       end
   
   end
   
   def main() 
       t = Timing.new()
       mat1 = [
           [0, 1, 1, 2],
           [0, 1, 0, 0],
           [0, 0, 1, 0],
           [0, 1, 2, 0]
       ]
       mat2 = [
           [1, 0, 1, 0],
           [2, 0, 2, 1],
           [1, 0, 0, 0]
       ]
       mat3 = [
           [1, 0, 1],
           [0, 2, 0],
           [1, 0, 1]
       ]
       print("Result mat1 : ", t.minTimeToRot(mat1), "\n")
       print("Result mat2 : ", t.minTimeToRot(mat2), "\n")
       print("Result mat3 : ", t.minTimeToRot(mat3), "\n")
   end
   
   main()

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1
   
import scala.collection.mutable._;
   /*
       Scala Program for
       Minimum time required to rot all oranges
   */
   class Position(var row: Int,
       var col: Int)
   {
   
   }
   class Timing()
   {
       def minTimeToRot(mat: Array[Array[Int]]): Int = {
           // Number of row
           var n: Int = mat.length;
           // Number of columns
           var m: Int = mat(0).length;
           var queue: Queue[Position] = new Queue[Position]();
           // Define some auxliary variables
           var size: Int = 0;
           var time: Int = 0;
           var tempRow: Int = 0;
           var tempCol: Int = 0;
           var result: Boolean = true;
           var i: Int = 0;
           // Add cordinate of rot oranges
           while (i < n)
           {
               var j: Int = 0;
               while (j < m)
               {
                   if (mat(i)(j) == 2)
                   {
                       queue.enqueue(new Position(i, j));
                   }
                   j += 1;
               }
               i += 1;
           }
           // Execute this loop unit when queue not empty and result is true
           while (!queue.isEmpty && result == true)
           {
               // Get the size of queue
               size = queue.size;
               // Change result
               result = false;
               i = 0;
               // Check of all 4 Direction of rot orange
               // Note size is based on queue size
               while (i < size)
               {
                   // Get queue element
                   var curr: Position = queue.front;
                   // Remove queue element
                   queue.dequeue;
                   // Up element adjustment 
                   // Get the position of row and columns
                   tempRow = curr.row - 1;
                   tempCol = curr.col;
                   if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
                   {
                       // Add change coordinate
                       queue.enqueue(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat(tempRow)(tempCol) = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row + 1;
                   tempCol = curr.col;
                   // Down element adjustment 
                   if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
                   {
                       // Change right orange
                       // Fresh orange to rot orange  
                       mat(tempRow)(tempCol) = 2;
                       // Add change cordinate
                       queue.enqueue(new Position(tempRow, tempCol));
                       // When change orange
                       result = true;
                   }
                   // Change columns
                   tempRow = curr.row;
                   tempCol = curr.col + 1;
                   // Right element adjustment 
                   if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
                   {
                       // Add change coordinate
                       queue.enqueue(new Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat(tempRow)(tempCol) = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row;
                   // Change columns
                   tempCol = curr.col - 1;
                   // Left element
                   if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
                   {
                       // Add change coordinate
                       queue.enqueue(new Position(tempRow, tempCol));
                       // change orange 1 to 2
                       // Fresh orange to rot orange  
                       mat(tempRow)(tempCol) = 2;
                       // When change orange
                       result = true;
                   }
                   i += 1;
               }
               if (result)
               {
                   time += 1;
               }
           }
           i = 0;
           while (i < n)
           {
               var j: Int = 0;
               while (j < m)
               {
                   if (mat(i)(j) == 1)
                   {
                       // In case when orange are not rot
                       return -1;
                   }
                   j += 1;
               }
               i += 1;
           }
           return time;
       }
   }
   object Main
   {
       def main(args: Array[String]): Unit = {
           var t: Timing = new Timing();
           var mat1: Array[Array[Int]] = Array(
             Array(0, 1, 1, 2), 
             Array(0, 1, 0, 0), 
             Array(0, 0, 1, 0), 
             Array(0, 1, 2, 0)
           );
           var mat2: Array[Array[Int]] = Array(
             Array(1, 0, 1, 0), 
             Array(2, 0, 2, 1), 
             Array(1, 0, 0, 0)
           );
           var mat3: Array[Array[Int]] = Array(
             Array(1, 0, 1), 
             Array(0, 2, 0), 
             Array(1, 0, 1)
           );
           println("Result mat1 : " + t.minTimeToRot(mat1));
           println("Result mat2 : " + t.minTimeToRot(mat2));
           println("Result mat3 : " + t.minTimeToRot(mat3));
       }
   }

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1
import Foundation;
   /*
       Swift 4 Program for
       Minimum time required to rot all oranges
   */
   class Position
   {
       var row: Int;
       var col: Int;
       init(_ row: Int, _ col: Int)
       {
           self.row = row;
           self.col = col;
       }
   }
   class Timing
   {
       func minTimeToRot(_ mat: inout[[Int]]) -> Int
       {
           // Number of row
           let n: Int = mat.count;
           // Number of columns
           let m: Int = mat[0].count;
           var queue = [Position]();
           // Define some auxliary variables
           var size: Int = 0;
           var time: Int = 0;
           var tempRow: Int = 0;
           var tempCol: Int = 0;
           var result: Bool = true;
           var i: Int = 0;
           // Add cordinate of rot oranges
           while (i < n)
           {
               var j: Int = 0;
               while (j < m)
               {
                   if (mat[i][j] == 2)
                   {
                       queue.append(Position(i, j));
                   }
                   j += 1;
               }
               i += 1;
           }
           // Execute this loop unit when queue not empty and result is true
           while ((queue.count > 0) && result == true)
           {
               // Get the size of queue
               size = queue.count;
               // Change result
               result = false;
               i  = 0;
               // Check of all 4 Direction of rot orange
               // Note size is based on queue size
               while (i < size)
               {
                   // Get queue element
                   let curr: Position = queue[0];
                   // Remove queue element
                   queue.removeFirst();
                   // Up element adjustment 
                   // Get the position of row and columns
                   tempRow = curr.row - 1;
                   tempCol = curr.col;
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.append(Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row + 1;
                   tempCol = curr.col;
                   // Down element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Change right orange
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // Add change cordinate
                       queue.append(Position(tempRow, tempCol));
                       // When change orange
                       result = true;
                   }
                   // Change columns
                   tempRow = curr.row;
                   tempCol = curr.col + 1;
                   // Right element adjustment 
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.append(Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row;
                   // Change columns
                   tempCol = curr.col - 1;
                   // Left element
                   if ((tempRow >= 0 && tempRow < n) 
                       && (tempCol >= 0 && tempCol < m) 
                       && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.append(Position(tempRow, tempCol));
                       // change orange 1 to 2
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   i += 1;
               }
               if (result)
               {
                   time += 1;
               }
           }
           i = 0;
           while (i < n)
           {
               var j: Int = 0;
               while (j < m)
               {
                   if (mat[i][j] == 1)
                   {
                       // In case when orange are not rot
                       return -1;
                   }
                   j += 1;
               }
               i += 1;
           }
           return time;
       }
   }
   func main()
   {
       let t: Timing = Timing();
       var mat1: [
           [Int]
       ] = [
           [0, 1, 1, 2],
           [0, 1, 0, 0],
           [0, 0, 1, 0],
           [0, 1, 2, 0]
       ];
       var mat2: [
           [Int]
       ] = [
           [1, 0, 1, 0],
           [2, 0, 2, 1],
           [1, 0, 0, 0]
       ];
       var mat3: [
           [Int]
       ] = [
           [1, 0, 1],
           [0, 2, 0],
           [1, 0, 1]
       ];
       print("Result mat1 : ", t.minTimeToRot(&mat1));
       print("Result mat2 : ", t.minTimeToRot(&mat2));
       print("Result mat3 : ", t.minTimeToRot(&mat3));
   }
   main();

Output

Result mat1 :  3
   Result mat2 :  1
   Result mat3 :  -1
/*
       Kotlin Program for
       Minimum time required to rot all oranges
   */
   import java.util.Queue
   import java.util.LinkedList
   class Position
   {
       var row: Int;
       var col: Int;
       constructor(row: Int, col: Int)
       {
           this.row = row;
           this.col = col;
       }
   }
   class Timing
   {
       fun minTimeToRot(mat: Array < Array < Int >> ): Int
       {
           // Number of row
           val n: Int = mat.count();
           // Number of columns
           val m: Int = mat[0].count();
           var queue: Queue < Position > = LinkedList < Position > ();
           // Define some auxliary variables
           var size: Int ;
           var time: Int = 0;
           var tempRow: Int;
           var tempCol: Int ;
           var result: Boolean = true;
           var i: Int = 0;
           // Add cordinate of rot oranges
           while (i < n)
           {
               var j: Int = 0;
               while (j < m)
               {
                   if (mat[i][j] == 2)
                   {
                       queue.add(Position(i, j));
                   }
                   j += 1;
               }
               i += 1;
           }
           // Execute this loop unit when queue not empty and result is true
           while (!queue.isEmpty() && result == true)
           {
               // Get the size of queue
               size = queue.size;
               // Change result
               result = false;
               i = 0;
               // Check of all 4 Direction of rot orange
               // Note size is based on queue size
               while (i < size)
               {
                   // Get queue element
                   val curr: Position = queue.peek();
                   // Remove queue element
                   queue.remove();
                   // Up element adjustment 
                   // Get the position of row and columns
                   tempRow = curr.row - 1;
                   tempCol = curr.col;
                   if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.add(Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row + 1;
                   tempCol = curr.col;
                   // Down element adjustment 
                   if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
                   {
                       // Change right orange
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // Add change cordinate
                       queue.add(Position(tempRow, tempCol));
                       // When change orange
                       result = true;
                   }
                   // Change columns
                   tempRow = curr.row;
                   tempCol = curr.col + 1;
                   // Right element adjustment 
                   if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.add(Position(tempRow, tempCol));
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   // Change row
                   tempRow = curr.row;
                   // Change columns
                   tempCol = curr.col - 1;
                   // Left element
                   if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
                   {
                       // Add change coordinate
                       queue.add(Position(tempRow, tempCol));
                       // change orange 1 to 2
                       // Fresh orange to rot orange  
                       mat[tempRow][tempCol] = 2;
                       // When change orange
                       result = true;
                   }
                   i += 1;
               }
               if (result)
               {
                   time += 1;
               }
           }
           i = 0;
           while (i < n)
           {
               var j: Int = 0;
               while (j < m)
               {
                   if (mat[i][j] == 1)
                   {
                       // In case when orange are not rot
                       return -1;
                   }
                   j += 1;
               }
               i += 1;
           }
           return time;
       }
   }
   fun main(args: Array < String > ): Unit
   {
       val t: Timing = Timing();
       val mat1: Array < Array < Int >> = arrayOf(arrayOf(0, 1, 1, 2), arrayOf(0, 1, 0, 0), arrayOf(0, 0, 1, 0), arrayOf(0, 1, 2, 0));
       val mat2: Array < Array < Int >> = arrayOf(arrayOf(1, 0, 1, 0), arrayOf(2, 0, 2, 1), arrayOf(1, 0, 0, 0));
       val mat3: Array < Array < Int >> = arrayOf(arrayOf(1, 0, 1), arrayOf(0, 2, 0), arrayOf(1, 0, 1));
       println("Result mat1 : " + t.minTimeToRot(mat1));
       println("Result mat2 : " + t.minTimeToRot(mat2));
       println("Result mat3 : " + t.minTimeToRot(mat3));
   }

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1
package main
   import "fmt"
   /*
       Go Program for
       Minimum time required to rot all oranges
   */
   type Position struct {
       row int
       col int
   }
   func getPosition(row int, col int) * Position {
       var me * Position = & Position {}
       me.row = row
       me.col = col
       return me
   }
   type Timing struct {}
   func getTiming() * Timing {
       var me * Timing = & Timing {}
       return me
   }
   func(this Timing) minTimeToRot(mat[][] int) int {
       // Number of row
       var n int = len(mat)
       // Number of columns
       var m int = len(mat[0])
       var queue[] * Position
       // Define some auxliary variables
       var size int = 0
       var time int = 0
       var tempRow int = 0
       var tempCol int = 0
       var result bool = true
       // Add cordinate of rot oranges
       for i:= 0; i < n; i++{
           for j:= 0;j < m;j++{
               if mat[i][j] == 2 {
                   queue = append(queue, getPosition(i, j))
               }
           }
       }
       // Execute this loop unit when queue not empty and result is true
       for ((len(queue) > 0) && result == true) {
           // Get the size of queue
           size = len(queue)
           // Change result
           result = false
           // Check of all 4 Direction of rot orange
           // Note size is based on queue size
           for i:= 0 ; i < size; i++{
               // Get queue element
               var curr * Position = queue[0]
               // Remove queue element
               queue = queue[1: ]
               // Up element adjustment 
               // Get the position of row and columns
               tempRow = curr.row - 1
               tempCol = curr.col
               if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
                   // Add change coordinate
                   queue = append(queue, getPosition(tempRow, tempCol))
                   // Fresh orange to rot orange  
                   mat[tempRow][tempCol] = 2
                   // When change orange
                   result = true
               }
               // Change row
               tempRow = curr.row + 1
               tempCol = curr.col
               // Down element adjustment 
               if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
                   // Change right orange
                   // Fresh orange to rot orange  
                   mat[tempRow][tempCol] = 2
                   // Add change cordinate
                   queue = append(queue, getPosition(tempRow, tempCol))
                   // When change orange
                   result = true
               }
               // Change columns
               tempRow = curr.row
               tempCol = curr.col + 1
               // Right element adjustment 
               if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
                   // Add change coordinate
                   queue = append(queue, getPosition(tempRow, tempCol))
                   // Fresh orange to rot orange  
                   mat[tempRow][tempCol] = 2
                   // When change orange
                   result = true
               }
               // Change row
               tempRow = curr.row
               // Change columns
               tempCol = curr.col - 1
               // Left element
               if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
                   // Add change coordinate
                   queue = append(queue, getPosition(tempRow, tempCol))
                   // change orange 1 to 2
                   // Fresh orange to rot orange  
                   mat[tempRow][tempCol] = 2
                   // When change orange
                   result = true
               }
           }
           if result {
               time++
           }
       }
       for i:= 0; i < n; i++{
           for j:= 0; j < m; j++{
               if mat[i][j] == 1 {
                   // In case when orange are not rot
                   return -1
               }
           }
       }
       return time
   }
   func main() {
       var t * Timing = getTiming()
       var mat1 = [][] int {
           {
               0,
               1,
               1,
               2,
           }, {
               0,
               1,
               0,
               0,
           }, {
               0,
               0,
               1,
               0,
           }, {
               0,
               1,
               2,
               0,
           },
       }
       var mat2 = [][] int {
           {
               1,
               0,
               1,
               0,
           }, {
               2,
               0,
               2,
               1,
           }, {
               1,
               0,
               0,
               0,
           },
       }
       var mat3 = [][] int {
           {
               1,
               0,
               1,
           }, {
               0,
               2,
               0,
           }, {
               1,
               0,
               1,
           },
       }
       fmt.Println("Result mat1 : ", t.minTimeToRot(mat1))
       fmt.Println("Result mat2 : ", t.minTimeToRot(mat2))
       fmt.Println("Result mat3 : ", t.minTimeToRot(mat3))
   }

Output

Result mat1 : 3
   Result mat2 : 1
   Result mat3 : -1

The time complexity of the above code is O(N * M), where N is the number of rows in the grid and M is the number of columns.

Explanation:

  1. Adding Rotten Oranges to the Queue:

    • In the worst case, all elements in the grid can be rotten oranges, resulting in a total of N * M elements being added to the queue.
    • This process has a time complexity of O(N * M).
  2. Performing BFS:

    • The while loop executes as long as the queue is not empty.
    • In each iteration, we process the oranges in the queue, which is determined by the size of the queue at the beginning of the iteration.
    • The maximum number of elements that can be present in the queue is N * M (all the oranges in the grid).
    • Thus, the while loop can execute a maximum of N * M times in the worst case.
    • Inside the loop, we perform constant time operations (adding coordinates to the queue, changing orange states, updating flags).
    • Therefore, the time complexity of the while loop is O(N * M).
  3. Checking Remaining Fresh Oranges:

    • After the BFS loop, we iterate through the entire grid once to check if there are any remaining fresh oranges.
    • This iteration has a time complexity of O(N * M) since we need to check each element in the grid.

Overall, the time complexity of the code is dominated by the BFS loop, resulting in a total time complexity of O(N * M).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment