Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time

Question

Ok, so I got this for homework and been struggling for a while now. The full assignment requires this:

While N = number of elements in given array and n = number of different elements,

init(S,A[1...N]) - accept an array A as input and initialize S data structure in O(Nlogn) time

insert(S,x) - insert the key x to S in $O(\log n)$ time

freq(S,x) - return the number of appearances of x in S, in O(logn) time

mostFreq(S) - return the most frequent element in S, in O(1) time

I was thinking of using a balanced bst, inserting elements from the array one by one, but it would be $O(n \log n)$ and not O(Nlogn) as required.

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

as for the last function (mostFreq) - I have no idea how to deal with it whatsoever. I guess it involves holding some variable that will be updated on each insert, but I got nothing.

So it's clear I'm pretty lost :) any suggestions?

Answer 1

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

That's exactly the solution I would go for.

Store a mapping of $\langle x, freq_x\rangle$ in the BST. Because each $x$ will be unique in the bst you will be able to search for the frequency with just $x$.

insert becomes

if x is in BST then
    replace <x, freq> with <x, freq+1> in bst
    if freq+1 > max_freq then
        max_freq := freq+1
        max_x := x
    endif
else 
    insert <x, 1> into bst
    if max_freq = 0 then
        max_freq := 1
        max_x := x
    endif
endif

You don't really need a tree, instead a hashtable would drop the complexity down to O(1) for every access and O(N) for init.