# Number of elements with lower index equal to some element, for all items on an array

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.

• $r=[0,n-1]$? Do you mean $r\in [0,n-1]$? – 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.
• 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? – Mateus Buarque Mar 27 '18 at 15:46