LeetCode 581 - Shortest Unsorted Continuous Subarray

http://bookshadow.com/weblog/2017/05/15/leetcode-shortest-unsorted-continuous-subarray/

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:

1. Then length of the input array is in range [1, 10,000].
2. The input array may contain duplicates, so ascending order here means <=.

X.
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/discuss/103066/Ideas-behind-the-O(n)-two-pass-and-one-pass-solutions

II -- O(n) time two-pass solution

It turns out that the two boundary indices i and j can be found in linear time, if we take advantage of the following three properties:

1. nums[0, i - 1] and nums[j + 1, n - 1] are both sorted.
2. nums[i] != nums_sorted[i] and nums[j] != nums_sorted[j].
3. nums[i - 1] <= min and max <= nums[j + 1], where min and max are the minimum and maximum values of subarray nums[i, j].

The first and third properties guarantee that the subarray nums[0, i - 1] will be exactly the same as subarray nums_sorted[0, i - 1], and the subarray nums[j + 1, n - 1] exactly the same as nums_sorted[j + 1, n - 1], while the second property ensures that i will be the first index at which the two elements of nums and nums_sorted are different and j be the last such index.

Since we aim at the shortest subarrays, from the first property alone, we need to find the two longest sorted subarrays starting at index 0 and ending at index n - 1, respectively. Assume the two subarrays are nums[0, l] and nums[r, n - 1]. If there is overlapping between these two subarrays, i.e.l >= r, then the whole array is sorted so 0 will be returned. Otherwise, the input array is not sorted. However, we cannot say sorting nums[l, r] will leave the whole array sorted, because at this moment the third property may not be satisfied.

To guarantee the third property, assume min and max are the minimum and maximum values of subarray nums[l, r], then we need to decrease l as long as nums[l] > min, and increase r as long as nums[r] < max. After this is done, it can be shown that the second property will be met automatically, and nums[l + 1, r - 1] will be the shortest subarray we are looking for (that is, i = l + 1 and j = r - 1).

Finding the longest subarrays and the maximum and minimum values of the middle subarray takes one-pass. Ensuring the third property requires a second pass. Therefore we have this two-pass solution:

public int findUnsortedSubarray(int[] nums) {
    int l = 0, r = nums.length - 1;
    
    while (l < r && nums[l] <= nums[l + 1]) l++;
        
    if (l >= r) return 0;
    
    while (nums[r] >= nums[r - 1]) r--;
    
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
  
    for (int k = l; k <= r; k++) {
        max = Math.max(max, nums[k]);
        min = Math.min(min, nums[k]);
    }
    
    while (l >= 0 && min < nums[l]) l--;
    while (r < nums.length && nums[r] < max) r++;
        
    return (r - l - 1);
}

---

III -- O(n) time one-pass solution

To understand this one-pass solution, we need to introduce some equivalent mathematical models for describing a sorted array (assuming in ascending order). Suppose the given array is nums with length n, these models are as follows:

1. nums[k] <= nums[k + 1] for all 0 <= k < n - 1.
2. nums[k] == max[k] for all 0 <= k <= n - 1, where max[k] is the maximum value of the subarray nums[0, k].
3. nums[k] == min[k] for all 0 <= k <= n - 1, where min[k] is the minimum value of the subarray nums[k, n - 1].

The first model is the most common one (and probably the most familiar one) while the last two are less common. It's easy to show that the second model is equivalent to the first by noting that for any index k < n - 1, we have max[k] <= max[k + 1], then nums[k] = max[k] <= max[k + 1] = nums[k + 1]. Similar results hold for the third model: nums[k] = min[k] <= min[k + 1] = nums[k + 1].

With these models in place, we can show that if indices i and j satisfy the following conditions, then nums[i, j] will be the shortest subarray we are looking for:

1. i is the smallest index such that nums[i] != min[i];
2. j is the largest index such that nums[j] != max[j].

The proof proceeds by showing that the two conditions above are equivalent to the three properties in part II.

Firstly we will show that the first property in part II is held true. From condition 1, we have nums[k] == min[k] for all 0 <= k < i. Then nums[k] = min[k] <= min[k + 1] = nums[k + 1] for all k < i - 1. By definition, nums[0, i - 1] is sorted. Similarly from condition 2, nums[k] == max[k] for all j < k <= n - 1. Then nums[k] = max[k] <= max[k + 1] = nums[k + 1] for all j < k < n - 1. By definition, nums[j + 1, n - 1] is sorted.

Then we will show the third property is satisfied. Let min_m and max_m be the minimum and maximum values of subarray nums[i, j], respectively, then we have min_m >= min[i] >= min[i - 1] = nums[i - 1] and max_m <= max[j] <= max[j + 1] = nums[j + 1].

Lastly we will show that the second property is also valid. Note that if the first and third properties are both true, then we know the subarray nums[0, i - 1] will be exactly the same as subarray nums_sorted[0, i - 1], and the subarray nums[j + 1, n - 1] exactly the same as nums_sorted[j + 1, n - 1]. In this case just suppose we have nums[i] == nums_sorted[i] and nums[j] == nums_sorted[j], let's see what will happen. Since the subarrays nums[i, n - 1] and nums_sorted[i, n - 1]contain exactly the same elements (though the order may be different), then the minimum element of the former will be the same as the latter. Since nums_sorted[i, n - 1]is sorted in ascending order, we will have min[i] = nums_sorted[i] = nums[i], which contradicts the assumption that nums[i] != min[i]. Similarly we can show that nums[j] == nums_sorted[j] implies nums[j] == max[j], which contradicts the assumption that nums[j] != max[j].

Finding the smallest index i such that nums[i] != min[i] and the largest index j such that nums[j] != max[j] can be done in one-pass, as shown below. Note that we don't really need arrays to hold values for min[r] and max[l], by taking advantage of the recurrence relation min[r] = Math.min(min[r + 1], nums[r]) and max[l] = Math.max(max[l - 1], nums[l]). Also we initialized the indices i and j such that correct results will be returned even if the input array is already sorted (which requires initially j - i + 1 = 0).

public int findUnsortedSubarray(int[] nums) {
    int i = 0, j = -1;
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    
    for (int l = 0, r = nums.length - 1; r >= 0; l++, r--) {
        max = Math.max(max, nums[l]);
        if (nums[l] != max) j = l;
        
        min = Math.min(min, nums[r]);
        if (nums[r] != min) i = r;
    }
    
    return (j - i + 1);
}

https://www.geeksforgeeks.org/minimum-length-unsorted-subarray-sorting-which-makes-the-complete-array-sorted/

1) If the input array is [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], your program should be able to find that the subarray lies between the indexes 3 and 8.

1) Find the candidate unsorted subarray 
a) Scan from left to right and find the first element which is greater than the next element. Let s be the index of such an element. In the above example 1, s is 3 (index of 30).
b) Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order). Let e be the index of such an element. In the above example 1, e is 7 (index of 31).

2) Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.
a) Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max. min and max for [30, 25, 40, 32, 31] are 25 and 40 respectively.
b) Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element. There is no such element in above example 1.
c) Find the last element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element. In the above example 1, e is changed to 8 (index of 35)

3) Print s and e.

    static void printUnsorted(int arr[], int n)

    {

      int s = 0, e = n-1, i, max, min;   

        

      // step 1(a) of above algo

      for (s = 0; s < n-1; s++)

      {

        if (arr[s] > arr[s+1])

          break;

      }

      if (s == n-1)

      {

        System.out.println("The complete array is sorted");

        return;

      }

        

      // step 1(b) of above algo

      for(e = n - 1; e > 0; e--)

      {

        if(arr[e] < arr[e-1])

          break;

      }

        

      // step 2(a) of above algo

      max = arr[s]; min = arr[s];

      for(i = s + 1; i <= e; i++)

      {

        if(arr[i] > max)

          max = arr[i];

        if(arr[i] < min)

          min = arr[i];

      }

        

      // step 2(b) of above algo

      for( i = 0; i < s; i++)

      {

        if(arr[i] > min)

        {  

          s = i;

          break;

        }      

      } 

        

      // step 2(c) of above algo

      for( i = n -1; i >= e+1; i--)

      {

        if(arr[i] < max)

        {

          e = i;

          break;

        } 

      }  

            

      // step 3 of above algo

      System.out.println(" The unsorted subarray which"+

                         " makes the given array sorted lies"+

                       "  between the indices "+s+" and "+e);

      return;

    }

https://blog.csdn.net/Koala_Tree/article/details/78468486
按照我们自己寻找最小子数组的思路来解决。
首先分别设置左、右指针来指示子数组的首和尾，并设置最大值和最小值，（最小值赋大值，最大值赋小值）；
分别左右两方向寻找不符合递增规则的边界索引，期间若左指针l最后等于数组最大索引，则证明数组全部元素均按升序排序；
在找到的界限内寻找内部的最小值和最大值；
左指针向左走，右指针向右走，直到小于界限内最小值后的位置，及大于界限内最大值前的位置。
注意处理好最后返回值。
一次遍历，左、右同时进行；
左边前进记录当前经过元素的最大值，若按照升序规则，则当前遍历元素即为当前最大值；如果二者不相等，则用j记录当前前进的索引；
右边后退记录当前经过元素的最小值，按照升序规则，则当前遍历元素即为当前最小值；如果二者不相等，则用i记录当前后退的索引。
当一次遍历完成，前进的索引记录了不符合升序规则的最大索引，后退的索引记录了不符合规则的最小索引。
注意在给i和j赋初值的时候要考虑数组元素全部按升序排序的情况，返回为0。所以，赋值i和j为不大于0且相差1，如：i = 0, j = -1，或i = -1, j = -2
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int i = 0, j = -1, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;

        for (int l = 0, r = nums.length-1; r >= 0; l++, r--){
            max = Math.max(max, nums[l]);
            if (nums[l] != max) j = l;

            min = Math.min(min, nums[r]);
            if (nums[r] != min) i = r;
        }

        return (j - i + 1);
    }
}
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/discuss/103057/Java-O(n)-Time-O(1)-Space

I use the variables beg and end to keep track of minimum subarray A[beg...end] which must be sorted for the entire array A to be sorted. If end < beg < 0 at the end of the for loop, then the array is already fully sorted.

public int findUnsortedSubarray(int[] A) {
    int n = A.length, beg = -1, end = -2, min = A[n-1], max = A[0];
    for (int i=1;i<n;i++) {
      max = Math.max(max, A[i]);
      min = Math.min(min, A[n-1-i]);
      if (A[i] < max) end = i;
      if (A[n-1-i] > min) beg = n-1-i; 
    }
    return end - beg + 1;
}

Although it looks like a single pass, this is technically two pass solution in a compact form. It processes each entity twice, once forward, once backwards in the same loop. Great implementation and coding magic!
https://leetcode.com/articles/shortest-unsorted-continous-subarray/
http://www.cnblogs.com/grandyang/p/6876457.html

是O(n)的时间复杂度加上O(1)的空间复杂度，博主觉得这实际上是对上面的那种方法进行空间上的优化的结果，用两个变量mx和mn来代替上面的有序数组，我们仔细来分析发现，最小值mn初始化为数组的最后一个数字，最大值mx初始化为了第一个数字，然后我们从第二个数字开始遍历，mx和nums[i]之间取较大值赋值给mx，然后比较此时mx和nums[i]之间的大小关系，如果mx大于nums[i]，就把i赋值给end，那么我们想如果第一个数字小于第二个，mx就会赋值为第二个数字，这时候mx和nums[i]就相等了，不进行任何操作，这make sense，因为说明此时是有序的。mn和nums[n-1-i]之间取较小值赋给mn，然后比较此时mn和nums[n-1-i]之间的大小关系，如果mn小于nums[n-1-i]，就把n-1-i赋值给start，那么什么时候会进行赋值呢，是当倒数第二个数字大于最后一个数字，这样mn还是最后一个数字，而nums[n-1-i]就会大于mn，这样我们更新start。我们可以看出start是不断往前走的，end是不断往后走的，整个遍历完成后，start和end就分别指向了最短无序连续子数组的起始和结束位置

    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size(), start = -1, end = -2;
        int mn = nums[n - 1], mx = nums[0];
        for (int i = 1; i < n; ++i) {
            mx = max(mx, nums[i]);
            mn = min(mn, nums[n - 1 - i]);
            if (mx > nums[i]) end = i;
            if (mn < nums[n - 1 - i]) start = n - 1 - i;
        }
        return end - start + 1;
    }

Approach #3 Using Sorting [Accepted]
http://blog.csdn.net/u014688145/article/details/71948763
对数组进行排序，然后直接进行比较，数组排序的时间复杂度为O(nlogn)，所以整个时间复杂度为O(nlogn)
public int findUnsortedSubarray(int[] nums) { int[] sorted = nums.clone(); Arrays.sort(sorted); int len = 0; for (int i = 0; i < nums.length; i++){ if (nums[i] == sorted[i]) len++; else break; } for (int j = nums.length-1; j >=0; j--){ if (nums[j] == sorted[j]) len++; else break; } return Math.max(0, nums.length-len); }

对数组nums排序，记排序后的数组为snums，数组长度为n

令s = e = -1

从0到n-1枚举i，记满足nums[i] != snums[i]的最小i值为s，最大i值为e

则当s != e时，所求最短连续子数组为nums[s .. e] 

否则，所求子数组为空

def findUnsortedSubarray(self, nums): """ :type nums: List[int] :rtype: int """ snums = sorted(nums) s = e = -1 for i in range(len(nums)): if nums[i] != snums[i]: if s == -1: s = i e = i return e - s + 1 if e != s else 0


Approach #2 Better Brute Force [Time Limit Exceeded]

X.

In the brute force approach, we consider every possible subarray that can be formed from the given array $nums$. For every subarray $nums[i:j]$ considered, we need to check whether this is the smallest unsorted subarray or not. Thus, for every such subarray considered, we find out the maximum and minimum values lying in that subarray given by $max$ and $min$ respectively.

If the subarrays $nums[0:i-1]$ and $nums[j:n-1]$ are correctly sorted, then only $nums[i:j]$ could be the required subrray. Further, the elements in $nums[0:i-1]$ all need to be lesser than the $min$ for satisfying the required condition. Similarly, all the elements in $nums[j:n-1]$ need to be larger than $max$. We check for these conditions for every possible $i$ and $j$ selected.

Further, we also need to check if $nums[0:i-1]$ and $nums[j:n-1]$ are sorted correctly. If all the above conditions are satisfied, we determine the length of the unsorted subarray as $j-i$. We do the same process for every subarray chosen and determine the length of the smallest unsorted subarray found.

• Time complexity : $O(n^3)$. Three nested loops are there.

  public int findUnsortedSubarray(int[] nums) {

    int res = nums.length;

    for (int i = 0; i < nums.length; i++) {

      for (int j = i; j <= nums.length; j++) {

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, prev = Integer.MIN_VALUE;

        for (int k = i; k < j; k++) {

          min = Math.min(min, nums[k]);

          max = Math.max(max, nums[k]);

        }

        if ((i > 0 && nums[i - 1] > min) || (j < nums.length && nums[j] < max))

          continue;

        int k = 0;

        while (k < i && prev <= nums[k]) {

          prev = nums[k];

          k++;

        }

        if (k != i)

          continue;

        k = j;

        while (k < nums.length && prev <= nums[k]) {

          prev = nums[k];

          k++;

        }

        if (k == nums.length) {

          res = Math.min(res, j - i);

        }

      }

    }

    return res;

  }