C++ Solution: O(n) Time & O(1) Space


  • 0
    J
    class Solution {
    public:
        int findUnsortedSubarray(vector<int>& nums) {
            if (nums.size() < 2) return 0;
            int left = 0, right = nums.size() - 1;
            int i = left + 1;
            for (; i < nums.size(); ++i) {
                if (nums[left] > nums[i]) break;
                ++left;
            }
            for (; i < nums.size(); ++i) {
                while (left >= 0 && nums[left] > nums[i]) {
                    --left;
                }
            }
            i = right - 1;
            for (; i >= 0; --i) {
                if (nums[right] < nums[i]) break;
                --right;
            }
            for (; i >= 0; --i) {
                while (right < nums.size() && nums[right] < nums[i]) {
                    ++right;
                }
            }
            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.