Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
1.1.
Example - 
2.
Naive Approach
2.1.
Implementation
2.2.
Output
2.3.
Time Complexity: O(N ^ 2)
2.4.
Space Complexity: O(1)
3.
Efficient Approach
3.1.
Implementation using KMP
3.2.
Output
3.3.
Implementation using Z-Algorithm
3.4.
Output
3.5.
Time Complexity: O(N + M)
3.6.
Space Complexity: O(N+M)
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

The number of times array B appears as a subarray in A

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Problem

Given two arrays A and B of size N and M, respectively, find the number of times array B appears as a subarray in A if we can add some arbitrary constant value to every element in B.

Note: M > 1

Example - 

Input: 

N = 10, M = 5

A = [ 5, 10, 8, 10, 11, 9, 11, 12, 10, 15 ]

B = [ 4, 2, 4, 5, 3 ]

Output:

2

Explanation:

  1. If we add 6 to every element in B, it becomes [ 10, 8, 10, 11, 9 ]. It equals A’s subarray from the 2nd element to the 6th element. 
  2. If we add 7 to every element in B, it becomes [ 11, 9, 11, 12, 10 ]. It equals A’s subarray from the 5th element to the 9th element. 

There are no other subarrays of A equals B after adding some constant value. Thus, the number of times array B appears as a subarray in A is 2.

Input:

N = 8, M = 4

A = [1, 2, 3, 4, 5, 6, 7, 8]

B = [10, 11, 12 ,13]

Output:

5

Naive Approach

We can iterate over every subarray of A of size M and check if the difference of each element of the current subarray and array B is the same or not. If the difference is the same for every element, we can add every element of B by that number to make it equal to the current subarray. In this case, we will increment our answer.

Implementation

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

void solve(int N, int M, int A[], int B[]){
   
    // Initializing answer
    int ans = 0;
   
    // Iterating over the left endpoint of the subarray
    for (int l=0; l<N-M+1; l++){
        int r = l + M;
       
        // Initializing difference
        int dif = A[l] - B[0];
        int flag = 1;
       
        // Iterating over the subarray
        for(int i=l+1; i<r; i++){
           
            // If difference is not equal, break
            if (A[i] - B[i-l] != dif){
                flag = 0;
                break;
            }
        }
       
        // If difference is same for all i, increment ans
        ans += flag;
    }

    // Printing number of times array B appears as a subarray in A
    cout<<ans<<endl;
}

// Driver Code
int main() {
    int N = 10, M = 5;
    int A[] = {5, 10, 8, 10, 11, 9, 11, 12, 10, 15};
    int B[] = {4, 2, 4, 5, 3};
    solve(N, M, A, B);
    return 0;
}

Output

2

Time Complexity: O(N ^ 2)

In this approach, we use a nested loop to iterate over every subarray of size M. In the worst case, this will take O(N ^ 2) time.

Space Complexity: O(1)

We are only using some variables in this approach that will take constant space. Therefore the space complexity is O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Efficient Approach

Prerequisite: KMP Algorithm

Let us look at this problem in another way. We have to check if B exists as a subarray of A or not, but the extra thing is that we can add any value to all B elements. This means that array B is not fixed. Can we try to figure out something that remains constant in the whole process? The difference between consecutive elements.

The difference between consecutive elements of both A and B is the same. If we replace A and B by the difference of their consecutive elements, we will have to check the number of times array B appears as a subarray in A. We can use various string matching algorithms like KMP, Z-algorithm, Rabin Karp to solve this efficiently.

Implementation using KMP

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

vector<int> getLps(int m, int b[]){
 
    // Vector to store the LPS array.
    vector<int>lps(m);
 
    /*
    Prev is the last longest proper prefix
    which is also a suffix
    */
    int prev = 0;
    int ind = 1;
    while (ind < m){
 
        // If both are equal
        if (b[ind]==b[prev]){
            prev++;
            lps[ind]=prev;
            ind++;
        }
 
        /*
        If the current elements are unequal
        And LPS is 0
        */
        else if (prev==0){
            lps[ind]=0;
            ind++;
        }
 
        /*
        If the current elements are unequal
        But LPS is not 0
        */
        else{
            prev = lps[prev-1];
        }
       
    }
    return lps;
}
 
// Function to implement KMP
int kmp(int n, int m, int a[], int b[]){
    vector<int> lps = getLps(m, b);

    // Initializing variables
    int ans = 0;
    int aIdx = 0;
    int bIdx = 0;
 
    while (bIdx < n){
 
        // If both the elements match
        if (a[bIdx] == b[aIdx]){
            aIdx++;
            bIdx++;
        }
        if (aIdx == m){
 
            // This means that the entire pattern has matched
            ans++;
 
            // Updating aIdx to the last element matched.
            aIdx = lps[aIdx-1];
        }
        else if (bIdx < n){
            if (a[bIdx]!=b[aIdx]){
                if (aIdx != 0)
 
                    // Updating lps to the last element matched
                    aIdx = lps[aIdx-1];
                else
 
                    // If no element matched, we move to next index
                    bIdx++;
            }
        }
    }
    return ans;
}

// Number of times array B appears as a subarray in A
void solve(int n, int m, int a[], int b[]){
    int difa[n-1];
    int difb[m-1];
   
    // Storing difference of consecutive elements
    for(int i=0; i<n-1; i++){
        difa[i] = a[i+1]-a[i];
    }
    for(int i=0; i<m-1; i++){
        difb[i] = b[i+1]-b[i];
    }
   
    /*
    Using KMP to find the
    Number of times array B appears as a subarray in A
    */
    int ans = kmp(n-1, m-1, difa, difb);
    cout<<ans<<endl;
}
 
// Driver Code
int main(){
    int N = 10, M = 5;
    int A[] = {5, 10, 8, 10, 11, 9, 11, 12, 10, 15};
    int B[] = {4, 2, 4, 5, 3};
    solve(N, M, A, B);
}

Output

2

Implementation using Z-Algorithm

Prerequisite: Z-algorithm

The Z array for any array ‘Arr’ of length 'N' is an array of size 'N' where the ith element is equal to the maximum number of elements starting from the position ‘i’ that coincide with the starting elements of ‘Arr’. To solve this problem, we can create a Z array of ‘B’ + [some random number] + ‘A’. Now, whenever Z[i] is equal to ‘M’ (the length of B), we will increment our answer by 1 as it will mean the starting ‘M’ characters (which is actually the array B) have matched.

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

#include<iostream>
using namespace std;
 
// Fills Z array for given array
void getZarr(int n, int a[], int Z[])
{
    int left, right, k;
 
    // [left,right] make a window which matches with prefix of s
    left = right = 0;
    for (int i = 1; i < n; ++i)
    {
        // if i>right nothing matches so we will calculate.
        // Z[i] using a naive way.
        if (i > right)
        {
            left = right = i;
 
            while (right<n && a[right-left] == a[right])
                right++;
            Z[i] = right-left;
            right--;
        }
        else
        {

            // k = i-left so k corresponds to number which
            // matches in [left,right] interval.
            k = i-left;
 
            if (Z[k] < right-i+1)
                Z[i] = Z[k];
 
            // For example a = "aaaaaa" and i = 2, right is 5,
            // left is 0
            else
            {
                // else start from right and check manually
                left = i;
                while (right<n && a[right-left] == a[right])
                    right++;
                Z[i] = right-left;
                right--;
            }
        }
    }
}
 
// Function to implement Z-Algo
int ZAlgo(int n, int m, int a[], int b[])
{
    // Create concatenated array
    int concat[n+m+1];
    for(int i=0; i<m; i++){
        concat[i] = b[i];
    }
    concat[m] = -1000000;
    for(int i=m+1; i<n+m+1; i++){
        concat[i] = a[i-m-1];
    }
    int l = n+m+1;
 
    // Construct Z array
    int Z[l];
    getZarr(l, concat, Z);

    int ans = 0;
 
    // now looping through Z array for matching condition
    for (int i = 0; i < l; ++i)
    {
        // if Z[i]  is equal to length of b
        if (Z[i] == m) ans++;
    }
    return ans;
}

// Number of times array B appears as a subarray in A
void solve(int n, int m, int a[], int b[]){
    int difa[n-1];
    int difb[m-1];
   
    // Storing difference of consecutive elements
    for(int i=0; i<n-1; i++){
        difa[i] = a[i+1]-a[i];
    }
    for(int i=0; i<m-1; i++){
        difb[i] = b[i+1]-b[i];
    }
   
    /*
    Using KMP to find the
    Number of times array B appears as a subarray in A
    */
    int ans = ZAlgo(n-1, m-1, difa, difb);
    cout<<ans<<endl;
}


// Driver Code
int main(){
    int N = 10, M = 5;
    int A[] = {5, 10, 8, 10, 11, 9, 11, 12, 10, 15};
    int B[] = {4, 2, 4, 5, 3};
    solve(N, M, A, B);
}

Output

2

Time Complexity: O(N + M)

Both KMP and Z-Algorithm take linear time to find the number of times array B appears as a subarray in A. Therefore, the time complexity of the above approach is O(N + M).

Space Complexity: O(N+M)

We have created two new arrays to store consecutive elements of A and B. This will take O(N + M) space. KMP and Z-Algorithm also use linear space. Therefore the total space complexity is O(N + M).

FAQs

  1. What is the use of the KMP algorithm?
    The KMP algorithm is used to find patterns in long strings. It can be used to search a substring in a string, find the number of unique substrings in a string, find all occurrences of the pattern in the string, etc.
     
  2. What are other similar algorithms?
    Z Algorithm also searches for the given pattern in the string. Both these algorithms have the same space and time complexity, but the Z algorithm is simpler to understand. There is another algorithm called Rabin Karp, which uses O(1) space.
     
  3. What is the LPS array?
    LPS stands for Longest proper Prefix, which is also a Suffix. As the name suggests, LPS[i] stores the longest proper prefix and a substring pat suffix [0:i]. A string’s proper prefix is any other than the entire string itself.

Key Takeaways

In this article, we discussed the approach to finding the number of times array B appears as a subarray in A, given that we can add any constant value to all elements of B. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Check out this problem - Subarray With 0 Sum

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Z Algorithm
Next article
Inappropriate Words Filter
Live masterclass