Permutation of first N natural numbers having given array as the prefix maximum array | Java program for the above approach ; 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
import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static boolean checkPermutation ( int ans [ ] , int a [ ] , int n ) { int Max = Integer . MIN_VALUE ; for ( int i = 0 ; i < n ; i ++ ) { Max = Math . max ( Max , ans [ i ] ) ; if ( Max != a [ i ] ) return false ; } return true ; } static void findPermutation ( int a [ ] , int n ) { int ans [ ] = new int [ n ] ; HashMap < Integer , Integer > um = new HashMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! um . containsKey ( a [ i ] ) ) { ans [ i ] = a [ i ] ; um . put ( a [ i ] , i ) ; } } ArrayList < Integer > v = new ArrayList < > ( ) ; int j = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { if ( ! um . containsKey ( i ) ) { v . add ( i ) ; } } for ( int i = 0 ; i < n ; i ++ ) { if ( ans [ i ] == 0 ) { ans [ i ] = v . get ( j ) ; j ++ ; } } if ( checkPermutation ( ans , a , n ) ) { for ( int i = 0 ; i < n ; i ++ ) { System . out . print ( ans [ i ] + " ▁ " ) ; } } else System . out . println ( " - 1" ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 3 , 4 , 5 , 5 } ; int N = arr . length ; findPermutation ( arr , N ) ; } }