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
- 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 of i and 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 N is the size of the array.
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 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).
Also Read - Selection Sort in C
568+ registered 
