581.Shortest Unsorted Continuous Subarray

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/solution/

1-Sort and Compare nlogn

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] snums = nums.clone();
        Arrays.sort(snums);
        int start = snums.length, end = 0;
        for(int i = 0; i< snums.length; i++){
            if(snums[i] != nums[i]){
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }
}

2-Using Stack

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack<Integer> stack = new Stack();
        int n = nums.length;
        int left = n, right = 0;
        for(int i = 0; i < n; i++){
            while(!stack.empty() && nums[stack.peek()] > nums[i]){
                left = Math.min(left, stack.pop());
            }
            stack.push(i);
        }
        stack.clear();
        for(int i = n - 1; i >= 0; i--){
            while(!stack.empty() && nums[stack.peek()] < nums[i]){
                right = Math.max(right,  stack.pop());
            }
            stack.push(i);
        }
        return right - left > 0 ? right - left + 1 : 0;
    }
}

3- Same Thinking like stack. But less space needed.

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
        boolean flag = false;
        int n = nums.length;
        for(int i = 1; i< n; i++){
            if(nums[i] < nums[i-1])
                flag = true;
            if(flag)
                minVal = Math.min(minVal, nums[i]);
        }
        flag = false;
        for(int i = n -2; i>=0; i--){
            if(nums[i] > nums[i+1])
                flag = true;
            if(flag)
                maxVal = Math.max(maxVal, nums[i]);
        }
        int left, right;
        for(left = 0;  left < n; left++){
            if(minVal < nums[left])
                break;
        }
        for(right = n -1; right >= 0; right--){
            if(maxVal > nums[right])
                break;
        }
        return right - left < 0 ? 0 :right - left + 1; 
    }
}