Naive Approach
Let’s see the naive approach step by step 

Since, the problem talks about sorting so, in the naive approach, we will first copy the array A[] in some array, say, B[].

Then sort the array B[] in ascending order.

Compare the two arrays, A[] and B[], using two pointers i and j.

Declare two variables  start and end, which denote the starting and ending index of the required subarray. Initialize both as  start=end=1.

Iterate over the arrays until i<j.

On each iteration check if A[i]==B[i] and A[j]==B[j]. If both are true, then increment pointer i by 1 and decrement j by 1 i.e., i++ and j.

Else, if A[i] is not equal to B[i], then it means that the subarray A[0,i1] is sorted since it matches with B[0,i1] and B is sorted. So, the index i is the starting index of the required subarray that is start=i.

Similarly, if A[j] is not equal to B[j], then this implies that the subarray A[j+1,length(A)1] is sorted as it matches with B[j+1,length(B)1] and B is sorted. Hence, index j is the ending index of the required subarray that is end=j.

The loop should break when  i becomes greater or equal to j, Or both start!=1 and end!=1 is true.
Let’s see the code implementation and the time and space complexity analysis in the next section.
C++ Implementation
/*C++ code to find the Smallest subarray to sort in the given array
*/
#include <bits/stdc++.h>
using namespace std;
pair<int, int> smallestSubArrayToSort(int A[], int n)
{
pair<int, int> subArray;
int start, end;
start = end = 1;
int B[n];
// copying array A to B
for (int i = 0; i < n; i++)
{
B[i] = A[i];
}
// sorting array B
sort(B, B + n);
int i, j;
i = 0;
j = n  1;
while (i < j)
{
if (start != 1 && end != 1)
break;
if (start == 1 && A[i] != B[i])
start = i;
if (end == 1 && A[j] != B[j])
end = j;
i++;
j;
}
subArray.first = start;
subArray.second = end;
return subArray;
}
int main()
{
int n = 9;
int A[n] = {1, 2, 3, 9, 6, 7, 5, 25, 30};
int start, end;
pair<int, int> subArray = smallestSubArrayToSort(A, n);
start = subArray.first;
end = subArray.second;
cout << "The length of the smallest subarray to sort in the given array is: " << end  start + 1 << " and the subarray is: \n";
for (int i = start; i <= end; i++)
{
cout << A[i] << " ";
}
cout << endl;
}
Output
The length of the smallest subarray to sort in the given array is: 4, and the subarray is:
9 6 7 5
Time Complexity
O(n + nlogn) which is O(nlogn) where n = number of elements in the given array.
Sort the array B[] takes O(nlogn) time and comparing the array A[], and B[] takes O(n) time.
Hence, the total time complexity is O(n + nlogn) which is approximately O(nlogn).
Space Complexity
O(n), where n = number of elements in the given array as we use array B[] of size n to sort and compare the elements of the given array.
Can we improve the time complexity?📈
Notice that you are not required to sort the whole array in this problem. Even without sorting the given array, you can find the smallest subarray to sort.
How? 💡
Suppose the required smallest subarray is A[start, end], then it is clear that the subarrays before and after this subarray, i.e. A[0,start1] and A[end+,n1], are already sorted.
So, we have to find two things

An index “start” such that A[0,start1] is sorted in ascending order.

Another index, “end”, is such that A[end+1,n1] is sorted in ascending order.
In the next section, you will see how to find both these indexes in linear time. Before moving on, I recommend you to think about this and try to find it out on your own.
Approach
The approach is pretty straightforward.
The steps are as follows:

Traverse the array A[] from left to right i.e. from i=0 to i=n1.

Store the maximum element found so far in the variable max_so_far and store the last index i for which A[i]<max_so_far in the variable end.

Traverse the array from right to left, i.e. from i=n1 to i=0.

Store the minimum element found so far in the variable min_so_far and store the last index i for which A[i]>min_so_far in the variable start.

The required subarray is A[start, end].
Let’s see the code implementation along with the analysis of time and space complexity in the next section.
C++ Implementation
/*C++ code to find Smallest subarray to sort in the given array in
O(n) time and constant space*/
#include <bits/stdc++.h>
using namespace std;
pair<int, int> smallestSubArrayToSort(int A[], int n)
{
pair<int, int> subArray;
int start = 1, end = 1;
int max_so_far = INT_MIN;
for (int i = 0; i < n; i++)
{
if (max_so_far < A[i])
{
max_so_far = A[i];
}
if (A[i] < max_so_far)
{
end = i;
}
}
int min_so_far = INT_MAX;
for (int i = n  1; i >= 0; i)
{
if (min_so_far > A[i])
{
min_so_far = A[i];
}
if (A[i] > min_so_far)
{
start = i;
}
}
subArray.first = start;
subArray.second = end;
return subArray;
}
int main()
{
int n = 9;
int A[n] = {1, 2, 3, 9, 6, 7, 5, 25, 30};
int start, end;
pair<int, int> subArray = smallestSubArrayToSort(A, n);
start = subArray.first;
end = subArray.second;
if (start != 1)
{
cout << "The length of the smallest subarray to sort in the array A[] is: " << end  start + 1 << " and the subarray is: ";
for (int i = start; i <= end; i++)
{
cout << A[i] << " ";
}
cout << endl;
}
else
{
cout << "Array is already sorted\n";
}
int B[n] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
subArray = smallestSubArrayToSort(B, n);
start = subArray.first;
end = subArray.second;
if (start != 1)
{
cout << "The length of the smallest subarray to sort in the array B[] is: " << end  start + 1 << " and the subarray is: ";
for (int i = start; i <= end; i++)
{
cout << A[i] << " ";
}
cout << endl;
}
else
{
cout << "Array B[] is already sorted.";
}
}
Output
The length of the smallest subarray to sort in the array A[] is: 4, and the subarray is: 9 6 7 5
Array B[] is already sorted.
Time Complexity
O(n) where n = the number of elements in the given array, as we iterate over the entire array twice to find the indexes start and end. Hence, the time complexity is O(n).
Space Complexity
O(1), as we don’t use any extra space.
Frequently Asked Questions

What are the subarrays of an array?
Subarrays are arrays within another array. Subarrays contain contiguous elements of an array.

How many Subarrays are in an array?
The number of all possible subarrays of an array of size N is N * (N + 1)/2.

How many subsets does an array have?
An array of size N has a 2^N number of subsets.

What is the difference between Subarray and subsequence?
A subarray has Order and Continuity which implies they are contiguous whereas a subsequence has Order but not Continuity. So, subsequences need not be contiguous.
Key Takeaways
In this article, we learnt to solve an interesting problem based on arrays and specifically subarrays. We started by understanding the problem statement by working on examples and then we also saw the two approaches and thought processes.
In the end, we also saw the Code implementation in C++ along with analysis of time and space complexities.
To learn arrays from scratch, you can check this amazing course  Learn Arrays.
Practice makes perfect✨. So, you must practice TOP ARRAY CODING INTERVIEW QUESTIONS from to crack product basecd companies smoothly.
Recommended Problems 
Are you planning to ace the interviews of reputed productbased companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!