581. Shortest Unsorted Continuous Subarray

Description

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 <=.

Solution

Sort, time O(nlog), space O(1)

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        
        int unsortedStart = 0;
        while (unsortedStart < nums.length 
               && nums[unsortedStart] == sorted[unsortedStart]) {
            ++unsortedStart;
        }

        int unsortedEnd = nums.length - 1;
        while (unsortedEnd > unsortedStart  // important! incase all sorted
               && nums[unsortedEnd] == sorted[unsortedEnd]) {
            --unsortedEnd;
        }
        
        return unsortedEnd - unsortedStart + 1;
    }
}

Optimised: two-pointer, time O(n), space O(1)

很妙的解法。
对于一个递增的数组，它的特性是：

• 每一个数字都不小于它左边所有的数字。
• 每一个数字都不大于它右边所有的数字。

所以此题目变成求解：

• end：小于左侧数字们max的最大index，所以需要从左向右遍历；
• start: 大于右侧数字们min的最小index，所以需要从右向左遍历。

然后end - start + 1即为所求。
注意特殊处理原数组已经是sorted的情况哦。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int start = -1; 
        int end = -2;       // tricky
        int max = nums[0];
        int min = nums[nums.length - 1];
        
        for (int i = 0; i < nums.length; ++i) {
            //from left to right, search the current max
            max = Math.max(max, nums[i]);   
            //from right to left, search the current min 
            min = Math.min(min, nums[nums.length - i - 1]); 
            if (nums[i] < max) {
                end = i;
            }
            if (nums[nums.length - i - 1] > min) {
                start = nums.length - i - 1;
            }
        }
        
        return end - start + 1;
    }
}