Shortest Unsorted Continuous Subarray

Ishita Chawla
Last Updated: May 13, 2022

Introduction

Learning Data Structures and Algorithms is critical because it helps in reducing the time and space complexity of the codes and enhances the logical abilities of an individual.  

But just knowing the topics or cramming the questions is of no use until you utilize your concepts and solve a question in two or more different ways. It will allow you to think outside of the box and get a better understanding by applying everything you have learned till now.

Today, we will discuss one such significant problem, Shortest Unsorted Continuous Subarray often asked in several interviews. We will try to solve it using three different approaches. We will gradually improve the time complexity as we proceed.

Problem Statement:

You are given an array, ‘ARR,’ of length ‘N,’ and your task is to determine the shortest length of the subarray such that if this subarray is sorted in increasing order, the entire array will become sorted in the increasing order.

Example

  1. N = 7

ARR = {2, 6, 4, 8, 10, 9, 15}

The length of the shortest continuous unsorted array in this example is equal to 5.

2. N = 5

ARR = {12, 9, 7, 4, 2}

Since the array is completely sorted in descending order, the length of the shortest continuous unsorted array in this example is equal to 5.

3. N = 3

ARR = {2, 3, 4}

    Since the array, is already sorted, the answer, in this case, is 0.

Brute Force Approach

Algorithm

  • In this approach, we consider all possible subarrays that can be formed from the given array, ARR, and check whether this is the shortest unsorted continuous subarray or not. 
  • For every subarray, say ARR[i . . .j], we find the minimum and maximum values lying in that subarray, given by MINI AND MAXI
  • We now have to check whether ARR[0. . .i - 1] and ARR[j + 1. . . N - 1] is sorted or not.
  • Now, we check whether all elements lying in  ARR[0. . .i - 1] are smaller than MINI  and all elements lying in ARR[j + 1. . . N - 1] are larger than MAXI.
  • We check for all possible values ofand j and check for every possible subarray.
  • If these conditions are satisfied, we have obtained our shortest unsorted continuous subarray.
  • The length of this subarray is given by j - i +1.

Implementation

Program

/*C++ program to find the shortest unsorted continuous subarray length using brute force. */
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to check if a subarray is sorted or not.
bool isSorted(vector<int> &arr, int l, int r)
{
    for (int i = l + 1; i < r; i++)
    {
        if (arr[i] < arr[i - 1])
        {
            return false;
        }
    }
    return true;
}

// Function to find the shortest unsorted continuous subarray.
int findUnsortedSubarray(vector<int> &arr)
{
    int n = arr.size();

    // If the array contains only 1 element, the answer will be 0.
    if (n == 1)
        return 0;

    int ans = n;

    // Finding the shortest unsorted continuous subarray.
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            // Checking if the left and right sides of this subarray are sorted or not.
            bool isLeftSorted = isSorted(arr, 0, i);
            bool isRightSorted = isSorted(arr, j + 1, n);
            int mini = INT_MAX, maxi = 0;

            // Finding the minimum and maximum element of the chosen subarray.
            for (int k = i; k <= j; k++)
            {
                mini = min(mini, arr[k]);
                maxi = max(maxi, arr[k]);
            }

            // For the subarray containing the first element, we will only check if the right side of this subarray is sorted or not.
            if (i == 0 && j != n - 1)
            {
                if (isRightSorted && arr[j + 1] >= maxi)
                {
                    if (j == i)
                        ans = 0;
                    else
                        ans = min(ans, j - i + 1);
                }
            }

            // For the subarray containing the last element, we will only check if the left side of this subarray is sorted or not.
            else if (j == (n - 1) && i != 0)
            {
                if (isLeftSorted && arr[i - 1] <= mini)
                {
                    if (j == i)
                        ans = 0;
                    else
                        ans = min(ans, j - i + 1);
                }
            }

            // Otherwise we will have to check for both the left and the right sides as they should be sorted.
            else if (i != 0 && j != (n - 1) && isLeftSorted && isRightSorted && arr[i - 1] <= mini && arr[j + 1] >= maxi)
            {
                if (j == i)
                    ans = 0;
                else
                    ans = min(ans, j - i + 1);
            }
        }
    }

    // Returning the length of the shortest unsorted continuous subarray.
    return ans;
}

int main()
{
    int n, a;
    vector<int> arr;

    // Taking user input.
    cout << "Enter the number of elements: ";
    cin >> n;
    cout << "Enter the elements:\n";
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }

    // Calling the function and printing the answer.
    cout << "The length of the shortest unsorted continuous subarray is " << findUnsortedSubarray(arr);
}

Input

Enter the number of elements: 7

Enter the elements:

2 6 4 8 10 9 15

 

Output

The length of the shortest unsorted continuous subarray is 5.

 

Time Complexity

The time complexity is given by O(N3), where is the size of the array.

The brute force approach stated above uses nested loops to find the length of the shortest unsorted continuous subarray length, so the time complexity will be given by O(N * N * N) or simply O(N3).

Space Complexity

The space complexity is given by O(1).

The approach did not use any extra space, so its space complexity is constant, i.e, O(1).

Using Sorting

Algorithm

  • We make a copy of the original array and sort it.
  • The main idea is to find a mismatch in the values.
  • We start with the first index and store the first index where a mismatch of values occurs. This suggests that we have found the starting point of our subarray.
  • Now, we traverse from the last and store the value of the first index where the mismatch of values occurs. This index marks the end point of our subarray.
  • Since we have the starting and the endpoint of our subarray, we can easily find its length.

Let’s try to understand this with the help of an example:

N = 7

ARR = {2, 6, 4, 8, 10, 9, 15}

The first mismatch from the beginning occurs at index 1.

The first mismatch from the last occurs at index 5.

Thus, the shortest unsorted continuous subarray length is 5 - 1 + 1, which is 5.

Implementation

Program

/*C++ program to find the length of the shortest unsorted continuous subarray using sorting.*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the shortest unsorted continuous subarray.
int findUnsortedSubarray(vector<int> arr, int n)
{
    vector<int> arrSorted;

    // Creating a copy of the original vector and sorting it.
    for (int i = 0; i < n; i++)
    {
        arrSorted.push_back(arr[i]);
    }
    sort(arrSorted.begin(), arrSorted.end());

    // The two indices will store the first and last indices where the values of the 2 vectors do not match.
    int startIndex = -1, endIndex = -1;
    for (int i = 0; i < n; i++)
    {
        if (arrSorted[i] != arr[i])
        {
            startIndex = i;
            break;
        }
    }
    for (int i = n - 1; i >= 0; i--)
    {
        if (arrSorted[i] != arr[i])
        {
            endIndex = i;
            break;
        }
    }

    // Returning the length of the shortest unsorted continuous subarray.
    return ((endIndex - startIndex > 0) ? endIndex - startIndex + 1 : 0);
}

int main()
{
    int n, a;
    vector<int> arr;

    // Taking user input.
    cout << "Enter the number of elements: ";
    cin >> n;
    cout << "Enter the elements:\n";
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }

    // Calling the function and printing the answer.
    cout << "The length of the shortest unsorted continuous array is " << findUnsortedSubarray(arr, n);
}

Input

Enter the number of elements: 5

Enter the elements:

5 4 3 2 1

 

Output

The length of the shortest unsorted continuous subarray is 5.

 

Time Complexity

The time complexity is given by O(N * log N), where is the size of the array.

We have sorted the array, and sorting performs O(N * log N) comparisons when applied to N elements. Thus, the time complexity of this approach is O(N * log N).

Space Complexity

The space complexity is given by O(N), where is the size of the array.

We copy the original array containing N elements, so the extra space consumed is  O(N).

Without Extra Space

Algorithm

  • The concept behind this algorithm is to find the left and right boundary of the subarray by finding the minimum and maximum element of the unsorted subarray. 
  • Since we need to sort the array, our final graph will be increasing. So our first task is to determine the point where the slope of our graph falls because whenever the slope falls, we know that the unsorted array has started.
  • We now determine the minimum element found till the end of the array ARR given by MINI.
  • Similarly, we traverse the array from the last index to find the point where the slope rises and find the maximum element, MAXI, until we reach the array's beginning.
  • Now, we traverse the array once again, find the first element that is larger than MINI, and store its index.
  • Similarly, we traverse the array from the last and find the first element that is smaller than MAXI and store its index.
  • We have the start and endpoints of our subarray, and its length can easily be determined. 

Let us understand this with the help of an example:

N = 7

ARR = {2, 6, 4, 8, 10, 9, 15}

Thus, the length of the shortest possible continuous subarray is given by 

5 - 1 + 1 which is 5.

Implementation

Program

/*C++ program to find the length of the shortest possible continuous subarray without using extra space.*/
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to find the shortest unsorted continuous subarray.
int findshortest(vector<int> arr, int n)
{
    int mini = INT_MAX, maxi = INT_MIN;
    bool sorted = true;

    // Finding the first element where the slope of the graph falls.
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[i - 1])
            sorted = false;
        if (!sorted)
            mini = min(mini, arr[i]);
    }

    // Finding the first element from the last at which the slope of the graph becomes rising.
    sorted = true;
    for (int i = n - 2; i >= 0; i--)
    {
        if (arr[i] > arr[i + 1])
            sorted = false;
        if (!sorted)
            maxi = max(maxi, arr[i]);
    }
    int startIndex, endIndex;

    // Finding the first element from the start, which is just larger than the minimum element.
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > mini)
        {
            startIndex = i;
            break;
        }
    }

    // Finding the first element from the last that is just smaller than the maximum element.
    for (int i = n - 1; i >= 0; i--)
    {
        if (arr[i] < maxi)
        {
            endIndex = i;
            break;
        }
    }

    // Returning the length of the shortest unsorted continuous subarray.
    return ((endIndex - startIndex > 0) ? endIndex - startIndex + 1 : 0);
}

int main()
{
    int n, a;
    vector<int> arr;

    // Taking user input.
    cout << "Enter the number of elements: ";
    cin >> n;
    cout << "Enter the elements:\n";
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }

    // Calling the function and printing the answer.
    cout << "The length of the shortest unsorted continuous array is " << findshortest(arr, n);
}

Input

Enter the number of elements: 4

Enter the elements:

1 6 7 10

 

Output

The length of the shortest unsorted continuous subarray is 0.

 

Time Complexity

The time complexity is given by O(N), where is the size of the array.

The logic consists of 4 loops that traverse the array from 0 to N - 1. So the time complexity is linear and O(N + N + N + N) or O(4 * N), which is nothing but O(N).

Space Complexity

The space complexity is given by O(1).

As we can see, we have not used any extra space to make a copy of the original array or to store the elements. So the space complexity is constant, i.e., O(1).

Key Takeaways

So, this blog discussed the problem of the Shortest Unsorted Continuous Subarray, using 3 different approaches, discussing each approach's time and space complexity. 

To learn more, head over right now to CodeStudio to practice problems on topics like ArraysGreedy, Brute Force and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think