How to Sort Array by Frequency in Java

The challenge

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

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:

import java.util.*;

public class Solution {
  public static int[] sortByFrequency(int[] array) {
    Map<Integer,Integer> freq = new HashMap<>();
    List<Integer> 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:

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<Integer,Long>)i).getValue())
                        .reversed()
                        .thenComparingLong(i -> ((Map.Entry<Integer,Long>)i).getKey()))
                .flatMapToInt(i -> Stream.generate(i::getKey)
                        .limit(i.getValue())
                        .mapToInt(Integer::intValue))
                .toArray();
    }
}

Option 3:

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<Integer, Long > fr = Arrays.stream(array).boxed().collect(Collectors.groupingBy(Function.identity(),Collectors.counting()));
        return Arrays.stream(array).boxed().sorted(new Comparator<Integer>() {
            @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

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}));
    }
}