InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Given two unsorted arrays. Check if the second array is a subarray of the first array. |
|
Answer» Example: Input : We use two pointers to explore both the ARRAY and the subarray. We maintain the pointer of array arr2[] and increase the pointer of both ARRAYS if any element of arr1[] matches the first element of arr2[], otherwise set the pointer of arr1 to the next element of the previous starting point and reset the pointer of arr2 to 0. If all of arr2's elements match, print True; otherwise, print False. The following is how the above strategy is put into action: Code: #include <bits/stdc++.h>using namespace std; //function to check if the second array is a subarray of the first arraybool checkSubArray(int arr1[], int arr2[], int n, int m){ int i = 0, j = 0; while (i < n && j < m) { // If element matches // increment both pointers if (arr1[i] == arr2[j]) { i++; j++; // checking if we have REACHED the end of the second array if (j == m) return true; } else { i = i - j + 1;// setting the pointer of the first array to the next element of the previous starting point j = 0; // resetting the pointer of the second array to 0. } } return false;}int main(){ int arr1[] = { 2, 3, 0, 5, 1, 1, 2 }; int arr2[] = { 3, 0, 5, 1 }; int n = sizeof(arr1) / sizeof(arr1[0]); int m = sizeof(arr2) / sizeof(arr2[0]); bool res = checkSubArray(arr1, arr2, n, m); if (res) cout << "True\n"; else cout << "False\n"; return 0;}In the above code, the function checkSubArray checks whether the second array is a sub array of the first array or not and returns the output correspondingly. We maintain two pointers, one for the first array and the other for the second array. If the elements match, we increment both the pointers; otherwise, we reset the pointers. |
|