# Print maximum frequency number in an array(with slight modification)

There is an integer array and 2 variables Q and M.The output required is the number which has the maximum frequency in the array, but the catch is that each number in the array can be increased/decreased by M and that too Q number of times.

In case of multiple answers print the first one.

eg:

array:1,2,3,4 and Q=1,M=1

Answer:3 ,as the array can be transformed into 2,2,2,4 (here 2 appears 3 times in this array, adding 1 in 1 and subtracting 1 from 3.)

A hashtable can be used here,but can't understand how to handle the addition and subtraction of each number of the array.

Can anyone please suggest an approach for that part?

Thanks.

Start by sorting the array. Now go over the array using four pointers, left, center left, center right, and right. The two central pointers bracket all the occurrences of some value $x$. The left pointer points at the leftmost value which is at least $x-M$, and the right pointer points at the rightmost value which is at most $x+M$. Using the positions of these pointers you can calculate the maximum frequency of $x$.
Traversing the array should take linear time, so the entire algorithm takes time $O(n\log n)$.
For a possibly simpler solution, you can sort the array and then use a single pointer to traverse it. Treat this pointer as one of the central pointers from the previous algorithm, and find the locations of all other pointers in logarithmic time using binary search. Traversal now takes time $O(n\log n)$, but this doesn't increase the asymptotic running time of the algorithm.