Hi, I'm trying to find an algorithm to answer queries to find the most frequent element in a subsegment of an array. I've read this post on StackOverflow, which mentions a method to get $$$O(\sqrt{N})$$$ per query: https://stackoverflow.com/questions/40302407/how-to-find-the-most-frequent-number-and-its-frequency-in-an-array-in-range-l-r.

Basically, the author of the answer says that we can choose a value $$$B = C \cdot \sqrt{N}$$$, and then handle the queries on the subsegment $$$(L, R)$$$ with casework: Case 1. If $$$R - L + 1 < 2 \cdot B$$$, then just loop through every value between $$$L$$$ and $$$R$$$ and take maximum of all frequencies. Case 2. If $$$R - L + 1 \geq 2 \cdot B$$$, then loop through all elements of the array that are "heavy" (aka they appear more than $$$B$$$ times in the entire array) and take the maximum of their frequencies over the interval.

I can see why this approach will work, but I tried using it on this problem and it got WA. I follow basically the same idea in the editorial. I find the rightmost k and the leftmost k occurrences, and then find the mode on the subsegment of the array in between (using the algorithm described). Here is my code.

Not only does my code get WA, but if I change the value of $$$B$$$ I actually pass different amounts of test cases. With the value of $$$B = 3 \sqrt {N}$$$, I can pass the first 14. If I change this to $$$2 \sqrt{N}$$$, then I can only pass the first 7.

Is there some problem with the approach described in the StackOverflow post or is it because of some other error in my code? Your help is greatly appreciated!