I was wondering if there exists an efficient algorithm for calculating the "rolling mode of an array of integers.
By rolling mode I mean that we have an array of integers of size $n$ and a sliding window of size $k$ and we we want to compute the mode for each window in the array.
There is an algorithm to do this in $O(n*k)$, by using a hash table in which we store the frequency of each integer. We can update this structure in $O(1)$ time, but to find the integer with max frequency we need $O(k)$ which gives the total running time.
I was wondering if there exists a faster algorithm(Perhaps a data structure that can index the values both by frequency and value).