package org.wesome.dsalgo;
import java.util.Map;
import java.util.TreeMap;
public class SortArrayWithDuplicate {
public static int[] sortArrayWithDuplicate(int[] arr) {
Map<Integer, Integer> freqMap = new TreeMap<>();
/* Store the integer as key and its frequency as value in Tree Map */
for (int key : arr) {
freqMap.put(key, freqMap.getOrDefault(key, 0) + 1);
}
/* Tree Map sorts the key into natural order. */
int i = 0;
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
int value = entry.getValue();
while (value > 0) {
/* override the input array with key upto frequency times */
arr[i] = entry.getKey();
i++;
value--;
}
}
return arr;
}
}