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
using System ; using System . Collections . Generic ; class GFG { static bool checkPermutation ( int [ ] ans , int [ ] a , int n ) { int Max = Int32 . MinValue ; 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 ] ; Dictionary < int , int > um = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! um . ContainsKey ( a [ i ] ) ) { ans [ i ] = a [ i ] ; um [ a [ i ] ] = i ; } } List < int > v = new List < int > ( ) ; 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 [ j ] ; j ++ ; } } if ( checkPermutation ( ans , a , n ) ) { for ( int i = 0 ; i < n ; i ++ ) { Console . Write ( ans [ i ] + " ▁ " ) ; } } else Console . Write ( " - 1" ) ; } public static void Main ( ) { int [ ] arr = { 1 , 3 , 4 , 5 , 5 } ; int N = arr . Length ; findPermutation ( arr , N ) ; } }