text: Permutation of first N natural numbers having given array as the prefix maximum array | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; bool checkPermutation ( int ans [ ] , int a [ ] , int n ) { int Max = INT_MIN ; for ( int i = 0 ; i < n ; i ++ ) { Max = max ( Max , ans [ i ] ) ; if ( Max != a [ i ] ) return false ; } return true ; } void findPermutation ( int a [ ] , int n ) { int ans [ n ] = { 0 } ; unordered_map < int , int > um ; for ( int i = 0 ; i < n ; i ++ ) { if ( um . find ( a [ i ] ) == um . end ( ) ) { ans [ i ] = a [ i ] ; um [ a [ i ] ] = i ; } } vector < int > v ; int j = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { if ( um . find ( i ) == um . end ( ) ) { v . push_back ( i ) ; } } for ( int i = 0 ; i < n ; i ++ ) { if ( ans [ i ] == 0 ) { ans [ i ] = v [ j ] ; j ++ ; } } if ( checkPermutation ( ans , a , n ) ) { for ( int i = 0 ; i < n ; i ++ ) { cout << ans [ i ] << " ▁ " ; } } else cout << " - 1" ; } int main ( ) { int arr [ ] = { 1 , 3 , 4 , 5 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findPermutation ( arr , N ) ; return 0 ; }