Shortest Unsorted Continuous Subarray

You are given an integer array. Your task is to find the shortest continuous subarray such that if you sort only this subarray in ascending order, the entire array will become sorted (in ascending order).

In other words, determine the minimal length of a subarray which when sorted makes the whole array sorted.

Note: If the array is already sorted, return 0.

The problem can be formally described with the following approach:

Let \(n\) be the size of the array. Traverse the array from left to right maintaining the maximum value seen so far. When an element is found that is less than this maximum, mark it as a candidate for the end of the unsorted subarray. Similarly, traverse from right to left maintaining the minimum value seen so far. An element greater than this minimum indicates a candidate for the start index of the unsorted subarray. The answer is \(\text{end index} - \text{start index} + 1\). If no such indices exist, the array is already fully sorted.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the length of the shortest continuous subarray that needs to be sorted. If the array is already sorted, output 0.

7
2 6 4 8 10 9 15

5