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.