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

Also Read - __Selection Sort in C__