Solution: Shortest Unsorted Continuous Subarray
Tags: algorithms, javascript, java, python
Published: 2021-02-25 10:10:09

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/shortest-unsorted-continuous-subarray/discuss/1082138).*

---

#### [Leetcode Problem #581 (*Medium*): Shortest Unsorted Continuous Subarray](https://leetcode.com/problems/shortest-unsorted-continuous-subarray/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given an integer array `nums`, you need to find one **continuous subarray** that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.
>
Return the shortest such subarray and output its length.

---

#### ***Examples:***

>
Example 1:||
|---:|---|
Input:|nums = [2,6,4,8,10,9,15]
Output:|5
Explanation:|You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
>
Example 2:||
|---:|---|
Input:|nums = [1,2,3,4]
Output:|0
>
Example 3:||
|---:|---|
Input:|nums = [1]
Output:|0

---

#### ***Constraints:***
<br />
>
 - `1 <= nums.length <= 10^4`
 - `-10^5 <= nums[i] <= 10^5`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The easiest approach here would be to simply sort a copy of the input array (**N**) and then compare both ends of the two arrays from the outside inward to see how many elements they had in common. The distance between the first discrepancy on either end will be our answer. This solution would be **O(N log N) time**, but we can do better.

To solve this problem in **O(N) time**, we have to consider just how we can tell if one end of an array is properly sorted. For starters, we can easily tell that the left end subarray breaks sort order when an element if smaller than the one before it.

At that point, we know that the subarray is sorted with respect to itself, but what about with respect to the *entire* array? Unfortunately, we can only be sure of this once we've seen every element in the array.

This should point us to our solution: we have to, in essence, iterate backwards from each end of the array in order to find out how many elements on the opposite end are in their proper position. So we will iterate from right to left to figure out how many elements at the left end of the array are correct, and then vice versa from left to right for the right end.

We can do this by keeping track of the **max** (going left to right) and **min** (going right to left) elements seen so far and noting the last time an element wasn't the same as the **max** or **min** values, depending on direction (**left** and **right**).

We can calculate the length of the mid subarray from **left** and **right** and then **return** the answer.

---

#### ***Implementation:***

<br />Rather than performing more calculations on each iteration to store the correct positions for **left** and **right**, we can just store **i** and do our calculation once at the very end instead.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var findUnsortedSubarray = function(N) {
    let len = N.length - 1, left = -1, right = -1,
        max = N[0], min = N[len]
    for (let i = 1; i <= len; i++) {
        let a = N[i], b = N[len-i]
        a < max ? right = i : max = a
        b > min ? left = i : min = b
    }
    return Math.max(0, left + right - len + 1)
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def findUnsortedSubarray(self, N: List[int]) -> int:
        lenN, left, right = len(N) - 1, -1, -1
        maxN, minN = N[0], N[lenN]
        for i in range(1, len(N)):
            a, b = N[i], N[lenN-i]
            if a < maxN: right = i
            else: maxN = a
            if b > minN: left = i
            else: minN = b
        return max(0, left + right - lenN + 1)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int findUnsortedSubarray(int[] N) {
        int len = N.length - 1, left = -1, right = -1,
            max = N[0], min = N[len];
        for (int i = 1; i <= len; i++) {
            int a = N[i], b = N[len-i];
            if (a < max) right = i;
            else max = a;
            if (b > min) left = i;
            else min = b;
        }
        return Math.max(0, left + right - len + 1);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int findUnsortedSubarray(vector<int>& N) {
        int len = N.size() - 1, left = -1, right = -1,
            maxN = N[0], minN = N[len];
        for (int i = 1; i <= len; i++) {
            int a = N[i], b = N[len-i];
            if (a < maxN) right = i;
            else maxN = a;
            if (b > minN) left = i;
            else minN = b;
        }
        return max(0, left + right - len + 1);
    }
};
```