Сортировка массива по модулю их значений с их частотами

Given an array arr containing N positive integers, sort them according to the increasing modulus of their values with their frequencies.

Пример:

Input: arr[]={1, 1, 5, 3, 2, 3, 3, 3, 4, 5, 4, 5}
Output: 2 4 4 1 1 5 5 5 3 3 3 3 
Explanation:
The elements are sorted in the following order:
2 % frequency(2) = 2 % 1 = 0
4 % frequency(4) = 4 % 2 = 0
1 % frequency(1) = 1 % 2 = 1
5 % frequency(5) = 5 % 3 = 2
3 % frequency(4) = 3 % 4 = 3

Input: arr[]={2, 9, 8, 2, 8, 9, 2, 8, 5}
Output: 5 9 9 2 2 2 8 8 8 

Подход: чтобы решить этот вопрос, сохраните частоты каждого числа на карте, а затем создайте собственный компаратор, который будет выполнять сортировку. Эта функция сравнения будет принимать два целочисленных значения, скажем, A и B в качестве параметров, и условие в этом компараторе для сортировки массива:

(A % frequency(A)) > (B % frequency(B))

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)