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:

Both the sizes of the array are equal
Simple return False

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.

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
TOP Interview Coding Problems/Challenges