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.