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.

Table of contents

Introduction

Problem Statement

Naive Approach

C++ Implementation

4.1.

Time Complexity

4.2.

Space Complexity

Can we improve the time complexity?📈

Approach

C++ Implementation

7.1.

Time Complexity

7.2.

Space Complexity

Frequently Asked Questions

Key Takeaways

Last Updated: Mar 27, 2024

Smallest subarray to sort in the given array

Author Yukti Kumari

Introduction

You know that arrays are very basic data structures and are most frequently used due to their simple implementation and multiple use cases.

So, in your entire coding journey, you will encounter many problems based on arrays.

In this article, we will see yet another but quite interesting problem based on arrays and specifically subarrays. We will start by understanding the problem statement by working on examples, and then we will see the approach and thought process.

In the end, you will also see the Code implementation in C++.

Remember, knowing how to analyse the complexity of your code is as important as writing the code itself. To help you with this skill, in the end, you will get to know the time and space complexities with appropriate explanations.

Now, let’s head straight to the problem statement.

Problem Statement

Find the minimum length of the subarray when sorted completely sorts the given array. Print the smallest subarray and its length.

Example -

Suppose we are given the array A[] = { 1,2,3,9,6,7, 5,25,30 }

Then the required minimum length subarray is - {9,6,7,5} having length 4.

This is because if you sort the above subarray, then the entire array gets sorted in ascending order.

So, {9,6,7,5} after sorting becomes {5,6,7,9} and the array A[] becomes {1,2,3,5,6,7,9,25,30} and hence the smallest subarray is of length 4.

An important point to note here is that there can be many subarrays that, when sorted, sorts the entire array. But among all such possible subarrays, our goal is to select the subarray having the minimum length.

Like, in this array A[] = { 1,2,3,9,6,7, 5,25,30 }

The following subarrays which when sorted, sorts the array A[] -

{ 1,2,3,9,6,7, 5}
{2,3,9,6,7, 5}
{9,6,7, 5,25,30}
{9,6,7, 5}

And there can be many more such subarrays.

But the smallest subarray among them is {9,6,7, 5}.

Please try to solve this problem yourself on Coding Ninjas Studio before moving on to the further discussion

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,i-1] is sorted since it matches with B[0,i-1] 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,start-1] and A[end+,n-1], are already sorted.

So, we have to find two things-

An index “start” such that A[0,start-1] is sorted in ascending order.
Another index, “end”, is such that A[end+1,n-1] 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=n-1.
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=n-1 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.