How to Sort Array by Frequency in Java

1 min read 381 words

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}));
    }
}
Tags:
Andrew
Andrew

Andrew is a visionary software engineer and DevOps expert with a proven track record of delivering cutting-edge solutions that drive innovation at Ataiva.com. As a leader on numerous high-profile projects, Andrew brings his exceptional technical expertise and collaborative leadership skills to the table, fostering a culture of agility and excellence within the team. With a passion for architecting scalable systems, automating workflows, and empowering teams, Andrew is a sought-after authority in the field of software development and DevOps.

Tags