Given an integer array nums, we have to find one subarray (contiguous elements of an array) that if we sort only this array in ascending order, the whole will be sorted in ascending order.
Return the start and end indices of shortest such array. If the array is already sorted, return [1, 1].
Example 1
 Input: nums = [1,2,6,4,7,8,10,9,12]
 Output: [2,7]
 Explanation: If we sort the subarray [6,4,7,8,10,9], the whole array will get sorted.
Example 2
 Input: nums = [4,6,8,10]
 Output: [1, 1]
 Explanation: The array is already sorted in ascending order.
Approach 1: Sorting
Idea
If we sort the given array and check in which indices (from both start and end) where the elements start mismatching with original array, we can say if we sort the subarray form by those indices, the whole array will get sorted.
Implementation
We will create new sorted array and find the left most and right nost indices simply by comparing the elements.
vector<int> findUnsortedSubarray(vector<int>& nums) {
vector<int> sortedArray = nums;
sort(sortedArray.begin(), sortedArray.end());
int start = 1, end = 1;
for (int i = 0; i < (int)nums.size(); ++i) {
if (nums[i] != sortedArray[i]) {
start = i;
break;
}
}
for (int i = (int)nums.size()  1; i >= 0; i) {
if (nums[i] != sortedArray[i]) {
end = i;
break;
}
}
return {start, end};
Complexity Analysis
 Time Complexity: $O(NlogN)$ for sorting (where $N=$ the length of the array)
 Space Complexity: $O(N)$ since we are copying the array (for sorting, assuming quick sort is used the space complexity is $O(logN)$).
Approach 2: Traversing from Both End
Idea
In the above solution, we are sorting the array even if the only small part of the array is unsorted. So, we can try finding the first outoforder element without sorting.

Finding the first outoforder elements
 We will scan the array from left to right array and find the element which is smaller than the previous element. Let’s say this index is $S$.
 Then, we will perform similar steps but from right to left. If an element is greater than the next element, we will keep track of this index. Let’s say this index is $E$.

Check whether sorting the subarray formed by those outoforder elements sort the array
 Find the minimum and maximum elements formed by $S$ and $E$ (nums[S…E]). Let’s denote them by currentMinima and currentMaxima.
 If there is any element in the first part of the array (nums[0…S]) which is greater the currentMinima, update $S$ with this index.
 Similarly, if there is any element in the last part of the array(nums[E + 1…N]), which is smaller than the currentMaxima, update $E$ with this index.
Implementation
vector<int> findUnsortedSubarray(vector<int>& nums) {
int startSubarrayIdx = 1, endSubarrayIdx = 1;
int n = nums.size();
for (int i = 0; i < n  1; ++i) {
if (nums[i] > nums[i + 1]) {
startSubarrayIdx = i;
break;
}
}
if (startSubarrayIdx == 1) {
return {1, 1};
}
for (int i = n  1; i >= 1; i) {
if (nums[i] < nums[i  1]) {
endSubarrayIdx = i;
break;
}
}
int currentMaxima = INT_MIN, currentMinima = INT_MAX;
for (int i = startSubarrayIdx; i <= endSubarrayIdx; ++i) {
currentMaxima = max(currentMaxima, nums[i]);
currentMinima = min(currentMinima, nums[i]);
}
for (int i = 0; i < startSubarrayIdx; ++i) {
if (nums[i] > currentMinima) {
startSubarrayIdx = i;
break;
}
}
for (int i = n  1; i >= endSubarrayIdx + 1; i) {
if (nums[i] < currentMaxima) {
endSubarrayIdx = i;
break;
}
}
return {startSubarrayIdx, endSubarrayIdx};
}
Complexity Analysis
 Time Complexity: $O(N)$, we are traversing the array twice at the worst case
 Space Complexity: $O(1)$, only constant extra space is used
Approach 3: Traversing from Both End  Simpler
Idea
We can simplify the above approach by keeping track of the maximum found element (from left) and minimum found element (from right).
 When traversing from left to right, if we find an element that is greater than the current maxima, we will update the current maxima with this value. If the current element is greater than the current maxima, we will keep track of the index. This simply means the current element does not follow the ascending order rule as thus outoforder. Say this index is $E$.
 When traversing from right to left, if we find an element that is lesser than the current minima, we will update the current minima with this value. If the current element is lesser than the current minima, we will keep track of the index. Again, this element does not follow the ascending order rule. Say this index is $S$.
Once the traversal is complete, the answer will be $[S, E]$.
Implementation
vector<int> findUnsortedSubarray(vector<int>& nums) {
int startSubarrayIdx = 1, endSubarrayIdx = 1;
int currentMaxima = INT_MIN, currentMinima = INT_MAX;
for (int i = 0; i < (int)nums.size(); ++i) {
currentMaxima = max(currentMaxima, nums[i]);
if (currentMaxima > nums[i]) {
// this element is out of order
endSubarrayIdx = i;
}
}
if (endSubarrayIdx == 1) {
return {1, 1};
}
for (int i = (int)nums.size()  1; i >= 0; i) {
currentMinima = min(currentMinima, nums[i]);
if (currentMinima < nums[i]) {
// this element is out of order
startSubarrayIdx = i;
}
}
return {startSubarrayIdx, endSubarrayIdx};
}
Complexity Analysis
 Time Complexity: $O(N)$, we are traversing the array twice
 Space Complexity: $O(1)$, only constant extra space is used