import java.util.Arrays;

/*
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

 */

public class Shortest_Unsorted_Continuous_Subarray {

    public static void main(String[] args) {
        Shortest_Unsorted_Continuous_Subarray out = new Shortest_Unsorted_Continuous_Subarray();
        Solution s = out.new Solution();


        int[] input = new int[]{2, 6, 4, 8, 10, 9, 15};
        System.out.println(s.findUnsortedSubarray(input)); // output: 5

        int[] input2 = new int[]{2, 2, 2, 6, 4, 8, 10, 9, 15};
        System.out.println(s.findUnsortedSubarray(input2)); // output: 5

        int[] input3 = new int[]{2, 6, 4, 8, 8, 8, 10, 9, 15};
        System.out.println(s.findUnsortedSubarray(input3)); // output: 7

        int[] sorted = new int[]{1, 2, 3, 4, 5};
        System.out.println(s.findUnsortedSubarray(sorted)); // output: 0
    }

    public class Solution {

        public int findUnsortedSubarray(int[] nums) {

            int[] original = Arrays.copyOf(nums, nums.length);
            Arrays.sort(nums); // o(NlogN)

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

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

            while(right >= 0 && nums[right] == original[right]) {
                right--;
            }

            // @note: key is check final position of left/right
            // one corner case is input is [1,2,3,4]
            return left >= right? 0: right - left + 1;
        }

    }

    public class Solution2 {
        public int findUnsortedSubarray(int[] nums) {

            if (nums == null || nums.length == 0) {
                return 0;
            }

            // logN idea: scan from left to right, compare current with next, if next is smallers, then stop
            //            scan from right to left, compare current with prev, if prev is bigger, then stop
            // failed by: [1,3,2,2,2]

            // idea-2: fix above failure, use a counter for duplicates

            // idea-3: above idea-2 is failed by [1,3,2,3,3], ie, dup count should be applied only when right duplicates are smaller
            // idea-4: above idea-3 is hacky, better to find the localmin and localmax of subarray, then move pointers

            // int dup = 0; // @note: only need to count from right to left scan. left-to-right duplicates are fine
            int left = 0;
            int right = nums.length - 1;

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

            while(right - 1 >= 0 && nums[right] >= nums[right - 1]) {
                right--;
            }

            if (left >= right) {
                return 0;
            }

            // try to find local min/max in subarray [left, right]
            int localMin = Integer.MAX_VALUE;
            int localMax = Integer.MIN_VALUE;
            for (int i = left; i <= right; i++) {
                localMin = Math.min(localMin, nums[i]);
                localMax = Math.max(localMax, nums[i]);
            }

            // adjust [left, right] if possible
            while(left >= 0 && nums[left] > localMin) {
                left--;
            }
            while(right <= nums.length - 1 && nums[right] < localMax) {
                right++;
            }

            return right - left - 1; // @note: here -1, since above 2 while will move left/right at least once for each

            // // decide if to apply duplicate count
            // dup = (right + 1 >= nums.length || nums[left] <= nums[right + 1])? 0: dup;
            // return right - left + 1 + dup;
        }
    }

}

############

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int left = 0, right = nums.length - 1;
        while (left <= right && nums[left] == arr[left]) {
            ++left;
        }
        while (left <= right && nums[right] == arr[right]) {
            --right;
        }
        return right - left + 1;
    }
}

// OJ: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int findUnsortedSubarray(vector<int>& A) {
        int N = A.size(), L = N - 1, R = 0;
        for (int i = N - 2, mn = A.back(); i >= 0; --i) {
            mn = min(mn, A[i]);
            if (mn != A[i]) L = i - 1;
        }
        for (int i = 1, mx = A[0]; i < N; ++i) {
            mx = max(mx, A[i]);
            if (mx != A[i]) R = i + 1;
        }
        return max(0, R - L - 1);
    }
};

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        arr = sorted(nums)
        left, right = 0, len(nums) - 1
        while left <= right and nums[left] == arr[left]:
            left += 1
        while left <= right and nums[right] == arr[right]:
            right -= 1
        return right - left + 1

############

class Solution(object):
  def findUnsortedSubarray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) < 2:
      return 0
    maxs = [float("inf")] * len(nums)
    mins = [float("inf")] * len(nums)
    mins[-1] = nums[-1]
    maxs[0] = nums[0]
    start, end = 0, -2
    for i in range(1, len(nums)):
      maxs[i] = max(maxs[i - 1], nums[i])
    for i in reversed(range(len(nums) - 1)):
      mins[i] = min(mins[i + 1], nums[i])
    for i in reversed(range(1, len(nums))):
      if nums[i] < maxs[i - 1]:
        end = i
        break
    for i in range(len(nums) - 1):
      if nums[i] > mins[i + 1]:
        start = i
        break
    print
    end, start
    return max(end - start + 1, 0)

func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	maxn, minn := math.MinInt32, math.MaxInt32
	left, right := -1, -1
	for i := 0; i < n; i++ {
		if maxn > nums[i] {
			right = i
		} else {
			maxn = nums[i]
		}
		if minn < nums[n-i-1] {
			left = n - i - 1
		} else {
			minn = nums[n-i-1]
		}
	}
	if right == -1 {
		return 0
	}
	return right - left + 1
}

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int length = nums.length;
        int[] sorted = new int[length];
        System.arraycopy(nums, 0, sorted, 0, length);
        Arrays.sort(sorted);
        int low = -1;
        for (int i = 0; i < length; i++) {
            if (nums[i] != sorted[i]) {
                low = i;
                break;
            }
        }
        if (low < 0)
            return 0;
        int high = length;
        for (int i = length - 1; i >= 0; i--) {
            if (nums[i] != sorted[i]) {
                high = i;
                break;
            }
        }
        return high - low + 1;
    }
}

############

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int left = 0, right = nums.length - 1;
        while (left <= right && nums[left] == arr[left]) {
            ++left;
        }
        while (left <= right && nums[right] == arr[right]) {
            --right;
        }
        return right - left + 1;
    }
}

// OJ: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int findUnsortedSubarray(vector<int>& A) {
        int N = A.size(), L = N - 1, R = 0;
        for (int i = N - 2, mn = A.back(); i >= 0; --i) {
            mn = min(mn, A[i]);
            if (mn != A[i]) L = i - 1;
        }
        for (int i = 1, mx = A[0]; i < N; ++i) {
            mx = max(mx, A[i]);
            if (mx != A[i]) R = i + 1;
        }
        return max(0, R - L - 1);
    }
};

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        arr = sorted(nums)
        left, right = 0, len(nums) - 1
        while left <= right and nums[left] == arr[left]:
            left += 1
        while left <= right and nums[right] == arr[right]:
            right -= 1
        return right - left + 1

############

class Solution(object):
  def findUnsortedSubarray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) < 2:
      return 0
    maxs = [float("inf")] * len(nums)
    mins = [float("inf")] * len(nums)
    mins[-1] = nums[-1]
    maxs[0] = nums[0]
    start, end = 0, -2
    for i in range(1, len(nums)):
      maxs[i] = max(maxs[i - 1], nums[i])
    for i in reversed(range(len(nums) - 1)):
      mins[i] = min(mins[i + 1], nums[i])
    for i in reversed(range(1, len(nums))):
      if nums[i] < maxs[i - 1]:
        end = i
        break
    for i in range(len(nums) - 1):
      if nums[i] > mins[i + 1]:
        start = i
        break
    print
    end, start
    return max(end - start + 1, 0)

func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	maxn, minn := math.MinInt32, math.MaxInt32
	left, right := -1, -1
	for i := 0; i < n; i++ {
		if maxn > nums[i] {
			right = i
		} else {
			maxn = nums[i]
		}
		if minn < nums[n-i-1] {
			left = n - i - 1
		} else {
			minn = nums[n-i-1]
		}
	}
	if right == -1 {
		return 0
	}
	return right - left + 1
}

581 - Shortest Unsorted Continuous Subarray

All Problems

All Solutions

Welcome to Subscribe On Youtube

All Problems

All Solutions