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


  • 5

    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.


  • 1

    hope you can give me advice!


  • 1
    H

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


  • 0

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


  • 0
    H

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


Log in to reply
 

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