0
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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.