# 3 methods in C++

#1
``````//Method 1 - Sorting
//Time=O(nlog(n)), Space=O(n)
#define all(a) a.begin(),a.end()
vector<int> Solution::subUnsort(vector<int>& a)
{
vector<int>ans;
vector<int>b(a);
sort(all(b));
int i=0,n=a.size(),j=n-1;
while(i<n && b[i]==a[i])
i++;
while(j>=0 && b[j]==a[j])
j--;
if(i==n)
ans.push_back(-1);
else
{
ans.push_back(i);
ans.push_back(j);
}
return ans;
}

//Method 2 - Using LeftMax and RightMin
//gives MLE, which means memory limit is same as size of array
//Time=O(n), Space=O(2n)=O(n)
vector<int> Solution::subUnsort(vector<int>& a)
{
int n=a.size(),i=0,j=n-1;
vector<int>Lmax(n),Rmin(n),ans;
Lmax[0]=a[0];
Rmin[n-1]=a[n-1];
for(int i=1;i<n;i++)
{
Lmax[i]=max(a[i],Lmax[i-1]);
Rmin[n-1-i]=min(a[n-1-i],Rmin[n-i]);
}
while(i<n && Lmax[i]==Rmin[i])
i++;
while(j>=0 && Lmax[j]==Rmin[j])
j--;
if(i==n)
ans.push_back(-1);
else
{
ans.push_back(i);
ans.push_back(j);
}
return ans;
}

//Method 3 -
//By finding smallest element after sorted subarray from left,
//and largest element before sorted subarray from right
//Time=O(n), Space=O(1)
#define range(a,i,j) a.begin()+i,a.begin()+j
vector<int> Solution::subUnsort(vector<int>& a)
{
int n=a.size(),i=0,j=n-1,minn,maxx;
vector<int>ans;
while(i<n-1 && a[i]<=a[i+1])
i++;
if(i==n-1)
ans.push_back(-1);
else
{
minn=min_element(range(a,i+1,n))-a.begin();
while(i>=0 && a[i]>a[minn])
i--;
while(j>0 && a[j]>=a[j-1])
j--;
maxx=max_element(range(a,0,j))-a.begin();
while(j<n && a[j]<a[maxx])
j++;
ans.push_back(i+1);
ans.push_back(j-1);
}
return ans;
}
``````

If someone finds mistakes that may have been skipped owing to loose test cases, please do inform me.