Permutation of first N natural numbers having given array as the prefix maximum array | Function to check if the maximum prefix array of ans [ ] is equal to array arr [ ] ; Initialize a variable , Max ; Traverse the array , ans [ ] ; Store the maximum value upto index i ; If it is not equal to a [ i ] , then return false ; Otherwise return false ; Function to find the permutation of the array whose prefix maximum array is same as the given array a [ ] ; Stores the required permutation ; Stores the index of first occurrence of elements ; Traverse the array a [ ] ; If a [ i ] is not present in um , then store it in um ; Update the ans [ i ] to a [ i ] ; Stores the unvisited numbers ; Fill the array , v [ ] ; Store the index ; Traverse the array , ans [ ] ; Fill v [ j ] at places where ans [ i ] is 0 ; Check if the current permutation maximum prefix array is same as the given array a [ ] ; If true , the print the permutation ; Otherwise , print - 1 ; Driver Code ; Function Call
function checkPermutation ( ans , a , n ) { let Max = Number . MIN_VALUE ; for ( let i = 0 ; i < n ; i ++ ) { Max = Math . max ( Max , ans [ i ] ) ; if ( Max != a [ i ] ) return false ; } return true ; } function findPermutation ( a , n ) { let ans = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { ans [ i ] = 0 ; } let um = new Map ( ) ; for ( let i = 0 ; i < n ; i ++ ) { if ( ! um . has ( a [ i ] ) ) { ans [ i ] = a [ i ] ; um . set ( a [ i ] , i ) ; } } let v = [ ] ; let j = 0 ; for ( let i = 1 ; i <= n ; i ++ ) { if ( ! um . has ( i ) ) { v . push ( i ) ; } } for ( let i = 0 ; i < n ; i ++ ) { if ( ans [ i ] == 0 ) { ans [ i ] = v [ j ] ; j ++ ; } } if ( checkPermutation ( ans , a , n ) ) { for ( let i = 0 ; i < n ; i ++ ) { document . write ( ans [ i ] + " " ) ; } } else document . write ( " " ) ; } let arr = [ 1 , 3 , 4 , 5 , 5 ] ; let N = arr . length ; findPermutation ( arr , N ) ;