Let $A$ be an array of size $n$, and $f(i, r, a_r)$ be the number of indices $k$ such that $a_k$ = $a_r$ and $i \le k \le r$.

Example to clarify:

Imagine the array: $[1, 2, 3, 2, 2, 3, 4, 5]$. $f(0, 3, a_3)$, for example, would be equal to 2, because there are 2 elements in the array that appear before $a_3$ (which is 2) and are equal to it.

I've heard one of my colleagues talk about using a Fenwick Tree, but I don't see how that could be done.

I'd like to know if there´s a way to solve this problem in $O(n)$. By solving it I mean finding every value of $f$ for a fixed $i = 0$ and $r = [0, n-1]$

Space isn't really a problem, as long as it's polynomial.

  • $\begingroup$ $r=[0,n-1]$? Do you mean $r\in [0,n-1]$? $\endgroup$ – xskxzr Mar 27 '18 at 15:46

Do a linear scan over the array, and use a hashtable. Each time you see an element, add it to the hashtable (with a count of 1) if it's not already present, or increment the count of the item in the hashtable if it is already present. As you see each element $a_r$, you can compute $f(0,r,a_r)$ by looking up $a_r$ in the hashtable and finding its count, and then record this value of $f$. This will lead to an expected running time of $O(n)$ if you use a suitable hash function.

If you want deterministic running time, use a balanced search tree instead of a hashtable; that will achieve $O(n \log n)$ worst-case running time.

  • $\begingroup$ Sorry for my ignorance, i don't have much experience with hash tables. If i wanted to make the array $[f(0,0),f(0,1),f(0,2)...]$, how would i obtain it from the hastable? $\endgroup$ – Mateus Buarque Mar 27 '18 at 15:46
  • $\begingroup$ @MateusBuarque, see updated answer. $\endgroup$ – D.W. Mar 27 '18 at 17:10
  • $\begingroup$ i tried to make the hastable, but there´s a problem: when i look up ar in it, it counts the total number of ocorrunces of ar, not just the number of ocurrences with index lower than r (which is what the function f means). Is there a way to obtain the right answer? $\endgroup$ – Mateus Buarque Apr 4 '18 at 11:55
  • $\begingroup$ @MateusBuarque, oops, I had an error in my answer. See revised answer. The key is to do the lookup as you go, not at the end. Sorry about my mistake. $\endgroup$ – D.W. Apr 4 '18 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.