C++ O(n) Explained


#1

vector Solution::subUnsort(vector &A) {
int n = A.size();
int start = -1, end = -1;
// if we look at end variable then its the last index where things are not sorted
// i.e its the last index where A[i] < maxValue of left array
// after this A[i] >= maxValue of left array so sorted :slight_smile:
// so we consider the elements from start and keep cnahging the end value
// if we encounter index where A[i] < maxValue of left array
int maxi = A[0];
for(int i = 1; i < n; i++){
if(A[i] < maxi) end = i;
maxi = max(maxi, A[i]);
}
// at this point if end has not got a value other than -1 we know array is sorted
if(end == -1) return {-1};
// now we try to find start index so its the first index before which everything is sorted
// i.e first index where A[i] > minValue of right array
// before this A[i] < minValue of right array so sorted :slight_smile:
// so we consier the elements from end and keep changing the start value
// if we encounter index where A[i] > minValue of right array
int mini = A[n-1];
for(int i = n-1; i >= 0; iā€“){
if(A[i] > mini) start = i;
mini = min(mini, A[i]);
}
return {start, end};
}


#2

Its wrong. Please cross check