Problem statement:

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:

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.

Solution

public int findUnsortedSubarray(int[] arr) {
    if (arr.length < 2) {
        return 0;
    }

    int lo = 0, hi = arr.length - 1;

    while(lo < arr.length - 1 && arr[lo] <= arr[lo + 1]) {
        lo++;
    }

    if (lo == arr.length - 1) {
        return 0;
    }

    while(hi > 0 && arr[hi] >= arr[hi - 1]) {
        hi--;
    }

    int subarrayMin = arr[lo], subarrayMax = arr[lo];
    for (int i = lo; i <= hi; i++) {
        subarrayMin = Math.min(subarrayMin, arr[i]);
        subarrayMax = Math.max(subarrayMax, arr[i]);
    }

    while (lo > 0 && arr[lo - 1] > subarrayMin) lo--;
    while (hi < arr.length - 1 && arr[hi + 1] < subarrayMax) hi++;

    return hi - lo + 1;
}

Time complexity:

O(n)

Space complexity:

O(1)

Approach:

1. From the beginning and end of the array, find the first elements that are out of the sorting order. The two elements will be our candidate subarray.
2. Find the maximum and minimum of this subarray.
3. Extend the subarray from beginning to include any number which is bigger than the minimum of the subarray.
4. Similarly, extend the subarray from the end to include any number which is smaller than the maximum of the subarray.