Minimum Window Sort

Medium·Tagsarraytwo-pointerssorting

Problem Statement

Given an array of numbers, find the length of the shortest continuous subarray that, if sorted in ascending order, would result in the entire array being sorted. Return the length of this shortest subarray. If the array is already completely sorted, return `0`.

Examples

Example 1

Input

arr: [1, 2, 5, 3, 7, 10, 9, 12]

Output

"5"

Why

We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted.

Example 2

Input

arr: [1, 3, 2, 0, -1, 7, 10]

Output

"5"

Why

We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted.

Example 3

Input

arr: [1, 2, 3]

Output

"0"

Why

The array is already sorted.

Constraints

•1 <= arr.length <= 10000
•-10^9 <= arr[i] <= 10^9

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

From the beginning, find the first element that is out of sorting order. Do the same from the end.

Hint 2

The subarray between these two elements is our candidate window. But wait, what if the minimum element inside this candidate window is smaller than the elements preceding it?

Hint 3

Find the maximum and minimum of this candidate subarray. Expand the subarray from the beginning to include any number greater than the minimum of the subarray, and similarly expand from the end to include any number smaller than the maximum.