PROBLEM LINK:
Author: bharathg
Editorialist: bharathg
PREREQUISITES:
Maps,2-Pointer
PROBLEM:
Given an array A of size N.find the number of subarrays with greater than K distinct elements in it.
EXPLANATION:
The problem can considered as sigma(number of subarrays starting at position i for all 0<=i<N).
For finding number of subbarrays starting at position i=0,take j=0 and keep on adding the jth element to a MAP until the size of map is <= K(while increasing the value of j).When the size of MAP becomes K+1,one of the required subarray is found(with start=i and end=j). So add N-j to answer(i.e all subarrays with start=0 and j<=end<N).Similarly repeat for for all i<N.
This is O(N^2) solution and gives TLE. So we use two pointer method for updating the map.
After finding number of subbarrays starting at position i, remove the ith element from MAP and continue adding jth element until size of MAP becomes K+1.
This reduces the complexity to O(NlogN) if you use map.
This can be further reduced to O(N) by using unordered_map
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.