Shortest Unsorted Continous Subarray



Another approach. If we find the leftmost violation and rightmost violations first, we could construct the continuous subarray start from here. Let's say the leftmost violation is "left" and rightmost violation is "right", we could find the minimum and maximum of subarray A[left + 1, right  1] in linear time O(right  left  1). If the minimum is larger than A[left] and maximum is smaller than A[right], we are done, we just return "right  left  1". Otherwise, if minimum is smaller than A[left], we set left  and update maximum value. Similarly, if maximum is larger than A[right], we set right ++ and update minimum value. Since "left" and "right" are bounded. The total operations is O(n).
If left reached outside the boundary and right reached outside the boundary, we return the total length of the array.The time complexity is O(n)
Space complexity is O(1)Below is the code implementation.
public int findUnsortedSubarray(int[] nums) {
int i, j, k, left, right; i = 0; j = nums.length  1; for(i = 0; i < nums.length  1; i ++) { if(nums[i] <= nums[i + 1]) continue; // find left violation else break; } if(i == nums.length  1) return 0; left = i; for(j = nums.length  1; j >= 1; j ) { if(nums[j] >= nums[j  1]) continue; // find right violation else break; } if (j == 0) return 0; right = j; int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for(k = left + 1; k <= right  1; k ++) { min = Math.min(min, nums[k]); max = Math.max(max, nums[k]); } if(left + 1 > right  1) { max = nums[left]; min = nums[right]; } while (left >= 0 && right < nums.length) { if (nums[left] > min) { max = Math.max(max, nums[left]); left ; } else { if (nums[right] < max) { min = Math.min(min, nums[right]); right ++; } else { return (right  left  1); } } } if(left ==  1) { while(right < nums.length) { if (nums[right] < max) { min = Math.min(min, nums[right]); right ++; } else { return (right  left  1); } } } if(right == nums.length) { while(left >= 0) { if (nums[left] > min) { max = Math.max(max, nums[left]); left ; } else { return (right  left  1); } } } return nums.length; }
"""