Easy O(n) 2 pass solution


#1

vector Solution::subUnsort(vector &A) {

int n= A.size();

if(n<=1)
return {-1};

vector<int> maximum(n);

int max= INT_MIN;

for(int i=0;i<n;i++){
    
   if(A[i]>max)
   max= A[i];
   
   maximum[i]=max;
    
}

vector<int> minimum(n);

int min= INT_MAX;

for(int i=n-1;i>=0;i--){
    
    if(A[i]<min)
    min= A[i];
    
    minimum[i]=min;
}

int i=0;
int final_i;
int final_j;


while(i<n-1){
    
    if(minimum[i]==A[i] && A[i]<=A[i+1])
    i++;
    
    else 
    break;
    
}

final_i=i;

int j=n-1;

while(j>0){
    
    if(maximum[j]==A[j] && A[j]>=A[j-1])
    j--;
    
    else
    break;
    
}

final_j= j;

if(final_i==n-1 && final_j==0){
    return {-1};
}
vector<int> ans;

ans.push_back(final_i);
ans.push_back(final_j);

return ans;

}