Minimum time required to rot all oranges | Dynamic Programming | Javascript implementation of the approach ; DP table to memoize the values ; Visited array to keep track of visited nodes in order to avoid infinite loops ; Function to return the minimum of four numbers ; Function to return the minimum distance to any rotten orange from [ i , j ] ; If i , j lie outside the array ; If 0 then it can 't lead to  any path so return INT_MAX ; If 2 then we have reached our rotten oranges so return from here ; If this node is already visited then return to avoid infinite loops ; Mark the current node as visited ; Check in all four possible directions ; Take the minimum of all ; If result already exists in the table check if min_value is less than existing value ; Function to return the minimum time required to rot all the oranges ; Calculate the minimum distances to any rotten orange from all the fresh oranges ; Pick the maximum distance of fresh orange to some rotten orange ; If all oranges can be rotten ; Driver Code
let C = 5 ; let R = 3 ; let INT_MAX = 10000000 ; let table = new Array ( R ) ; let visited = new Array ( R ) ; for ( let i = 0 ; i < R ; i ++ ) { table [ i ] = new Array ( C ) ; visited [ i ] = new Array ( C ) ; } function min ( p , q , r , s ) { let temp1 = p < q ? p : q ; let temp2 = r < s ? r : s ; if ( temp1 < temp2 ) return temp1 ; return temp2 ; } function Distance ( arr , i , j ) { if ( i >= R j >= C i < 0 j < 0 ) return INT_MAX ; else if ( arr [ i ] [ j ] == 0 ) { table [ i ] [ j ] = INT_MAX ; return INT_MAX ; } else if ( arr [ i ] [ j ] == 2 ) { table [ i ] [ j ] = 0 ; return 0 ; } else if ( visited [ i ] [ j ] == 1 ) { return INT_MAX ; } else { visited [ i ] [ j ] = 1 ; let temp1 = Distance ( arr , i + 1 , j ) ; let temp2 = Distance ( arr , i - 1 , j ) ; let temp3 = Distance ( arr , i , j + 1 ) ; let temp4 = Distance ( arr , i , j - 1 ) ; let min_value = 1 + min ( temp1 , temp2 , temp3 , temp4 ) ; if ( table [ i ] [ j ] > 0 && table [ i ] [ j ] < INT_MAX ) { if ( min_value < table [ i ] [ j ] ) table [ i ] [ j ] = min_value ; } else table [ i ] [ j ] = min_value ; visited [ i ] [ j ] = 0 ; } return table [ i ] [ j ] ; } function minTime ( arr ) { let max = 0 ; for ( let i = 0 ; i < R ; i ++ ) { for ( let j = 0 ; j < C ; j ++ ) { if ( arr [ i ] [ j ] == 1 ) Distance ( arr , i , j ) ; } } for ( let i = 0 ; i < R ; i ++ ) { for ( let j = 0 ; j < C ; j ++ ) { if ( arr [ i ] [ j ] == 1 && table [ i ] [ j ] > max ) max = table [ i ] [ j ] ; } } if ( max < INT_MAX ) return max ; return - 1 ; } let arr = [ [ 2 , 1 , 0 , 2 , 1 ] , [ 0 , 0 , 1 , 2 , 1 ] , [ 1 , 0 , 0 , 2 , 1 ] ] document . write ( minTime ( arr ) ) ;