So I was asked asked to write an O(n) function, `insertRanked(int[] list, int item)`

, to insert an element into an array sorted by frequency (I have written a boolean function to check if `int[] list`

is sorted by frequency). After inserting the element into the array, the array is then sorted again by frequency.

For example, `insertRanked([65, 65, 65, 65, 1, 1, 1, 8, 8, 987, 987, 2, 2, 40], 2)`

should produce `[65, 65, 65, 65, 1, 1, 1, 2, 2, 2, 8, 8, 987, 987, 40]`

.

Is this possible to do in O(n)? I have thought of storing the elements and their counts into a `LinkedHashMap`

and using `Collections.sort()`

but the time complexity of `Collections.sort()`

is O(n*log(n)).