◻️581. Shortest Unsorted Continuous Subarray (easy)

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

Example 1:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

Input: nums = [1,2,3,4]
Output: 0

Example 3:

Input: nums = [1]
Output: 0

---

Solutions

Normal - without 2 pointer

Runtime 21 ms Memory 29.32 MB

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n=nums.size();
        if(n<=1) return 0;
        int i, j, Min=INT_MAX, Max=INT_MIN;
        for(i=0; i<n; ++i){
            if (i > 0 && nums[i] < nums[i - 1]) {
                Max = std::max(Max, nums[i]);
                Min = std::min(Min, nums[i - 1]);
            }
            if (i < n - 1 && nums[i] > nums[i + 1]) {
                Max = std::max(Max, nums[i]);
                Min = std::min(Min, nums[i + 1]);
            }
        }
        if(Max==INT_MIN) return 0;

        for(i=0; i<n && nums[i]<=Min; i++);
        for(j=n-1; j>=0 && nums[j]>=Max; j--);
        
        //Alternate
        // i = 0, j = n - 1;
        // while (i < n && nums[i] <= Min) {
        //     ++i;
        // }
        // while (j >= 0 && nums[j] >= Max) {
        //     --j;
        // }

        return j-i+1;
    }
};

Optimised - 2 Pointer Approach

Runtime 26 ms Memory 29.50 MB

Time Complexity : O(n) | Space Complexity : O(1)

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int low = 0, high = nums.size()-1;
        while (low+1 < nums.size() && nums[low] <= nums[low+1]) low++;
        while (high-1 >= 0 && nums[high-1] <= nums[high]) high--;

        if (low == nums.size()-1) return 0;

        int wMin = INT_MAX, wMax = INT_MIN;
        for (int i = low; i <= high; i++) {
            wMin = min(wMin, nums[i]);
            wMax = max(wMax, nums[i]);
        }

        while (low-1 >= 0 && nums[low-1] > wMin) low--;
        while (high+1 <= nums.size()-1 && nums[high+1] < wMax) high++;

        return high - low + 1;
    }
};