Partition array into two subarrays with every element in the right subarray strictly greater than every element in left subarray | Python3 program for 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 first subarray ; Print second subarray ; Otherwise ; Driver Code
import sys NEW_LINE def partitionArray ( a , n ) : NEW_LINE INDENT Min = [ 0 ] * n NEW_LINE Mini = sys . maxsize NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT Mini = min ( Mini , a [ i ] ) NEW_LINE Min [ i ] = Mini NEW_LINE DEDENT Maxi = - sys . maxsize - 1 NEW_LINE ind = - 1 NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT Maxi = max ( Maxi , a [ i ] ) NEW_LINE if ( Maxi < Min [ i + 1 ] ) : NEW_LINE ind = i NEW_LINE break NEW_LINE DEDENT if ( ind != - 1 ) : NEW_LINE INDENT for i in range ( ind + 1 ) : NEW_LINE print ( a [ i ] , end = " ▁ " ) NEW_LINE print ( ) NEW_LINE for i in range ( ind + 1 , n , 1 ) : NEW_LINE print ( a [ i ] , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Impossible " ) NEW_LINE DEDENT DEDENT arr = [ 5 , 3 , 2 , 7 , 9 ] NEW_LINE N = 5 NEW_LINE partitionArray ( arr , N ) NEW_LINE