Favorite Numbers

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
1 upvote
Asked in company
D.E.Shaw

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
6 3
1 2 1 1 1 1
1 2 1
7 2
3 9 6 9 2 2 4
4 9
Sample Output 1:
7
4
Explanation:
For the first test case, ‘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.

For the second test case ‘arr’ = [3, 9, 6, 9, 2, 2, 4] and ‘favArr’ = [4, 9], then all the subarrays which contains the same elements as the ‘favArr’ are [ 3, 9, 6, 9, 2, 2, 4], [9, 6, 9, 2, 2, 4], [6, 9, 2, 2, 4], [9, 2, 2, 4]. There are total of 4 sub arrays. Hence the answer is 4.
Sample Input 2:
2
7 3
8 9 1 3 2 3 10 
8 3 10
9 2
0 1 2 3 4 5 6 8 9 
0 8
Sample Output 2:
1
2
Hint

Try to think of a brute force approach.

Approaches (2)
Brute Force

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
Time Complexity

O(N^3), Where N is the size of the array ‘arr’.

 

We are iterating over all the subarrays of the array, which will cost O(N^2) time, and for each subarray, we are checking if the subarray contains all elements of favArr which will cost O(N). Hence the total time complexity is O(N^3).

Space Complexity

O(K), Where K is the size of the array ‘favArr’.

 

We are maintaining a map, which will take O(K) space in the worst case. Hence the final space complexity is O(K).

Code Solution
(100% EXP penalty)
Favorite Numbers
Full screen
Console