581. Shortest Unsorted Continuous Subarray

import java.util.Arrays;

/**
 * Copy and Sort the input array. (Tell this first in the interview)
 *
 * Time Complexity: O(N log N)
 *
 * Space Complexity: O(N)
 *
 * N = Length of the input nums array.
 */
class Solution1 {
    public int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        int[] numsCopy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(numsCopy);

        int left = 0;
        int right = nums.length - 1;

        while (left < nums.length && nums[left] == numsCopy[left]) {
            left++;
        }
        while (left < right && nums[right] == numsCopy[right]) {
            right--;
        }

        return right - left + 1;
    }
}

/**
 * Two pass Solution (Skip this in interview)
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Length of the input nums array.
 */
class Solution2 {
    public int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        int left = 0;
        while (left < nums.length - 1 && nums[left] <= nums[left + 1]) {
            left++;
        }
        if (left == nums.length - 1) {
            return 0;
        }

        int right = nums.length - 1;
        while (nums[right] >= nums[right - 1]) {
            right--;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = left; i <= right; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }

        while (left >= 0 && min < nums[left]) {
            left--;
        }
        left++;
        while (right < nums.length && max > nums[right]) {
            right++;
        }
        right--;

        return right - left + 1;
    }
}

/**
 * One Pass Solution (Best Solution)
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Length of the input nums array.
 */
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        int left = -1;
        int right = -2;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int len = nums.length;

        for (int i = 0, j = len - 1; i < len; i++, j--) {
            max = Math.max(max, nums[i]);
            if (nums[i] < max) {
                right = i;
            }

            min = Math.min(min, nums[j]);
            if (nums[j] > min) {
                left = j;
            }
        }

        return right - left + 1;
    }
}