Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-21T18:31:16Z https://cs.stackexchange.com/feeds/question/86581 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/86581 0 Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time MatanyaP https://cs.stackexchange.com/users/79599 2018-01-11T12:15:13Z 2018-01-12T13:46:23Z <p>Ok, so I got this for homework and been struggling for a while now. The full assignment requires this:</p> <p>While <strong>N = number of elements</strong> in given array and <strong>n = number of different elements</strong>, </p> <p><strong>init(S,A[1...N])</strong> - accept an array A as input and initialize S data structure in O(Nlogn) time</p> <p><strong>insert(S,x)</strong> - insert the key x to S in $O(\log n)$ time</p> <p><strong>freq(S,x)</strong> - return the number of appearances of x in S, in O(logn) time</p> <p><strong>mostFreq(S)</strong> - return the most frequent element in S, in O(1) time</p> <p>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. </p> <p>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.</p> <p>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.</p> <p>So it's clear I'm pretty lost :) any suggestions?</p> https://cs.stackexchange.com/questions/86581/-/86584#86584 0 Answer by ratchet freak for Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time ratchet freak https://cs.stackexchange.com/users/7470 2018-01-11T13:25:27Z 2018-01-11T14:55:27Z <blockquote> <p>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.</p> </blockquote> <p>That's exactly the solution I would go for. </p> <p>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$.</p> <p>insert becomes </p> <pre><code>if x is in BST then replace &lt;x, freq&gt; with &lt;x, freq+1&gt; in bst if freq+1 &gt; max_freq then max_freq := freq+1 max_x := x endif else insert &lt;x, 1&gt; into bst if max_freq = 0 then max_freq := 1 max_x := x endif endif </code></pre> <p>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.</p>