Is there a fast algorithm for computing the rolling mode of an array of integers?

Question

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).

Answer 1

Maintain two data structures as you move along.

1. A hash $H$ table of frequencies.

2. An array of sets $A$ containing the integers in each frequency. So $A[1]$ is the set of all integers that occur once in the window, $A[2]$ all that occur twice, etc.

When you move the window, you need to do two updates, one to increment a frequency of the new integer and one to decrement the frequency of the integer that left the window. For both the process is similar:

1. Look up the frequency $f$ of the integer in $H$ in $O(1)$ time.

2. Remove the integer from set $A[f]$ and add it to $A[f \pm 1]$ in $O(1)$ time (using hash sets).

3. Increment/decrement the frequency in $H$ in $O(1)$ time.

You don't need to track $A[0]$. The mode is any of the integers in the highest $A[f]$ which is non-empty, which you can keep track of in $O(1)$ time.

The total runtime is $O(n)$.