Problem Explanation

The problem asks to find the shortest subarray in a given array that if sorted, the whole array will be sorted.

For example with the array [2, 6, 4, 8, 10, 9, 15], we have to sort the subarray [6, 4, 8, 10, 9] to get [2, 4, 6, 8, 9, 10, 15] which is in ascending order. Therefore, the answer is 5 (length of the subarray).

Approach

The approach to solve this problem is to traverse the given array twice, once from left to right and once from right to left.

During the first traversal, we update the minimum element seen so far whenever we observe a decreasing sequence. During the second traversal, we update the maximum element seen so far whenever we observe an increasing sequence.

Finally, we find the first and last position in the array where the numbers are not in correct position (by comparing the numbers with the minimum and maximum elements found). The subarray between these two positions is the required shortest subarray to be sorted.

Solution

Python

1
2python
3class Solution:
4    def findUnsortedSubarray(self, nums: List[int]) -> int:
5        min_number, max_number = float('inf'), float('-inf')
6        for i in range(1, len(nums)):
7            if nums[i] < nums[i - 1]:
8                min_number = min(min_number, nums[i])
9                max_number = max(max_number, nums[i - 1])
10        for i in range(len(nums) - 2, -1, -1):
11            if nums[i] > nums[i + 1]:
12                min_number = min(min_number, nums[i])
13                max_number = max(max_number, nums[i + 1])
14        left, right = 0, len(nums) - 1
15        while left < len(nums) and nums[left] <= min_number:
16            left += 1
17        while right >= 0 and nums[right] >= max_number:
18            right -= 1
19        return max(0, right - left + 1)

Java

1
2java
3class Solution {
4    public int findUnsortedSubarray(int[] nums) {
5        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
6        boolean flag = false;
7        for (int i = 1; i < nums.length; i++) {
8            if (nums[i] < nums[i - 1])
9                flag = true;
10            if (flag)
11                min = Math.min(min, nums[i]);
12        }
13        flag = false;
14        for (int i = nums.length - 2; i >= 0; i--) {
15            if (nums[i] > nums[i + 1])
16                flag = true;
17            if (flag)
18                max = Math.max(max, nums[i]);
19        }
20        int l, r;
21        for (l = 0; l < nums.length; l++) {
22            if (min < nums[l])
23                break;
24        }
25        for (r = nums.length - 1; r >= 0; r--) {
26            if (max > nums[r])
27                break;
28        }
29        if (r - l < 0)
30            return 0;
31        return r - l + 1;
32    }
33}

C++

1
2cpp
3class Solution {
4public:
5    int findUnsortedSubarray(vector<int>& nums) {
6        int mini = INT_MAX;
7        int maxi = INT_MIN;
8        bool meetDecrease = false;
9        bool meetIncrease = false;
10
11        for (int i = 1; i < nums.size(); ++i) {
12            if (nums[i] < nums[i - 1])
13                meetDecrease = true;
14            if (meetDecrease)
15                mini = min(mini, nums[i]);
16        }
17
18        for (int i = nums.size() - 2; i >= 0; --i) {
19            if (nums[i] > nums[i + 1])
20                meetIncrease = true;
21            if (meetIncrease)
22                maxi = max(maxi, nums[i]);
23        }
24
25        int l;
26        for (l = 0; l < nums.size(); ++l)
27            if (nums[l] > mini)
28                break;
29
30        int r;
31        for (r = nums.size() - 1; r >= 0; --r)
32            if (nums[r] < maxi)
33                break;
34
35        return l < r ? r - l + 1 : 0;
36    }
37};

C#

1
2csharp
3public class Solution {
4    public int FindUnsortedSubarray(int[] nums) {
5        int min = int.MaxValue, max = int.MinValue;
6        bool flag = false;
7        for (int i = 1; i < nums.Length; i++) {
8            if (nums[i] < nums[i - 1])
9                flag = true;
10            if (flag)
11                min = Math.Min(min, nums[i]);
12        }
13        flag = false;
14        for (int i = nums.Length - 2; i >= 0; i--) {
15            if (nums[i] > nums[i + 1])
16                flag = true;
17            if (flag)
18                max = Math.Max(max, nums[i]);
19        }
20        int l, r;
21        for (l = 0; l < nums.Length; l++) {
22            if (min < nums[l])
23                break;
24        }
25        for (r = nums.Length - 1; r >= 0; r--) {
26            if (max > nums[r])
27                break;
28        }
29        if (r - l < 0)
30            return 0;
31        return r - l + 1;
32    }
33}

Javascript

1
2javascript
3var findUnsortedSubarray = function(nums) {
4    let min = Infinity, max = -Infinity;
5    let flag = false;
6    for (let i = 1; i < nums.length; i++) {
7        if (nums[i] < nums[i - 1])
8            flag = true;
9        if (flag)
10            min = Math.min(min, nums[i]);
11    }
12    flag = false;
13    for (let i = nums.length - 2; i >= 0; i--) {
14        if (nums[i] > nums[i + 1])
15            flag = true;
16        if (flag)
17            max = Math.max(max, nums[i]);
18    }
19    let l, r;
20    for (l = 0; l < nums.length; l++) {
21        if (min < nums[l])
22            break;
23    }
24    for (r = nums.length - 1; r >= 0; r--) {
25        if (max > nums[r])
26            break;
27    }
28    if (r - l < 0)
29        return 0;
30    return r - l + 1;
31};

This approach iterates over the array twice, once forward and once backward, while updating the minimum and maximum values seen so far. Lastly using this minimum and maximum values we find the first and last out-of-place elements, which marks the boundary of the subarray we want to sort.

The reason why this works is because if a number is smaller than the maximum number seen so far, it must be included in the subarray that needs to be sorted in order to make the complete array sorted. Same goes for the left boundary.

Let's simplify this with an example: [2, 6, 4, 8, 10, 9, 15]

• When we iterate over this array from the right, the maximum value seen is continuously updated until we reach the first number smaller than max, marking the right boundary of the subarray.
• The same process is repeated from the left, with the only difference of updating min and checking if the current number is greater than min, marking the left boundary of the subarray.

This solution only needs to run two passes over the array, so the time complexity is O(n), where n is the length of the array. The space complexity of this solution is O(1), because no extra data structure is used.

In conclusion, sorting the shortest subarray can be achieved by performing two traversal of the array, finding the minimum and maximum encountered so far, and then determining the first and last out-of-place positions in the array corresponding to these min and max values.

Remember: In this specific problem, decreasing (from left to right) and increasing (from right to left) sequences indicate wrongly positioned elements that should be included in our to-be-sorted subarray. These elements are the ones that dictate the start-end indexes of the subarray in the original array. The algorithm has been implemented above in Python, Java, Javascript, C++ and C# programming languages.