Shortest Unsorted Continuous Subarray

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.

Example 1:

Input: nums ={2,6,4,8,10,9,15}
Output: 5

Approach

Java

public class ShortestUnsortedContinuousSubarray {
    public static void main(String[] args) {
        int[] nums = { 2, 6, 4, 8, 10, 9, 15 };
        System.out.println(findUnsortedSubarray(nums));
    }
    static int findUnsortedSubarray(int[] nums) {
        int l = 0, r = nums.length - 1;
        fun(nums, l, r);
        return ans;
    }
    static int ans = 0;
    static int[] minMax(int[] nums, int l, int r) {
        int min1 = Integer.MAX_VALUE, max1 = Integer.MIN_VALUE;
        for (int i = l; i <= r; i++) {
            if (nums[i] > max1)
                max1 = nums[i];
            if (nums[i] < min1)
                min1 = nums[i];
        }
        return new int[] { min1, max1 };
    }
    static void fun(int[] nums, int l, int r) {
        int[] f = minMax(nums, l, r);
        if (f[0] == nums[l] && f[1] == nums[r]) {
            l = l + 1;
            r = r - 1;
            if (l < r)
                fun(nums, l, r);
            else {
                ans = 0;
                return;
            }
        } else if (f[0] == nums[l]) {
            l = l + 1;
            if (l < r)
                fun(nums, l, r);
            else {
                ans = 0;
                return;
            }
        } else if (f[1] == nums[r]) {
            r = r - 1;
            if (l < r)
                fun(nums, l, r);
            else {
                ans = 0;
                return;
            }
        } else {
            ans = r - l + 1;
            return;
        }
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
int ans = 0;
vector<int> minMax(vector<int> &nums, int l, int r)
{
    int min1 = INT_MAX, max1 = INT_MIN;
    for (int i = l; i <= r; i++)
    {
        if (nums[i] > max1)
            max1 = nums[i];
        if (nums[i] < min1)
            min1 = nums[i];
    }
    return {min1, max1};
}
void fun(vector<int> &nums, int l, int r)
{
    vector<int> f = minMax(nums, l, r);
    if (f[0] == nums[l] && f[1] == nums[r])
    {
        l = l + 1;
        r = r - 1;
        if (l < r)
            fun(nums, l, r);
        else
        {
            ans = 0;
            return;
        }
    }
    else if (f[0] == nums[l])
    {
        l = l + 1;
        if (l < r)
            fun(nums, l, r);
        else
        {
            ans = 0;
            return;
        }
    }
    else if (f[1] == nums[r])
    {
        r = r - 1;
        if (l < r)
            fun(nums, l, r);
        else
        {
            ans = 0;
            return;
        }
    }
    else
    {
        ans = r - l + 1;
        return;
    }
}
int findUnsortedSubarray(vector<int> &nums)
{
    int l = 0, r = nums.size() - 1;
    fun(nums, l, r);
    return ans;
}
int main()
{
    vector<int> nums = {2, 6, 4, 8, 10, 9, 15};
    cout << findUnsortedSubarray(nums);
    return 0;
}