Print maximum frequency number in an array(with slight modification)
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.