Partition array into two subarrays with every element in the right subarray strictly greater than every element in left subarray | Java 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
import java . util . * ; class GFG { static void partitionArray ( int a [ ] , int n ) { int min [ ] = new int [ n ] ; int mini = Integer . MAX_VALUE ; for ( int i = n - 1 ; i >= 0 ; i -- ) { mini = Math . min ( mini , a [ i ] ) ; min [ i ] = mini ; } int maxi = Integer . MIN_VALUE ; int ind = - 1 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { maxi = Math . max ( maxi , a [ i ] ) ; if ( maxi < min [ i + 1 ] ) { ind = i ; break ; } } if ( ind != - 1 ) { for ( int i = 0 ; i <= ind ; i ++ ) System . out . print ( a [ i ] + " ▁ " ) ; System . out . println ( ) ; for ( int i = ind + 1 ; i < n ; i ++ ) System . out . print ( a [ i ] + " ▁ " ) ; } else System . out . println ( " Impossible " ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 3 , 2 , 7 , 9 } ; int N = arr . length ; partitionArray ( arr , N ) ; } }