> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/lcci/mian-shi-ti-16.16.md).

# 面试题 16.16

Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n - m (that is, find the smallest such sequence).

Return \[m,n]. If there are no such m and n (e.g. the array is already sorted), return \[-1, -1].

Example:

Input: \[1,2,4,7,10,11,7,12,6,7,16,18,19] Output: \[3,9] Note:

0 <= len(array) <= 1000000

## Solutions

* Similar to `problem 581`, check for detailed explanation.
* **two scanning**

```cpp
class Solution {
public:
    vector<int> subSort(vector<int>& array) {
        if (!array.size()) return {-1, -1};
        int n = array.size();

        int li = -1, minv = INT_MAX; 
        for (int i = n - 1; i >= 0; i--) {
            if (array[i] <= minv)
                minv = array[i];
            else
                li = i;
        }

        int ri = -1, maxv = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (array[i] >= maxv)
                maxv = array[i];
            else
                ri = i;
        }

        return {li, ri};
    }
};
```