Maximum time required for all patients to get infected
Given a matrix arr[][], consisting of only 0, 1, and 2, that represents an empty ward, an uninfected patient, and an infected patient respectively. In one unit of time, an infected person at index (i, j) can infect an uninfected person adjacent to it i.e., at index (i – 1, j), (i + 1, j), (i, j – 1), and (i, j + 1). The task is to find the minimum amount of time required to infect all the patients. If it is impossible to infect all the patients, then print “-1”.
Examples:
Input: arr[][] = {{2, 1, 0, 2, 1}, {1, 0, 1, 2, 1}, {1, 0, 0, 2, 1}}
Output: 2
Explanation:
At time t = 1: The patients at positions {0, 0}, {0, 3}, {1, 3} and {2, 3} will infect patient at {{0, 1}, {1, 0}, {0, 4}, {1, 2}, {1, 4}, {2, 4}} during 1st unit time.
At time t = 2: The patient at {1, 0} will get infected and will infect patient at {2, 0}.After the above time intervals all the uninfected patients are infected. Therefore, the total amount of time required is 2.
Input: arr[][] = {{2, 1, 0, 2, 1}, {0, 0, 1, 2, 1}, {1, 0, 0, 2, 1}}
Output: -1
Approach: The given problem can be solved by using BFS Traversal on the 2D matrix. Follow the steps below to solve the given problem:
- Initialize a 2D array, say timeofinfection[][] with -1, such that timeofinfection[i][j] stores the time when the patient at index (i, j) was infected.
- Initialize a queue to store indices of infected patients and their time of infection.
- Traverse the given matrix arr[][] and perform the following operations:
- If the value at cell (i, j) is 2, then push that cell into the queue with the time of infection as 0 i.e., {i, j, 0}.
- Iterate until the queue is non-empty and perform the following steps:
- Pop the front element of the queue and store it in a variable, say current.
- From the current popped cell (i, j), if the adjacent cell has an infected person which is unvisited, then push the index of the adjacent cell with (1 + time of infection of the current popped cell) into the queue.
- After completing the above steps, if all the infected persons are visited, i.e. the time of infection of all the infected persons is non-negative, then print the maximum element present in the matrix timeofinfection[][] as the maximum unit of time required to infect all the patients.
- Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Direction arrays vector<pair< int , int > > direction = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } }; // Function to find the maximum time // required for all patients to get infected int maximumTime(vector<vector< int > > arr) { // Stores the number of rows int n = arr.size(); // Stores the number of columns int m = arr[0].size(); // Stores the time of infection // of the patient at index (i, j) int timeofinfection[n][m]; // Stores index and time of // infection of infected persons queue<pair<pair< int , int >, int > > q; // Traverse the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // Set the cell as unvisited timeofinfection[i][j] = -1; // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index and time of // infection of current patient q.push({ { i, j }, 0 }); timeofinfection[i][j] = 0; } } } // Iterate until queue becomes empty while (!q.empty()) { // Stores the front element of queue pair<pair< int , int >, int > current = q.front(); // Pop out the front element q.pop(); // Check for all four // adjacent indices for ( auto it : direction) { // Find the index of the // adjacent cell int i = current.first.first + it.first; int j = current.first.second + it.second; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || timeofinfection[i][j] != -1) { // Continue to the next // neighbouring cell continue ; } // Push the infected // neighbour into queue q.push({ { i, j }, current.second + 1 }); timeofinfection[i][j] = current.second + 1; } } // Stores the maximum time int maxi = INT_MIN; // Stores if any uninfected // patient exists or not int flag = 0; // Traverse the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // If no patient is // present at index (i, j) if (arr[i][j] != 1) continue ; // If an uninfected patient // is present at index (i, j) if (arr[i][j] == 1 && timeofinfection[i][j] == -1) { // Set flag as true flag = 1; break ; } // Update the maximum time of infection maxi = max(maxi, timeofinfection[i][j]); } } // If an uninfected patient is present if (flag) return -1; // Return the final result return maxi; } // Driver Code int main() { vector<vector< int > > arr = { { 2, 1, 0, 2, 1 }, { 1, 0, 1, 2, 1 }, { 1, 0, 0, 2, 1 } }; cout << maximumTime(arr); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { static class pair { int first, second, third; pair( int first, int second, int third) { this .first = first; this .second = second; this .third = third; } } // Direction arrays static int [][] direction = { { 1 , 0 }, { 0 , - 1 }, { - 1 , 0 }, { 0 , 1 } }; // Function to find the maximum time // required for all patients to get infected static int maximumTime( int [][] arr) { // Stores the number of rows int n = arr.length; // Stores the number of columns int m = arr[ 0 ].length; // Stores the time of infection // of the patient at index (i, j) int [][] timeofinfection = new int [n][m]; // Stores index and time of // infection of infected persons Queue<pair> q = new LinkedList<>(); // Traverse the matrix for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { // Set the cell as unvisited timeofinfection[i][j] = - 1 ; // If the current patient // is already infected if (arr[i][j] == 2 ) { // Push the index and time of // infection of current patient q.add( new pair(i, j, 0 )); timeofinfection[i][j] = 0 ; } } } // Iterate until queue becomes empty while (!q.isEmpty()) { // Stores the front element of queue pair current = q.peek(); // Pop out the front element q.poll(); // Check for all four // adjacent indices for ( int [] it : direction) { // Find the index of the // adjacent cell int i = current.first + it[ 0 ]; int j = current.second + it[ 1 ]; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || timeofinfection[i][j] != - 1 ) { // Continue to the next // neighbouring cell continue ; } // Push the infected // neighbour into queue q.add( new pair(i, j , current.second + 1 )); timeofinfection[i][j] = current.third + 1 ; } } // Stores the maximum time int maxi = Integer.MIN_VALUE; // Stores if any uninfected // patient exists or not int flag = 0 ; // Traverse the matrix for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { // If no patient is // present at index (i, j) if (arr[i][j] != 1 ) continue ; // If an uninfected patient // is present at index (i, j) if (arr[i][j] == 1 && timeofinfection[i][j] == - 1 ) { // Set flag as true flag = 1 ; break ; } // Update the maximum time of infection maxi = Math.max(maxi, timeofinfection[i][j]); } } // If an uninfected patient is present if (flag == 1 ) return - 1 ; // Return the final result return maxi; } // Driver code public static void main(String[] args) { int [][] arr = { { 2 , 1 , 0 , 2 , 1 }, { 1 , 0 , 1 , 2 , 1 }, { 1 , 0 , 0 , 2 , 1 } }; System.out.print(maximumTime(arr)); } } // This code is contributed by offbeat |
Javascript
<script> // JavaScript program for the above approach // Direction arrays var direction = [ [ 1, 0 ], [ 0, -1 ], [ -1, 0 ], [ 0, 1 ] ]; // Function to find the maximum time // required for all patients to get infected function maximumTime(arr) { // Stores the number of rows var n = arr.length; // Stores the number of columns var m = arr[0].length; // Stores the time of infection // of the patient at index (i, j) var timeofinfection = Array.from(Array(n), ()=>Array(m)); // Stores index and time of // infection of infected persons var q = []; // Traverse the matrix for ( var i = 0; i < n; i++) { for ( var j = 0; j < m; j++) { // Set the cell as unvisited timeofinfection[i][j] = -1; // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index and time of // infection of current patient q.push([ [ i, j ], 0 ]); timeofinfection[i][j] = 0; } } } // Iterate until queue becomes empty while (q.length!=0) { // Stores the front element of queue var current = q[0]; // Pop out the front element q.shift(); // Check for all four // adjacent indices for ( var it of direction) { // Find the index of the // adjacent cell var i = current[0][0] + it[0]; var j = current[0][1] + it[1]; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || timeofinfection[i][j] != -1) { // Continue to the next // neighbouring cell continue ; } // Push the infected // neighbour into queue q.push([[i, j], current[1] + 1 ]); timeofinfection[i][j] = current[1] + 1; } } // Stores the maximum time var maxi = -1000000000; // Stores if any uninfected // patient exists or not var flag = 0; // Traverse the matrix for ( var i = 0; i < n; i++) { for ( var j = 0; j < m; j++) { // If no patient is // present at index (i, j) if (arr[i][j] != 1) continue ; // If an uninfected patient // is present at index (i, j) if (arr[i][j] == 1 && timeofinfection[i][j] == -1) { // Set flag as true flag = 1; break ; } // Update the maximum time of infection maxi = Math.max(maxi, timeofinfection[i][j]); } } // If an uninfected patient is present if (flag) return -1; // Return the final result return maxi; } // Driver Code var arr = [ [ 2, 1, 0, 2, 1 ], [ 1, 0, 1, 2, 1 ], [ 1, 0, 0, 2, 1 ] ]; document.write( maximumTime(arr)); </script> |
Python
# function to traverse to nearby possible directions def bfs(i, j, mat, time): # marking position as visited mat[i][j] = 0 # stack to store positions that got infected in one unit time stack = [] # direction arrays row = [ - 1 , 0 , 0 , 1 ] col = [ 0 , - 1 , 1 , 0 ] # traversing to nearby uninfected beds for k in range ( 4 ): x = i + row[k] y = j + col[k] if x > = 0 and x < r and y > = 0 and y < c and mat[x][y] = = 1 : mat[x][y] = 0 stack.append((x, y)) # storing the time at which the patient got infected time[x][y] = time[i][j] + 1 return stack # function to calculate maximum time def maxTime(hospital): # array to store the time at which the patients got infected time = [[ 0 for i in range (c)] for j in range (r)] # to store newly infected ones que = [] # initial run for i in range (r): for j in range (c): if hospital[i][j] = = 2 : que + = bfs(i, j, hospital, time) # iterate till every infected patient has done spreading while ( len (que) ! = 0 ): for x, y in que: temp = bfs(x, y, hospital, time) que = temp # finally calculating maximum time res = 0 for i in range (r): for j in range (c): # checking if there is any uninfected person if hospital[i][j] = = 1 : return - 1 res = max (res, time[i][j]) return res # Driver Code Starts hospital = [[ 2 , 1 , 0 , 2 , 1 ], [ 1 , 0 , 1 , 2 , 1 ], [ 1 , 0 , 0 , 2 , 1 ]] r = len (hospital) c = len (hospital[ 0 ]) print (maxTime(hospital)) # Driver Code Ends |
C#
using System; using System.Collections.Generic; class GFG { public class pair { public int first; public int second; public int third; public pair( int first, int second, int third) { this .first = first; this .second = second; this .third = third; } } // Direction arrays static int [][] direction = { new int [] { 1, 0 }, new int [] { 0, -1 }, new int [] { -1, 0 }, new int [] { 0, 1 } }; // Function to find the maximum time // required for all patients to get infected static int maximumTime( int [][] arr) { // Stores the number of rows int n = arr.Length; // Stores the number of columns int m = arr[0].Length; // Stores the time of infection // of the patient at index (i, j) int [][] timeofinfection = new int [n][]; for ( int i = 0; i < n; i++) timeofinfection[i] = new int [m]; // Stores index and time of // infection of infected persons Queue<pair> q = new Queue<pair>(); // Traverse the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // Set the cell as unvisited timeofinfection[i][j] = -1; // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index and time of // infection of current patient q.Enqueue( new pair(i, j, 0)); timeofinfection[i][j] = 0; } } } // Iterate until queue becomes empty while (q.Count != 0) { // Stores the front element of queue pair current = q.Peek(); // Pop out the front element q.Dequeue(); // Check for all four // adjacent indices foreach ( int [] it in direction) { // Find the index of the // adjacent cell int i = current.first + it[0]; int j = current.second + it[1]; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || timeofinfection[i][j] != -1) { // Continue to the next // neighbouring cell continue ; } // Push the infected // patient into queue q.Enqueue( new pair(i, j, current.second + 1)); timeofinfection[i][j] = current.third + 1; } } // Stores the maximum time int maxi = int .MinValue; // Stores if any uninfected // patient exists or not int flag = 0; // Traverse the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // If no patient is // present at index (i, j) if (arr[i][j] != 1) continue ; // If an uninfected patient // is present at index (i, j) if (arr[i][j] == 1 && timeofinfection[i][j] == -1) { // Set flag as true flag = 1; break ; } // Update the maximum time of infection maxi = Math.Max(maxi, timeofinfection[i][j]); } } // If an uninfected patient is present if (flag == 1) return -1; // Return the final result return maxi; } // Driver code static void Main( string [] args) { int [][] arr = { new int []{ 2, 1, 0, 2, 1 }, new int []{ 1, 0, 1, 2, 1 }, new int []{ 1, 0, 0, 2, 1 } }; Console.WriteLine(maximumTime(arr)); } } |
2
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Approach 2:This uses the same BFS traversal technique but instead of using an array of integers to keep track of whether all patients are infected, it uses a single integer which reduces overall space consumption and overhead of doing an extra check for uninfected patients.
The basic idea is we will store the count of uninfected persons at the start and as an individual will got infected we will decrement this count. This will remove the overhead of checking for uninfected persons at the end. And the time at which the last person got infected will be our final answer.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Direction arrays vector<pair< int , int > > direction = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } }; // Function to find the maximum time // required for all patients to get infected int maximumTime(vector<vector< int > > arr) { // Stores the number of rows int n = arr.size(); // Stores the number of columns int m = arr[0].size(); // Stores whether particular index(i, j) // is visited or not vector<vector< bool >> visited(n,vector< bool >(m,0)); // Stores index and time of // infection of infected persons queue<pair<pair< int , int >, int > > q; //Stores uninfected patients count int uninfected_count=0; //Stores time at which last person got infected int time = 0; // Traverse the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index of current patient // and mark it as visited q.push({ { i, j }, 0 }); visited[i][j] = 1; } //If current patient is uninfected //increment uninfected count if (arr[i][j] == 1){ uninfected_count++; } } } // Iterate until queue becomes empty while (!q.empty()) { // Stores the front element of queue pair<pair< int , int >, int > current = q.front(); time = current.second; // Pop out the front element q.pop(); // Check for all four // adjacent indices for ( auto it : direction) { // Find the index of the // adjacent cell int i = current.first.first + it.first; int j = current.first.second + it.second; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || visited[i][j] != 0) { // Continue to the next // neighbouring cell continue ; } // Push the infected // neighbour into queue q.push({ { i, j }, time + 1 }); visited[i][j] = 1; uninfected_count--; } } // If an uninfected patient is present if (uninfected_count != 0) return -1; // Return the final result return time ; } // Driver Code int main() { vector<vector< int > > arr = { { 2, 1, 0, 2, 1 }, { 1, 0, 1, 2, 1 }, { 1, 0, 0, 2, 1 } }; cout << maximumTime(arr); return 0; } // Contributed By Devendra Kolhe |
Java
// Java program for the above approach import java.util.*; public class GFG{ static class pair { int first, second, third; pair( int first, int second, int third) { this .first = first; this .second = second; this .third = third; } } // Direction arrays static int direction[][] = { { 1 , 0 }, { 0 , - 1 }, { - 1 , 0 }, { 0 , 1 } }; // Function to find the maximum time // required for all patients to get infected static int maximumTime( int arr[][]) { // Stores the number of rows int n = arr.length; // Stores the number of columns int m = arr[ 0 ].length; // Stores whether particular index(i, j) // is visited or not boolean visited[][] = new boolean [n][m]; // Stores index and time of // infection of infected persons Queue<pair> q = new LinkedList<>(); //Stores uninfected patients count int uninfected_count= 0 ; //Stores time at which last person got infected int time = 0 ; // Traverse the matrix for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { // If the current patient // is already infected if (arr[i][j] == 2 ) { // Push the index of current patient // and mark it as visited q.add( new pair(i, j, 0 )); visited[i][j] = true ; } //If current patient is uninfected //increment uninfected count if (arr[i][j] == 1 ){ uninfected_count++; } } } // Iterate until queue becomes empty while (!q.isEmpty()) { // Stores the front element of queue pair current = q.peek(); time = current.third; // Pop out the front element q.poll(); // Check for all four // adjacent indices for ( int [] it : direction) { // Find the index of the // adjacent cell int i = current.first + it[ 0 ]; int j = current.second + it[ 1 ]; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] != 1 || visited[i][j]) { // Continue to the next // neighbouring cell continue ; } // Push the infected // neighbour into queue q.add( new pair( i, j, time + 1 )); visited[i][j] = true ; uninfected_count--; } } // If an uninfected patient is present if (uninfected_count != 0 ) return - 1 ; // Return the final result return time; } // Driver Code public static void main(String args[]) { int arr[][] = { { 2 , 1 , 0 , 2 , 1 }, { 1 , 0 , 1 , 2 , 1 }, { 1 , 0 , 0 , 2 , 1 } }; System.out.println(maximumTime(arr)); } } // This code is contributed by adityapande88. |
Python
# Python program for the above approach # Direction arrays direction = [( 1 , 0 ), ( 0 , - 1 ), ( - 1 , 0 ), ( 0 , 1 )] # Function to find the maximum time # required for all patients to get infected def maximumTime(arr): # Stores the number of rows n = len (arr) # Stores the number of columns m = len (arr[ 0 ]) # Stores whether particular index(i, j) # is visited or not visited = [[ False for j in range (m)] for i in range (n)] # Stores index and time of # infection of infected persons q = [] # Stores uninfected patients count uninfected_count = 0 # Stores time at which last person got infected time = 0 # Traverse the matrix for i in range (n): for j in range (m): # If the current patient # is already infected if arr[i][j] = = 2 : # Push the index of current patient # and mark it as visited q.append(((i, j), 0 )) visited[i][j] = True # If current patient is uninfected # increment uninfected count if arr[i][j] = = 1 : uninfected_count + = 1 # Iterate until queue becomes empty while q: # Stores the front element of queue current = q.pop( 0 ) time = current[ 1 ] # Check for all four # adjacent indices for it in direction: # Find the index of the # adjacent cell i = current[ 0 ][ 0 ] + it[ 0 ] j = current[ 0 ][ 1 ] + it[ 1 ] # If the current adjacent # cell is invalid or it # contains an infected patient if i < 0 or j < 0 or i > = n or j > = m or arr[i][j] ! = 1 or visited[i][j]: # Continue to the next # neighbouring cell continue # Push the infected # neighbour into queue q.append(((i, j), time + 1 )) visited[i][j] = True uninfected_count - = 1 # If an uninfected patient is present if uninfected_count ! = 0 : return - 1 # Return the final result return time # Driver Code arr = [[ 2 , 1 , 0 , 2 , 1 ], [ 1 , 0 , 1 , 2 , 1 ], [ 1 , 0 , 0 , 2 , 1 ]] print (maximumTime(arr)) # This code is contributed by divyansh2212 |
Javascript
// JavaScript program for the above approach // Direction arrays let direction = [ [1, 0], [0, -1], [-1, 0], [0, 1] ]; // Function to find the maximum time // required for all patients to get infected function maximumTime(arr) { // Stores the number of rows let n = arr.length; // Stores the number of columns let m = arr[0].length; // Stores whether particular index(i, j) // is visited or not let visited = Array(n).fill().map(() => Array(m).fill( false )); // Stores index and time of // infection of infected persons let q = []; // Stores uninfected patients count let uninfected_count = 0; // Stores time at which last person got infected let time = 0; // Traverse the matrix for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { // If the current patient // is already infected if (arr[i][j] === 2) { // Push the index of current patient // and mark it as visited q.push([ [i, j], 0 ]); visited[i][j] = true ; } // If current patient is uninfected // increment uninfected count if (arr[i][j] === 1) { uninfected_count += 1; } } } // Iterate until queue becomes empty while (q.length > 0) { // Stores the front element of queue let current = q.shift(); time = current[1]; // Check for all four // adjacent indices for (let it of direction) { // Find the index of the // adjacent cell let i = current[0][0] + it[0]; let j = current[0][1] + it[1]; // If the current adjacent // cell is invalid or it // contains an infected patient if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] !== 1 || visited[i][j]) { // Continue to the next // neighbouring cell continue ; } // Push the infected // neighbour into queue q.push([ [i, j], time + 1 ]); visited[i][j] = true ; uninfected_count -= 1; } } // If an uninfected patient is present if (uninfected_count !== 0) { return -1; } // Return the final result return time; } // Driver Code let arr = [ [2, 1, 0, 2, 1], [1, 0, 1, 2, 1], [1, 0, 0, 2, 1] ]; console.log(maximumTime(arr)); // This code is contributed by adityasharmadev01 |
C#
// Online C# Editor for free // Write, Edit and Run your C# code using C# Online Compiler using System; using System.Collections.Generic; public struct Pair { public int first, second, third; public Pair( int first, int second, int third) { this .first = first; this .second = second; this .third = third; } } public class GFG { // Direction arrays static int [][] direction = { new int [] { 1, 0 }, new int [] { 0, -1 }, new int [] { -1, 0 }, new int [] { 0, 1 } }; // Function to calculate maximum time required to infect // all uninfected cells static int MaximumTime( int [][] arr) { // Stores the number of rows int n = arr.Length; // Stores the number of columns int m = arr[0].Length; // Stores whether particular index(i, j) // is visited or not bool [, ] visited = new bool [n, m]; // Stores index and time of // infection of infected persons var q = new Queue<Pair>(); // Stores uninfected patients count int uninfected_count = 0; int time = 0; // Add infected cells to the queue and mark them as // visited Count the number of uninfected cells for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // If the current patient // is already infected if (arr[i][j] == 2) { // Push the index of current patient // and mark it as visited q.Enqueue( new Pair(i, j, 0)); visited[i, j] = true ; } // If current patient is uninfected // increment uninfected count if (arr[i][j] == 1) { uninfected_count++; } } } // Perform BFS until all uninfected cells are // infected while (q.Count > 0) { var current = q.Peek(); time = current.third; q.TryDequeue( out current); for ( int i = 0; i < 4; i++) { int x = current.first + direction[i][0]; int y = current.second + direction[i][1]; // Check if new cell is within bounds and // uninfected and Not Visited if (x < 0 || y < 0 || x >= n || y >= m || arr[x][y] != 1 || visited[x, y]) { continue ; } // Add new cell to the queue, mark as // visited and decrement uninfected count q.Enqueue( new Pair(x, y, time + 1)); visited[x, y] = true ; uninfected_count--; } } // If there are uninfected cells remaining, return // -1 to indicate infection failure if (uninfected_count != 0) { return -1; } // Return time taken to infect all uninfected cells return time; } public static void Main( string [] args) { int [][] arr = { new int [] { 2, 1, 0, 2, 1 }, new int [] { 1, 0, 1, 2, 1 }, new int [] { 1, 0, 0, 2, 1 } }; Console.WriteLine(MaximumTime(arr)); } // Code is Contributed By Vikas Bishnoi } |
2
Time Complexity: O(n*m)
Auxiliary Space: O(n*m)