Solution: Shortest Unsorted Continuous Subarray

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #581 (Medium): Shortest Unsorted Continuous Subarray

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:

• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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);
    }
};