# c++ O(n) one-pass solution which beats almost

• The idea is use variables `begin` and `end` to record the beginning and ending of the unsorted array.

``````    int findUnsortedSubarray(vector<int>& nums) {
int start = -1, end = -1,  max = INT_MIN;
for(int i=0; i<nums.size();i++){
if(max>nums[i]){
if(start == -1)start = i-1;
while(start-1>=0 && nums[start-1]>nums[i])start--;
end = i+1;
}
else max = nums[i];
}
return end - start;
}
``````

Firstly, if the array is already a sorted array, then it means `nums[i]` is not less than any `nums[j]` for all 0<=j<i. Therefore, the value of `start` and `end` will never change. So the program returns 0 finally.

Now, let's consider the case of the unsorted array. We use [1, 3, 3, 2, 8, 10, 0, 15] as the example. We use `max` to record the largest value we visited. If it's a sorted array, then `max` should be equal to the last element we visited. We only update `start` and `end` when `max` is less then the next element we visit. The process is as follows:

When i =0, max = nums[0] = 1;

When i=1, max = nums[1] = 3;

When i=2, max = nums[1] = 3;

When i =3, we find that max < nums[3], then it means that we find a unsorted subarray. Since `start ==-1`, so we know it is the beginning of the unsorted subarray, then update `start = i-1=2` and `end =i+1 = 4` (actually `end -1` should be the end of the unsorted subarray, but we use `end -start` to count the length of the unsorted subarray so we let `end =i+1`). Because, there might be duplicates in the array (like nums[1] = nums[2] = 3), we need to go back to check whether `nums[start-1] == nums[start]`. Then we update `start = 1`.

When i =4, max = nums[4] = 8.

When i =5, max = nums[5] = 10.

When i =6, we find that max < nums[6]. So we update `end =i+1 = 7` . Now we need to update `start`, since `start` does not equal to `-1` which means that we already have a start. So what need to do is to update `start` so that `nums[start] < =nums[i]` or we arrive the beginning of the array. Finally we update `start = 0` here.
when i =7, max = nums[7] = 15.

Finally we return `end - start` which is 7-0=7.

• hope you can give me advice!

• could you please explain your code by using words ~thank you !

• @haiki123
Sure. I update the post, you can look it and I hope you can understand the code.

• @Hao-Cai Thank you ! that's really elaborate~It's an unique solution,I understand it completely ~

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.