Topic describes

This is 581 on LeetCode. Shortest unordered continuous subarray, medium difficulty.

Tag: “sort”, “double pointer”

Given an integer array nums, you need to find a contiguous subarray. If you sort the subarray in ascending order, the entire array will be sorted in ascending order.

Find the shortest subarray that fits the problem and print its length.

Example 1:

Input: nums = [2,6,4,8,10,9,15] output: 5Copy the code

Example 2:

Input: nums = [1,2,3,4] output: 0Copy the code

Example 3:

Input: nums = [1] Output: 0Copy the code

Tip:

  • 1 <= nums.length <=
    1 0 4 10^4

  • –
    1 0 5 10^5     <= nums[i] <=
    1 0 5 10^5

  • Advanced: Can you design a solution with O(n) time complexity?

Double pointer + sort

[I,j][I,j][I,j][I,j] the interval is the answer.

Code:

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) i++;
        while (i <= j && nums[j] == arr[j]) j--;
        return j - i + 1; }}Copy the code
  • O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(n)O(n)O(n)

Dual pointer + linear scan

Another way to do this is to divide the entire array into three segments.

At the beginning, the two-pointer III and JJJ were used to find the segmentation points on the left and right sides that satisfied monotonic increasing.

Namely the [0, I] [0, I] [0, I] and [[j, j, n) n) [j, n) satisfies the requirement of ascending, and the middle section (I, j) (I, j) (I, j) does not ensure an orderly.

Then we traversed the middle part [I,j][I,j][I,j] :

  • Found nums [x] < nums [I – 1] nums [x] < nums nums [I – 1] [x] < nums [I – 1) : Since nums[x] NUMs [x]nums[X]nums[X]nums[I −1]nums[I-1]nums[I −1] will appear after nums[I −1]nums[I −1], the overall ascending order will not be satisfied, so we need to adjust the position of segmentation point III.
  • Found nums [x] > nums nums [m + 1] [x] > nums nums [m + 1] [x] > nums [j + 1) : Since nums[x]nums[x]nums[x] nums[x] will appear before NUMs [j+1]nums[j +1]nums[j +1]nums[j +1] after sorting [I,j][I,j] part, it will not meet the overall ascending order, so we need to adjust the position of the segmentation point JJJ.

Some details: While tweaking III and JJJ, we might reach the edge of the array, where we can set up two sentinels: one small enough to the left of the array, and one large enough to the right.

Code:

class Solution {
    int MIN = -100005, MAX = 100005;
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) i++;
        while (i < j && nums[j] >= nums[j - 1]) j--;
        int l = i, r = j;
        int min = nums[i], max = nums[j];
        for (int u = l; u <= r; u++) {
            if (nums[u] < min) {
                while (i >= 0 && nums[i] > nums[u]) i--;
                min = i >= 0 ? nums[i] : MIN;
            }
            if (nums[u] > max) {
                while(j < n && nums[j] < nums[u]) j++; max = j < n ? nums[j] : MAX; }}return j == i ? 0 : (j - 1) - (i + 1) + 1; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.581 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.