[leetcode] Shortest Unsorted Continuous Subarray

problem

code

1st try

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        
        if (len <= 1) return 0;
        
        int temp = Integer.MIN_VALUE;
        int low = len - 1;
        int high = 0;
        
      	// find low  which is nums[i] > nums[i+1]
        for (int i = 0; i < len; i++) {
            if (nums[i] >= temp) {
                temp = nums[i];
            } else {
                low = i;
                break;
            }
        }
        
      	// find high  which is nums[i] > nums[i+1] backward
        temp = Integer.MAX_VALUE;
        for (int i = len - 1; i >= 0; i--) {
            if (nums[i] <= temp) {
                temp = nums[i];
            } else {
                high = i;
                break;
            }
        }
        
      	// find an index, x, of an element, greater than nums[low]
      	// [1, 3, 3, 3, 2, 2, 2] => low index is 4, x should be 1
        int x = -1;
        for (int i = low; i >= 0; i--) {
            if (nums[i] > nums[low]) {
                x = i;
            }
        }
        
      	// find an index, x, of an element, less than nums[high]
      	// [1, 3, 3, 3, 2, 2, 2] => high index is 3, y should be 6   
        int y = -1;
        for (int i = high; i < len; i++) {
            if (nums[i] < nums[high]) {
                y = i;
            }
        }        
        
        // find min, max in a subarray
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = x; i <= y; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        
      	// find indexes of x and y which is greater and less than min and max in a subarray
        for (int i = x - 1; i >= 0; i--) {
            if (nums[i] > min) x = i;
        }
        for (int i = y + 1; i < len; i++) {
            if (nums[i] < max) y = i;
        }
               
        return x == -1 && y == -1 ? 0 : y - x + 1;
    }
}

Time: O(N)
Space: O(1)
but code is too long

2nd try: using sorting O(nlogn)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    const origin = [...nums];
    nums.sort((a, b) => a - b);

    let start = nums.length;
    let end = 0;
    for (let i = 0; i < nums.length; i++) {
        if (origin[i] != nums[i]) {
            start = Math.min(start, i);
            end = Math.max(end, i);
        }
    }
    
    return end - start >= 0 ? end - start + 1 : 0;
};

Time: O(nlogn), 100 times slower than 1st try

leetcode: 1 loop and O(N) O(1)

def find_unsorted_subarray(nums)
  l,r= 0, nums.length - 1
  min, max = 10001, -10001
  st,nd = 0,-1
  
  while r >=0 do
    nums[l] >= max ? max = nums[l] : nd = l
    nums[r] <= min ? min = nums[r] : st = r

    l += 1
    r -=1
  end
  
  nd - st + 1
end

leetcode: with stack O(N) O(N)

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