Skip to main content
Computer Science

Return to Question

edited title
Source Link
Teodor Dyakov
Teodor Dyakov
  • 1.3k
  • 1
  • 13
  • 22

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

I was wondering if there exists an efficient algorithm for calculating the "rolling mode of a set 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).

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

I was wondering if there exists an efficient algorithm for calculating the "rolling mode of a set of an 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).

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

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

Source Link
Teodor Dyakov
Teodor Dyakov
  • 1.3k
  • 1
  • 13
  • 22

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

I was wondering if there exists an efficient algorithm for calculating the "rolling mode of a set of an 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).