Let's Discuss a question I recently came across, it seems easy but constraints make it too hard (At least for me).
Given an array A of size N, find the maximum size of subarray in which frequency of all the elements are same.
1 <= N <= 3 x 10^5
1 <= A[i] <= 10^9
O(N^2) Approach I guess will be to maintain 2 maps and consider all subarray.
Can be do it better than O(N^2)?
What will be CF difficulty of this question with this constraints?
First of all N is 3 * 10 ^ 5 so you can use compression to reduce the complexity by logN.(Maps will add a logN factor.) Also you cannot use binary search for the answer, as for example; [1, 2, 2, 1, 3, 3, 4, 4, 4, 3, 4, 3] has a subarray (frequency of all elements are the same) of length 6 and 8 but not 7. It also has a subarray (frequency of all elements are the same) with all elements appearing 2 and 4 times but none where this count is 3. So I believe O(N^2) should be the best complexity.
I think we can maintain two maps here for :
-freq of element and freq of these freq
and we can use sliding window after it to check if the window is valid or not , which we can calculate in const time if the map having freq of freq's size is 1 i.e, there is only one freq of elements present in current subarray . If window is valid then find the max size , if not valid then shrink it upto curr element or while its valid.
Am I missing something??
[1, 2, 3, 3, 2, 1] For this case when you get the second 3 it isnt valid but if you shrink it you cannot get the answer which is the entire array.
we can construct frequency array fr of the elements and sort it in descending order. Now to check if a subarray of length L is possible, we need to iterate over all divisors(d) of L . It is possible to construct a subarray of length L with no of distinct elements d if fr[d] >= (L/d).
[1, 2, 3 4, 1, 2, 3, 1, 2, 1] => Array [4, 3, 2, 1] => fr lets consider L = 4 1 2 are d we can use, we cannot construct a subarray of length 4 with 2 distinct elements.Even though fr[2] = 2 >= 4/2 = 2. I think your solution works for subsequences only.
Sorry, I got confused between subarray and subsequence.
yupp right bro
didn't thought of this one ..
1446D2 - Frequency Problem (Hard Version) sounds similar