text: Partition array into two subarrays with every element in the right subarray strictly greater than every element in left subarray | C ++ program of the above approach ; Function to partition the array into two non - empty subarrays which satisfies the given condition ; Stores the suffix Min array ; Stores the Minimum of a suffix ; Traverse the array in reverse ; Update Minimum ; Store the Minimum ; Stores the Maximum value of a prefix ; Stores the index of the partition ; Update Max ; If Max is less than Min [ i + 1 ] ; Store the index of partition ; break ; If ind is not - 1 ; Print the first subarray ; Print the second subarray ; Otherwise ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void partitionArray ( int * a , int n ) { int * Min = new int [ n ] ; int Mini = INT_MAX ; for ( int i = n - 1 ; i >= 0 ; i -- ) { Mini = min ( Mini , a [ i ] ) ; Min [ i ] = Mini ; } int Maxi = INT_MIN ; int ind = -1 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { Maxi = max ( Maxi , a [ i ] ) ; if ( Maxi < Min [ i + 1 ] ) { ind = i ; break ; } } if ( ind != -1 ) { for ( int i = 0 ; i <= ind ; i ++ ) cout << a [ i ] << " ▁ " ; cout << endl ; for ( int i = ind + 1 ; i < n ; i ++ ) cout << a [ i ] << " ▁ " ; } else cout << " Impossible " ; } int main ( ) { int arr [ ] = { 5 , 3 , 2 , 7 , 9 } ; int N = 5 ; partitionArray ( arr , N ) ; return 0 ; }