Last Updated: 5 Oct, 2021

Favorite Numbers

Moderate

Asked in company

Solve now

Problem statement

You are given an array ‘arr’ consisting of integers and an array of favorite numbers ‘favArr’. Your task is to find the number of sub-arrays of 'arr' that includes all the favorite numbers, at least once.

For Example:

You are given, ‘arr’ = [1, 2, 1, 1, 1, 1] and ‘favArr’ = [1, 1, 2], then all the subarrays which contains the same elements as in the ‘favArr’ are [1, 2, 1] , [1, 2, 1, 1], [1, 2, 1, 1, 1], [1, 2, 1, 1, 1, 1], [2, 1, 1], [2, 1, 1, 1], [2, 1, 1, 1, 1]. There are total of 7 sub arrays. Hence the answer is 7.

Input Format:

The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, representing the size of ‘arr’ and ‘favArr’, respectively.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array ‘arr.’

The second line of each test case contains ‘K’ space-separated integers representing the elements of the array ‘favArr.’

Output Format:

For each test case, print a single integer representing the number of subarrays containing the integers in the ‘favArr’ at least once.

Print a separate line of each test case.

Constraints:

1 <= T <= 10
1 <= N <= 10^6
1 <= K <= N
0 <= arr[i], favArr[i] <= 10^9

Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.

Solve now

Approaches

01 Approach

This approach will iterate over all the instances of all arrays and count the number of subarrays that satisfy the condition given.

We will create a checkSubArr(subArr, favDict), where subArr is the subarray that will be checked and facDict is the frequency count of the elements in the favArr

Algorithm:

In the function checkSubArr(subArr, favDict),
- Set nums as the size of favDict
- Iterate num through subArr
  - If num in favDict
    - Decrease favDict[num] by 1
    - If favDict[num] is equal to 0, then decrease nums by 1
- If nums is 0 return True otherwise return False
Initialise an empty dictionary favDict
Set count as 0
Iterate num through favArr
- Increase favDict[num] by 1
Iterate i from 0 to size of arr
- Iterate j from i to size of arr
  - If checkSubArr(arr[i: j + 1], favDict) returns true
    - Increase count by 1
Finally, return count

Solve now

02 Approach

In this approach, we will store the number of occurrences of each integer in the favArr.

We will create two pointers start and end, and store each favourite integer’s occurrences in a map.

Then when we iterate end through the arr, and if we find the element in the map, we decrease its count, and whenever an integer has a count of 0 in the map, that means it is included in our current subarray sufficient times. When all the integers in the map are 0, we add all the subarrays to the answer.

Algorithm:

Initialise an empty dictionary freqNumCount
Iterate num through favNum
- Increase favNum[num] by 1
Set requiredNums as size of favNum
Set right and left as 0
Set solution as 0
While right is less than the size of arr
- If arr[right] is in favNumCount
  - Decrease favNumCount[arr[right]] by 1
  - If favNumCount[arr[right]] == 0
    - Decrease requiredNums by 1
- While requiredNums equal to 0
  - Add size of arr - right to solution
  - If arr[left] is present in favNumCount
    - Increase favNumCount[arr[left]] by 1
    - If favNumCount[arr[left]] is equal to 1
      - Increase requiredNums by 1
  - Increase left by 1
- Increase right by 1
Finally return solution

Solve now