I am solving problems on mo's algorithm and came across this problem FREQ2. I am using an array (inv_freq) where inv_freq[x] stores the no of distinct elements having frequency x along with a dynamically updated square root decomposed array of this to find the max frequency. I believe its complexity is O((Q+N)*sqrt(N)). My solution is timing out. Can someone help with a better way to find this maximum?
UPDATE: I saw this idea which uses an array where array[x] is the number of elements having frequency more than x which can be incremented and decremented with single addition of element or deletion of element to our range and binary searching over this array to find the maximum frequency.
Auto comment: topic has been updated by harsha_1_2 (previous revision, new revision, compare).
This problem can be done in $$$\mathcal{O}(N\sqrt{N})$$$ simply by using MO's algorithm (without even using binary search).
You should already know that MO's algorithm makes use of a sliding window.
The trick here is, to view your window as two parts. Part A consists of everything from the left pointer to the edge of the next bucket and Part B consists of everything else.
You simply keep the frequencies of the element in Part B and the most frequent element in Part B as well. For Part A, we can update it by brute force. To illustrate, we split a query [L, R] (that spans more than one bucket) into [L, M) and [M, R]. M is the index of the first element of the bucket no. L / (Block size) + 1.
Part A consists of elements in [L, M) and Part B consists of elements in [M, R]. It is trivial to handle Part B (we just add elements into our window). For Part A, we also add the elements into our window and compute the final answer after combining it with Part B. BUT, the trick here is to delete the elements in Part A after we have computed the answer for the current query.
Repeat this procedure for every query in the same bucket. Obviously, we can reset the statistics after every bucket.
Can you please explain it in a more detailed way.it would be very helpful. What happens when we need to delete the element.then how will we find the maximum frequency element?
In the method that he exposes, we do not need to remove any element, part A should add the $$$O(\sqrt n)$$$ new candidates in addition to the only one from part B. You can see this idea explained by Sergey Kulik here