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

• 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();
}
``````

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