### bihariforces's blog

By bihariforces, history, 5 weeks ago,

Mode of an array is the most frequent element, mode frequency is frequency of most frequent element.

For example, $[1,3,5,5]$ has mode $5$ and it's frequency is $2$ so mode frequency of this array is $2$.

For an array of length $N$ we need to find sum of mode frequency of all subarrays.

Is there any way to do this better than $O(N^2)$?

• +32

 » 4 weeks ago, # |   -6 see codechef last contest question 6
 » 4 weeks ago, # |   -14 A very similar problem was asked in Codechef Starters 136. A slight difference was that the string provided was binary, so there were only two elements you needed to keep a track of, but the overall process of implementation will be the same.
•  » » 4 weeks ago, # ^ |   +24 Not slight difference, binary is simple with prefix sums, I don't see any way to extend this to even ternary, let alone general array.
 » 4 weeks ago, # |   0 Since there are at most $\sqrt N$ different frequencies, so first we collect them, then for each frequency $f$ scan array with two pointers counting start of $f$-segment and end, but I can't immediately see is clean implementation of this because there are many cases where segments start and end.
•  » » 4 weeks ago, # ^ |   0 What will we exactly check for each possible frequency
•  » » » 4 weeks ago, # ^ |   0 Number of pairs $(l,r)$ where it's the mode frequency
•  » » » » 4 weeks ago, # ^ |   0 Then what will be the worst complexity?
•  » » » » » 4 weeks ago, # ^ |   0 The issue I see with this approach is array like 5 5 5 5 has single frequency, but subarrays have 4 of them, if you find a way handle this (maybe scan for values with given freq instead of frequencies itself) it should be $O(n\sqrt n)$
•  » » » » » » 4 weeks ago, # ^ |   0 how to be expert in 8 months
•  » » » » » » 4 weeks ago, # ^ |   0 I still don't get how would you implement counting the pairs when considering a particular frequency.