Subarrays With ‘K’ Distinct Values

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
48 upvotes
Asked in companies
Goldman SachsVMware IncD.E.Shaw

Problem statement

You are given an array ‘ARR’ having ‘N’ integers. You are also given an integer ‘K’. The task is to count the number of subarrays that have ‘K’ distinct values.


Subarray: A consecutive sequence of one or more values taken from an array.


For Example : 
‘N’ = 4, ‘K’ = 2
‘ARR’ = [1, 1, 2, 3]

There are ‘3’ subarrays with ‘2’ distinct elements, which are as follows: [1, 2], [2, 3], [1, 1, 2].
Thus, you should return ‘3’ as the answer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two integers, ‘N’ and ‘K’.

The second line contains ‘N’ integers representing the array ‘ARR’.
Output Format : 
Print the number of subarrays that have exactly ‘K’ distinct values.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the function.
Sample Input 1 :
5 2
2 1 3 2 4
Sample Output 1 :
9
Explanation of Sample Input 1 :
There are ‘4’ subarrays with exactly ‘2’ distinct elements, which are as follows: [2, 1], [1, 3], [3, 2], [2, 4].

Thus, you should return ‘4’ as the answer.
Sample Input 2 :
5 4
1 2 3 4 5
Sample Output 2 :
2
Constraints :
1 <= K <= N <= 10^5
1 <= Value in each element of ‘ARR’ <= 10^9

Time limit: 1 second
Hint

Find all the possible subarrays of ‘ARR’.

Approaches (2)
Brute Force Approach

We can generate all the subarrays of ‘ARR’ using two nested loops. In the outer loop, use a hash map to store the distinct values in the subarrays generated in the inner loop. If a subarray ‘[L, R]’ has more than ‘K’ distinct values, then all the subarrays ‘[L, R+1], [L, R+2], .., [L, N-1]’ will also have more than ‘K’ distinct values. So, we don’t need to check these subarrays.

 

Algorithm

 

  • Set ‘COUNT = 0’. Use it to store the count of subarrays with ‘K’ distinct values.
  • Run a loop where ‘L’ ranges from ‘0’ to ‘N - 1’:
    • Create a hash map ‘hashMap’ to store integers. Use it to store the distinct values in the subarrays starting at index ‘L’.
    • Run a loop where ‘R’ ranges from ‘L’ to ‘N-1’ to iterate through all subarrays starting from ‘L’:
      • Insert ‘ARR[R]’ into ‘hashMap’.
      • If ‘hashMap.size() == K’, then the subarray ‘[L, R]’ has ‘K’ distinct elements:
        • ‘COUNT += 1’. The subarray ‘[L, R]’ at most ‘K’ distinct values.
      • If ‘hashMap.size() > K’, then the subarray ‘[L, R]’ has more than ‘K’ distinct elements:
        • Break the loop/
  • Return ‘COUNT’ as the answer.
Time Complexity

O(N^2), where ‘N’ is the size of array ‘ARR’.

 

There are ‘N*(N+1)/2’ possible subarrays, and in the worst-case, every subarray will have at most ‘K’ distinct values. Thus, the time complexity will be ‘O(N^2)’.

Space Complexity

O(N), where ‘N’ is the size of array ‘ARR’.

 

The hash map used in each iteration will store at most ‘N’ values (when all the values in ‘ARR’ are distinct). Thus, the space complexity is ‘O(N)’.

Code Solution
(100% EXP penalty)
Subarrays With ‘K’ Distinct Values
Full screen
Console