Easy to understand c++ code with O(n) complexity


  • 0
    Y

    '''
    class Solution {
    public:
    int findUnsortedSubarray(vector<int>& nums) {
    int start=0, end=0, prev = nums[0], len = nums.size();

        // going from left to find unsorted starting index
        for (int i=1; i<len; i++) {
            if (nums[i]<prev) {
                start = i-1;
                break;
            }
            else {
                prev = nums[i];
            }
        }
        
        // going from right to find unsorted ending index
        prev = nums[len-1];
        for (int j=len-2; j>=0; j--) {
            if (nums[j]>prev) {
                end = j+1;
                break;
            }
            else {
                prev = nums[j];
            }
        }
        
        // find min and max in the unsorted array
        auto result = minmax_element(nums.begin()+start, nums.begin()+end+1); // last range has to +1!!!
        
        // check how left the min could go
        for (int k=0; k<start; k++) {
            if (*result.first<nums[k]) {
                start = k;
                break;
            }
        }
        
        // check how right the max could go
        for (int l=len-1; l>end; l--) {
            if (*result.second>nums[l]) {
                end = l;
                break;
            }
        }
        
        // check if the array is non-empty
        return end>start ? end-start+1:0;
    }
    

    };
    '''


Log in to reply
 

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