17 November

Q1 Shortest Unsorted Continuous Subarray

//the concept of this question is really worth remembering. How we identified the ordered set by seeing the right most and left most unordered element of a string.
//then we found out the largest of them

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;

        //first we find the bad element element from the left
        while (left < n - 1 && nums[left] <= nums[left + 1])
            ++left;

        // If the array is already sorted then, return 0 (case number 3)
        if (left == n - 1)
            return 0;

        //now we find the first unordered element from the right
        while (right > 0 && nums[right] >= nums[right - 1])
            --right;

        // 
        int subarrayMin = *min_element(nums.begin()+left,nums.begin()+right + 1);
        int subarrayMax = *max_element(nums.begin()+ left, nums.begin() + right +1);

        // Expand the left boundary
        while (left > 0 && nums[left - 1] > subarrayMin)
            --left;

        //for increasing the right boundary
        while (right < n - 1 && nums[right + 1] < subarrayMax)
            ++right;

        
        return right - left + 1;
    }
};