# Maximum Unsorted Subarray | InterView Bit

## Maximum Unsorted Subarray

Problem Description

Given an array A of non-negative integers of size N. Find the minimum sub-array Al, Al+1 ,..., Ar such that if we sort(in ascending order) that sub-array, then the whole array should get sorted. If A is already sorted, output -1.

Problem Constraints

1 <= N <= 1000000
1 <= A[i] <= 1000000

Input Format

First and only argument is an array of non-negative integers of size N.

Output Format

Return an array of length two where the first element denotes the starting index(0-based) and the second element denotes the ending index(0-based) of the sub-array. If the array is already sorted, return an array containing only one element i.e. -1.

Example Input

Input 1:

`A = [1, 3, 2, 4, 5]`

Input 2:

`A = [1, 2, 3, 4, 5]`

Example Output

Output 1:

`[1, 2]`

Output 2:

`[-1]`

Example Explanation

Explanation 1:

`If we sort the sub-array A1, A2, then the whole array A gets sorted.`

Explanation 2:

`A is already sorted.`

`bool helper(vector<int>&v,int i){    int x=v[i];    if(i==0)return x>v;    else if(i==v.size()-1)return x<v[i-1];    return x>v[i+1] || x<v[i-1];}vector<int> Solution::subUnsort(vector<int> &v) {    if(v.size()<2)return {-1};    int st,end;    vector<int>ans;    int smallest=INT_MAX,largest=INT_MIN;    for(int i=0; i<v.size(); i++){        if(helper(v,i)){            smallest=min(smallest,v[i]);            largest=max(largest,v[i]);        }    }    if(smallest==INT_MAX)return {-1};    int left=0,right=v.size()-1;    while(smallest>=v[left])left++;    while(largest<=v[right])right--;    return {left,right};    }`