Shortest Unsorted Continuous Subarray

Problem Statement

The task requires finding a contiguous subarray in an integer array nums. This subarray, when sorted, should render the entire array sorted in a non-decreasing order. The goal is to identify the shortest such subarray and determine its length. This could help visualize how closely an array is to being fully sorted and what minimal changes (in terms of sorting a small segment) are required to completely sort it.

Examples

Example 1

Input:

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

Example 2

Input:

nums = [1,2,3,4]

Output:

0

Example 3

Input:

nums = [1]

Output:

0

Constraints

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105

Approach and Intuition

Analyzing the Problem with Examples

1. Example 1:

   • Input: nums = [2,6,4,8,10,9,15]
   • The subarray that disrupts the sorting is [6, 4, 8, 10, 9]. Sorting this part alone would render the entire array sorted.
   • The length of this subarray is 5.

2. Example 2:

   • Input: nums = [1,2,3,4]
   • The array is already sorted in non-decreasing order. Thus, no subarray sorting is needed.
   • The shortest subarray length would therefore be 0.

3. Example 3:

   • Input: nums = [1]
   • This single-element array trivially satisfies the non-decreasing order requirement.
   • The length of the subarray needed for sorting, in this case, would once again be 0.

Steps to Derive the Solution

1. Identify the first point from the beginning of the array where elements are not in the expected order (increasing).
2. Identify the last point from the end of the array where elements deviate from the desired order.
3. The subarray contained within these two points is the candidate for sorting.
4. Calculate the length of this subarray for the result. If no such points exist (i.e., the entire array is already sorted), the length will be 0.

By adhering to these steps, one can determine the minimal effort required to make the entire array sorted through a localized sort operation.

Solutions

public class Solution {
    public int minimumUnsortedSubarray(int[] elements) {
        int smallest = Integer.MAX_VALUE, largest = Integer.MIN_VALUE;
        boolean unsorted = false;
        for (int i = 1; i < elements.length; i++) {
            if (elements[i] < elements[i - 1])
                unsorted = true;
            if (unsorted)
                smallest = Math.min(smallest, elements[i]);
        }
        unsorted = false;
        for (int i = elements.length - 2; i >= 0; i--) {
            if (elements[i] > elements[i + 1])
                unsorted = true;
            if (unsorted)
                largest = Math.max(largest, elements[i]);
        }
        int start, end;
        for (start = 0; start < elements.length; start++) {
            if (smallest < elements[start])
                break;
        }
        for (end = elements.length - 1; end >= 0; end--) {
            if (largest > elements[end])
                break;
        }
        return end - start < 0 ? 0 : end - start + 1;
    }
}