## The challenge

Sort elements in an array by decreasing frequency of elements. If two elements have the same frequency, sort them by increasing value.

 ``````1 2 3 4 `````` ``````Solution.sortByFrequency(new int[]{2, 3, 5, 3, 7, 9, 5, 3, 7}); // Returns {3, 3, 3, 5, 5, 7, 7, 2, 9} // We sort by highest frequency to lowest frequency. // If two elements have same frequency, we sort by increasing value. ``````

## The solution in Java code

Option 1:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `````` ``````import java.util.*; public class Solution { public static int[] sortByFrequency(int[] array) { Map freq = new HashMap<>(); List list = new ArrayList<>(); for (int a : array) { freq.put(a, freq.getOrDefault(a, 0) + 1); list.add(a); } Collections.sort(list, new Comparator() { public int compare(Object o1, Object o2) { Integer i1 = (Integer)o1, i2 = (Integer)o2; Integer f1 = freq.get(i1), f2 = freq.get(i2); int f = f2.compareTo(f1); return f == 0 ? i1.compareTo(i2) : f; }}); return list.stream().mapToInt(i -> i).toArray(); } } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````import java.util.*; import java.util.function.Function; import java.util.stream.Collectors; import java.util.stream.IntStream; import java.util.stream.Stream; public class Solution { public static int[] sortByFrequency(int[] array) { return IntStream.of(array) .boxed() .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) .entrySet() .stream() .sorted(Comparator.comparingLong(i -> ((Map.Entry)i).getValue()) .reversed() .thenComparingLong(i -> ((Map.Entry)i).getKey())) .flatMapToInt(i -> Stream.generate(i::getKey) .limit(i.getValue()) .mapToInt(Integer::intValue)) .toArray(); } } ``````

Option 3:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `````` ``````import java.util.*; import java.util.function.Function; import java.util.stream.Collectors; public class Solution { public static int[] sortByFrequency(int[] array) { System.out.println(Arrays.toString(array)); Map fr = Arrays.stream(array).boxed().collect(Collectors.groupingBy(Function.identity(),Collectors.counting())); return Arrays.stream(array).boxed().sorted(new Comparator() { @Override public int compare(Integer o1, Integer o2) { int c = Integer.compare((int)(long)fr.get(o2),(int)(long)fr.get(o1)); return c==0?Integer.compare(o1,o2):c; } }).mapToInt(x->x).toArray(); } } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````import org.junit.Test; import static org.junit.Assert.assertArrayEquals; import org.junit.runners.JUnit4; public class SolutionTest { @Test public void basicTests() { assertArrayEquals(new int[]{3, 3, 3, 5, 5, 7, 7, 2, 9}, Solution.sortByFrequency(new int[]{2, 3, 5, 3, 7, 9, 5, 3, 7})); assertArrayEquals(new int[]{1, 1, 1, 0, 0, 6, 6, 8, 8, 2, 3, 5, 9}, Solution.sortByFrequency(new int[]{1, 2, 3, 0, 5, 0, 1, 6, 8, 8, 6, 9, 1})); assertArrayEquals(new int[]{9, 9, 9, 9, 4, 4, 5, 5, 6, 6}, Solution.sortByFrequency(new int[]{5, 9, 6, 9, 6, 5, 9, 9, 4, 4})); assertArrayEquals(new int[]{1, 1, 2, 2, 3, 3, 4, 4, 5, 8}, Solution.sortByFrequency(new int[]{4, 4, 2, 5, 1, 1, 3, 3, 2, 8})); assertArrayEquals(new int[]{0, 0, 4, 4, 9, 9, 3, 5, 7, 8}, Solution.sortByFrequency(new int[]{4, 9, 5, 0, 7, 3, 8, 4, 9, 0})); } } ``````