Last updated on January 10th, 2025 at 12:18 am

Here, we see a 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

Topics

Array

Companies

Google

Level of Question

Medium

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. Code Implementation in Different Languages

3.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;
    }
};

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

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

3.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)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(1)
Java	O(n)	O(1)
JavaScript	O(n)	O(1)
Python	O(n)	O(1)