Partition array into two subarrays with every element in the right subarray strictly greater than every element in left subarray | 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
function partitionArray ( a , n ) { var min = Array ( n ) . fill ( 0 ) ; var mini = Number . MAX_VALUE ; for ( i = n - 1 ; i >= 0 ; i -- ) { mini = Math . min ( mini , a [ i ] ) ; min [ i ] = mini ; } var maxi = Number . MIN_VALUE ; var ind = - 1 ; for ( i = 0 ; i < n - 1 ; i ++ ) { maxi = Math . max ( maxi , a [ i ] ) ; if ( maxi < min [ i + 1 ] ) { ind = i ; break ; } } if ( ind != - 1 ) { for ( i = 0 ; i <= ind ; i ++ ) document . write ( a [ i ] + " " ) ; document . write ( " " ) ; for ( i = ind + 1 ; i < n ; i ++ ) document . write ( a [ i ] + " " ) ; } else document . write ( " " ) ; } var arr = [ 5 , 3 , 2 , 7 , 9 ] ; var N = arr . length ; partitionArray ( arr , N ) ;