O(n) simple solution in C++


#1
vector<int> Solution::subUnsort(vector<int> &A) {
vector<int> ans;
if (is_sorted(A.begin(), A.end())) {
    ans.push_back(-1);
    return ans;
}

int end = A.size()-1;
while (A[end-1] <= A[end])
    end--;
    
int start = 0;
for (int i = 0 ; i < A.size()-1 ; i++) {
    if (A[i] > A[i+1]) {
        start = i;
        break;
    }
}

int maxval = *max_element(A.begin()+start, A.begin()+end+1);
int minval = *min_element(A.begin()+start, A.begin()+end+1);
for (int i = 0 ; i < start ; i++) {
    if (minval < A[i]) {
        start = i;
    }
}
for (int i = end+1 ; i <= A.size() ; i++) {
    if (A[i] >= maxval) {
        ans.push_back(start);
        ans.push_back(i-1);
        return ans;
    }
}
ans.push_back(start);
ans.push_back(A.size()-1);
return ans;

}