bihariforces's blog

Sum of Mode Frequency of all Subarrays
By bihariforces, history, 3 weeks ago, In English

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)$$$?

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

see codechef last contest question 6

→ Reply
»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What will we exactly check for each possible frequency

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Number of pairs $$$(l,r)$$$ where it's the mode frequency

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Then what will be the worst complexity?

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)$$$

          → Reply
          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            how to be expert in 8 months

            → Reply
          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I still don't get how would you implement counting the pairs when considering a particular frequency.

            → Reply