C++ two passes solution


  • 0
    A

    1st pass, from left to right, keep current maximum, update right index when number is less than current maximum;
    2nd pass, from right to left, keep current minimum, uddate left index when number is larger than current minimum.

    class Solution {
    public:
        int findUnsortedSubarray(vector<int>& nums) {
            if (nums.empty())
                return 0;
            
            int m = nums[0], n = nums.size(), left = n, right = -1;
            for (int i = 1; i < n; ++i) {
                if (nums[i] < m)
                    right = i;
                m = max(m, nums[i]);
            }
            m = nums[n - 1];
            for (int i = n - 1; i >= 0; --i) {
                if (nums[i] > m)
                    left = i;
                m = min(m, nums[i]);
            }
            return max(0, right - left + 1);
        }
    };
    

Log in to reply
 

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