9-liner C++ O(N) count max length of left sorted and bounded sub-array


  • 0

    Calculate the max lengths of left and right sub-arrays which are also bounded by the rest of values. Subtract their lengths from the original length, and you have the min sub-array length which needs to be sorted.

        int findUnsortedSubarray(vector<int>& nums) {
            int L = leftSortedLen<less<int>>(nums);
            if (L == nums.size()) return 0;
            reverse(nums.begin(), nums.end());
            int R = leftSortedLen<greater<int>>(nums);
            return nums.size() - L - R;
    
        }
        
        // max length of left sorted subarray which is no larger than rest of numbers
        template <class T>
        int leftSortedLen(vector<int>& nums) {
            auto i = nums.begin();
            while ( i+1 < nums.end() && !T()(*(i+1), *i) ) ++i;
            return i+1 == nums.end()? nums.size() :
              upper_bound(nums.begin(), i, *min_element(i,nums.end(),T()),T()) - nums.begin();
        }
    

    Another version using stack:

        int findUnsortedSubarray(vector<int>& nums) {
            int L = leftSortedLen(nums, false);
            if (L == nums.size()) return 0;
            int R = leftSortedLen((reverse(nums.begin(), nums.end()), nums), true);
            return nums.size() - L - R;
        }
            
        int leftSortedLen(vector<int>& nums, bool isGreater) {
            stack<int> s;
            int curMin = INT_MAX;
            for (int x : nums) {
                if (isGreater) x = -x; // negate value to flip comparison
                if (curMin == INT_MAX and (s.empty() or x >= s.top())) s.push(x); 
                else for (curMin = min(curMin, x); !s.empty() && x < s.top(); s.pop()) 
                           if (s.empty()) break; 
                          
            }
            return s.size();
        }
    

Log in to reply
 

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