Pattern - Frequency Counting

The most common hash map pattern: count how many times each element appears.

freq := empty hash map
for each element in array
    if element in freq
        freq[element] := freq[element] + 1
    else
        freq[element] := 1

After this, freq[x] tells you how many times x appeared. Time: $O(n)$. Space: $O(k)$ where $k$ is the number of distinct elements.