Partition an array into two subarrays with right greater than left

Given an array of N elements. You have to partition the array into two non-empty subarrays such that every number in the right subarray is strictly greater than every number in the left subarray.

If it is possible, then print the two resultant subarrays separated by a line otherwise, print  “Impossible”.

Note : that multiple answers may exist, you may print any of them.

Examples :

Input : A[] = {5, 3, 2, 7, 9}
Output : {5, 3, 2}
          {7, 9}
Explanation :
It is seen that every element of the second subarray {7, 9} is
strictly greater than every number in the first subarray {5, 3, 2}.
So.
it is a valid partition of the given array.

Input : A[] = {1,1,1,1,1}
Output : Impossible
Explanation :
It can be shown that there is no partition possible for this array.

Naive Approcah : 

The brute force way to solve this question is to check for every split position in the array if all numbers on the left of it are smaller than all on the right.

Time Complexity : O(N^2)

Auxiliary Space : O(N)

Efficient Approach : 

• Traversing from the left to right can save the maximum value on the left.
• Then, finding the minimum value on the right is sufficient.
• Pre-calculate the minimum value at every position while iterating over the input from the right.
• Now, check if the left maximum is smaller than the right minimum for every position.
• Whenever we will get such position , we will store that position in ‘ind’ variable and break from the loop and make two subarrays-
  1.The left subarray which  will contain the first  ‘ind’ elements of the original array.
  2.The right subarray which will conatin the rest elements of the original array.
• Finally, print those subarrays separated by a line.
• If such positions are not found, simply print “Impossible”.

Implementation :

//JAVA program of the above approach
import java.util.*;
class Main
{
//Function to partition the array into two non-empty subarrays such that 
//every number in the right subarray is strictly greater than every number in the left subarray
 static void solve(int a[],int n)
  {
     //min array to store the minimum value at every position form the right
     int min[]=new int[n];
     int minimum=Integer.MAX_VALUE;
     for(int i=n-1;i>=0;i--)
       {
          minimum=Math.min(minimum,a[i]);
          min[i]=minimum;
       }
       
      int max=Integer.MIN_VALUE;
      //ind variable to store the position where partition can be made
      int ind=-1;
      for(int i=0;i<n-1;i++)
        {
          //max variable to store maximum value at that index
          max=Math.max(max,a[i]);
          
          //if the maximum is less than the minimum of the next position
          if(max<min[i+1])
            {
               //store that position in 'ind'
               ind=i;
               //break from the loop as we have got our position
               break;
            }
         }
      //if the position i.e. ind is not equal to -1
      //this denotes,the partition is possible at the place of ind
      if(ind!=-1)
        {
           //make two list left and right
           ArrayList<Integer> left=new ArrayList<>();
           ArrayList<Integer> right=new ArrayList<>();
           
           //left for storing first ind elements of the original array
           for(int i=0;i<=ind;i++)
             left.add(a[i]);
             
           //right for storing the rest elements of the original array
           for(int i=ind+1;i<n;i++)
             right.add(a[i]);
            
           //Print those lists
           for(int i=0;i<left.size();i++)
             System.out.print(left.get(i)+" ");
             
            System.out.println();
           
           for(int i=0;i<right.size();i++)
             System.out.print(right.get(i)+" ");
        }
      //if the ind is equal to -1 
      //this denotes, the partition is not possible
      else
        System.out.println("Impossible");
  }
  
//Driver Code
public static void main (String[] args) 
 {
   //Given array
   int a[]={5, 3, 2, 7, 9};
   int n=a.length;
   
   solve(a,n);
 }
}

5 3 2 
7 9

Time Complexity : O(N)

Auxiliary Space : O(N)