Last updated on December 25th, 2024 at 05:05 am

Here, we see the Shortest Unsorted Continuous Subarray LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Shortest Unsorted Continuous Subarray LeetCode Solution

1. Problem Statement

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

Example 1:
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: To arrange the whole array in ascending order, you need to sort [6, 4, 8, 10, 9] in ascending order.

Example 2:
Input: nums = [1,2,3,4]
Output: 0

Example 3:
Input: nums = [1]
Output: 0

2. Coding Pattern Used in Solution

The coding pattern used in this code is Two Pointers. The algorithm uses two pointers (left and right) to traverse the array from both ends simultaneously. The goal is to identify the smallest subarray that, if sorted, would make the entire array sorted. This pattern is commonly used when solving problems that involve finding boundaries or ranges in an array.

3. Explanation of How the Code Works

1. The code iterates through the array from both ends simultaneously using two pointers:
   • One pointer (right) moves from left to right to find the last index where the array is out of order.
   • The other pointer (left) moves from right to left to find the first index where the array is out of order.
2. During the traversal:
   • The max value tracks the largest value seen so far from the left.
   • The min value tracks the smallest value seen so far from the right.
3. If a value is smaller than max (from the left) or larger than min (from the right), the respective pointers (right or left) are updated.
4. Finally, the length of the unsorted subarray is calculated as right - left + 1. If the array is already sorted, the result is 0.

4. Code Implementation in Different Languages

4.1 Shortest Unsorted Continuous Subarray C++

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {

        int n = nums.size();
        int e = 0;
        int maxi = nums[0];
        for(int i=1; i<n; ++i){
            if(nums[i]<maxi) e = i;
            else maxi = nums[i];
        }

        int s = 1;     // taken 1 because return 0-1+1 = 0 when already sorted
        int mini = nums.back();
        for(int i=n-2; i>=0; --i){
            if(nums[i] > mini) s = i;
            else mini = nums[i];
        }
        return e-s+1;
    }
};

4.2 Shortest Unsorted Continuous Subarray Java

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length - 1, left = -1, right = -1,
            max = nums[0], min = nums[len];
        for (int i = 1; i <= len; i++) {
            int a = nums[i], b = nums[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);
    }
}

4.3. Shortest Unsorted Continuous Subarray JavaScript

var findUnsortedSubarray = function(nums) {
    let len = nums.length - 1, left = -1, right = -1,
        max = nums[0], min = nums[len]
    for (let i = 1; i <= len; i++) {
        let a = nums[i], b = nums[len-i]
        a < max ? right = i : max = a
        b > min ? left = i : min = b
    }
    return Math.max(0, left + right - len + 1)
};

4.4. Shortest Unsorted Continuous Subarray Python

class Solution(object):
    def findUnsortedSubarray(self, nums):
        lenN, left, right = len(nums) - 1, -1, -1
        maxN, minN = nums[0], nums[lenN]
        for i in range(1, len(nums)):
            a, b = nums[i], nums[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)

5. Time and Space Complexity

1. Time Complexity: O(n)
2. Space Complexity: O(1)

The code is highly efficient, leveraging the two-pointer technique and constant space to solve the problem in linear time.