# Shortest Unsorted Continuous Subarray

__Introduction__

__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:__

__Problem Statement:__You are given an array, ‘* ARR,’* of length

*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.*

**‘N,’**__Example__

__Example__

**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__

__Brute Force Approach__

__Algorithm__

__Algorithm__- In this approach, we consider all possible subarrays that can be formed from the given array,
, and check whether this is the shortest unsorted continuous subarray or not.**ARR** - For every subarray, say
we find the minimum and maximum values lying in that subarray, given by**ARR[i . . .j],**AND**MINI****MAXI** - We now have to check whether
and**ARR[0. . .i - 1]**is sorted or not.**ARR[j + 1. . . N - 1]** - Now, we check whether all elements lying in
are smaller than**ARR[0. . .i - 1]**and all elements lying in**MINI**are larger than**ARR[j + 1. . . N - 1]**.**MAXI** - We check for all possible values of
and**i**and check for every possible subarray.**j** - 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**

**Implementation**

__Program__

__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__

__Input__Enter the number of elements: 7 Enter the elements: 2 6 4 8 10 9 15 |

__Output__

__Output__The length of the shortest unsorted continuous subarray is 5. |

**Time Complexity**

**Time Complexity**

The time complexity is given by * O(N^{3}), *where

*is the size of the array.*

**N**The brute force approach stated above uses * 3 *nested loops to find the length of the shortest unsorted continuous subarray length, so the time complexity will be given by

*or simply*

**O(N * N * N)**

**O(N**^{3}).**Space Complexity**

**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__

__Using Sorting__

__Algorithm__

__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**

**Implementation**

__Program__

__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__

__Input__Enter the number of elements: 5 Enter the elements: 5 4 3 2 1 |

__Output__

__Output__The length of the shortest unsorted continuous subarray is 5. |

**Time Complexity**

**Time Complexity**

The time complexity is given by * O(N * log N), *where

*is the size of the array.*

**N**We have sorted the array, and sorting performs * O(N * log N) *comparisons when applied to

*elements. Thus, the time complexity of this approach is*

**N**

**O(N * log N).****Space Complexity**

**Space Complexity**

The space complexity is given by * O(N), *where

*is the size of the array.*

**N**We copy the original array containing* N* elements, so the extra space consumed is

**O(N).**__Without Extra Space__

__Without Extra Space__

__Algorithm__

__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
given by**ARR****MINI.** - Similarly, we traverse the array from the last index to find the point where the slope rises and find the maximum element,
, until we reach the array's beginning.**MAXI** - Now, we traverse the array once again, find the first element that is larger than
, and store its index.**MINI** - Similarly, we traverse the array from the last and find the first element that is smaller than
and store its index.**MAXI** - 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**

**Implementation**

__Program__

__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__

__Input__Enter the number of elements: 4 Enter the elements: 1 6 7 10 |

__Output__

__Output__The length of the shortest unsorted continuous subarray is 0. |

**Time Complexity**

**Time Complexity**

The time complexity is given by * O(N), *where

*is the size of the array.*

**N**The logic consists of * 4* loops that traverse the array from

*to*

**0***. So the time complexity is linear and*

**N - 1***or*

**O(N + N + N + N)***which is nothing but*

**O(4 * N),**

**O(N).****Space Complexity**

**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__

__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

__Arrays__*,*

__Greedy,__

__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.

Comments

## No comments yet

## Be the first to share what you think