Home » Data Structure » Array Coding Problems

Check if one array is subarray of the other or not in C++

In this article, we are going to see how we can use STL library function equal() to find whether one array is subarray of others or not?
Submitted by Radib Kar, on July 16, 2020

Prerequisite: std::equal() function

Problem statement:

Check if one array is subarray of another or not.

Example

Input 1:
Arr1= [3, 4, 5, 8]
Arr2= [1, 3, 4, 5, 8, 9, 10]

Output:
True
Arr1 is subarray of arr2

Input 2:
Arr1= [3, 4, 5, 8, 9 , 10, 12]
Arr2= [1, 3, 4, 5, 8, 9, 10]

Output:
False
None is subarray of one another

Input 3:
Arr1= [3, 4, 5, 8, 9]
Arr2= [3, 4]

Output:
True
Arr2 is subarray of arr1

Solution

We already saw that we have an STL function equal() that checks whether two ranges have the same elements in order or not. We can use that function to figure out whether an array is subarray of the other one or not. No doubt, if two array sizes are not equal then the smaller size one may have the possibility of being subarray of the bigger array. If their sizes are equal then they can't be a subarray of one another anyway.

So there can be three cases:

1. Both the sizes of the array are equal
   Simple return False
2. arr1 size is greater than arr2
   Check for each range of arr1 having length the same as arr2 whether equal to arr2 or not. If we can find any such range equal to arr2 then arr2 is subarray of arr1. Following is the algorithm for this case.
   

   For i=0 to length(arr1)-length(arr2)
   	If equal(arr2.begin(),arr2.end(), arr1.begin()+i) is true
   	Then return true since we found a range 
       starting from arr1[i] which is equal to arr2
   Return false if no such range is found.
   

3. arr2 size is greater than arr1
   Check for each range of arr2 having length the same as arr1 whether equal to arr1 or not. If we can find any such range equal to arr1 then arr1 is subarray of arr2. Following is the algorithm for this case.
   

   For i=0 to length(arr2)-length(arr1)
   	If equal(arr1.begin(),arr1.end(), arr2.begin()+i) is true
   	Then return true since we found a range 
       starting from arr2[i] which is equal to arr1
   Return false if no such range is found.
   

C++ implantation:

#include <bits/stdc++.h>
using namespace std;

void isSubarray(vector<int> arr1, vector<int> arr2)
{
    if (arr1.size() == arr2.size()) {
        cout << "False\n";
        cout << "None of the Arrays can be subarray one other\n";
        return;
    }

    else if (arr1.size() > arr2.size()) {
        for (int i = 0; i < arr1.size() - arr2.size(); i++) {

            if (equal(arr2.begin(), arr2.end(), arr1.begin() + i)) {
                cout << "True\n";
                cout << "Array2 is subarray of Array1\n";
            }
        }
    }
    else { //arr2.size()>arr1.size()

        for (int i = 0; i < arr2.size() - arr1.size(); i++) {

            if (equal(arr1.begin(), arr1.end(), arr2.begin() + i)) {
                cout << "True\n";
                cout << "Array1 is subarray of Array2\n";
            }
        }
    }
}

int main()
{
    cout << "Enter number of elements for array1\n";
    int n;
    cin >> n;
    
    vector<int> arr1(n);

    cout << "Input the elements\n";

    for (int i = 0; i < n; i++)
        cin >> arr1[i];

    cout << "Enter number of elements for array2\n";
    int m;
    cin >> m;
    
    vector<int> arr2(m);
    cout << "Input the elements\n";

    for (int i = 0; i < m; i++)
        cin >> arr2[i];

    isSubarray(arr1, arr2);

    return 0;
}

Output:

Output1:
Enter number of elements for array1
4
Input the elements
3 4 5 8
Enter number of elements for array2
7
Input the elements
1 3 4 5 8 9 10

True
Array1 is subarray of Array2


Output2:

Enter number of elements for array1
7
Input the elements
3 4 5 8 9 10 12
Enter number of elements for array2
7
Input the elements
1 3 4 5 8 9 10
False
None of the Arrays can be subarray one other

Output3:
Enter number of elements for array1
5
Input the elements
3 4 5 8 9
Enter number of elements for array2
2
Input the elements
3 4
True
Array2 is subarray of Array1