# Insert an element into an array sorted according to frequency, then sort the array by frequency again

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)).

Here's one approach to start you off could be based on count.

``````import java.util.ArrayList;
import java.util.HashMap;
import java.util.TreeMap;

public class SortCount {
public static void main(String[] args) {
int nums[] = {([65, 65, 65, 65, 1, 1, 1, 8, 8, 987, 987, 2, 2, 40};
HashMap<Integer,Integer> counts = new HashMap<Integer,Integer>();

for(int i = 0; i < nums.length; i++) {
if(counts.containsKey(nums[
Integer c = counts.get(nums[i]) + 1;
counts.put(nums[i], c);
}
else {
counts.put(nums[i],1);
}
}

ValueComparator<Integer,Integer> bvc = new ValueComparator<Integer,Integer>(counts);
TreeMap<Integer,Integer> sortedMap = new TreeMap<Integer,Integer>(bvc);
sortedMap.putAll(counts);

ArrayList<Integer> output = new ArrayList<Integer>();
for(Integer i : sortedMap.keySet()) {
for(int c = 0; c < sortedMap.get(i); c++) {
}
}

System.out.println(output.toString());
}
}

//Which uses a Comparator class to compare the values in a Map:

import java.util.Comparator;
import java.util.Map;

public class ValueComparator<T1,T2 extends Comparable<T2>> implements Comparator<T1> {
Map<T1,T2> base;
public ValueComparator(Map<T1,T2> base) {
this.base = base;
}

@Override
public int compare(T1 k1, T1 k2) {
T2 val1 = base.get(k1);
T2 val2 = base.get(k2);

return val1.compareTo(val2);
}
}
``````