Frequency of numbers in array

Write a program for the following scenario.

Input Array: {5,7,1,2,3,4,5,5,5,6,7}

Output

5 is repeated 4 times

7 is repeated 2 times

1 is repeated 1 time

2 is repeated 1 time

3 is repeated 1 time

4 is repeated 1 time

6 is repeated 1 time

Print output in sorted order of their frequencies, if frequencies are equal, sorts them using the number.

This problem can be easily solved by using HashMap, Traverse the array and find the counts of each number (Use number as key and frequency as value). Once you got HashMap with frequencies, use a comparator to sort numbers based on frequencies.

Step 1: Build map like key as integer and frequency as value. For above example, map can be constructed like following.

Key	Frequency
1	1
2	1
3	1
4	1
5	4
6	1
7	2

Following logic is used to construct above map.

private static Map<Integer, Integer> getFrequencyMap(int arr[]) {
 Map<Integer, Integer> countMap = new HashMap<>();

 /* Populate map as<key, frequency> */
 for (int i : arr) {
  Integer data = countMap.get(i);
  if (data == null)
   countMap.put(i, 1);
  else
   countMap.put(i, data + 1);
 }

 return countMap;
}

Step 2: Once you got map, construct a list, which contains map entries. Once we got list of objects, we can write a comparator to sort given elements base don frequency, if frequencies are equal, we can sort by using key.

Following code is used to construct a list from map entries.

private static List<Map.Entry<Integer, Integer>> getSortedListFromMap(
  Map<Integer, Integer> countMap) {
 Set<Map.Entry<Integer, Integer>> entrySet = countMap.entrySet();
 List<Map.Entry<Integer, Integer>> list = new LinkedList<>(entrySet);

 Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {

  @Override
  public int compare(Entry<Integer, Integer> obj1,
    Entry<Integer, Integer> obj2) {
   int val1 = obj1.getValue();
   int val2 = obj2.getValue();

   if (val1 - val2 == 0)
    return obj1.getKey() - obj2.getKey();

   return val2 - val1;
  }

 });

 return list;
}

Find complete working application below.

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;
import java.util.Set;

public class FrequencySort {

 private static Map<Integer, Integer> getFrequencyMap(int arr[]) {
  Map<Integer, Integer> countMap = new HashMap<>();

  /* Populate map as<key, frequency> */
  for (int i : arr) {
   Integer data = countMap.get(i);
   if (data == null)
    countMap.put(i, 1);
   else
    countMap.put(i, data + 1);
  }

  return countMap;
 }

 private static List<Map.Entry<Integer, Integer>> getSortedListFromMap(
   Map<Integer, Integer> countMap) {
  Set<Map.Entry<Integer, Integer>> entrySet = countMap.entrySet();
  List<Map.Entry<Integer, Integer>> list = new LinkedList<>(entrySet);

  Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {

   @Override
   public int compare(Entry<Integer, Integer> obj1,
     Entry<Integer, Integer> obj2) {
    int val1 = obj1.getValue();
    int val2 = obj2.getValue();

    if (val1 - val2 == 0)
     return obj1.getKey() - obj2.getKey();

    return val2 - val1;
   }

  });

  return list;
 }

 public static String[] getFrequencyInfo(int arr[]) {
  Objects.nonNull(arr);
  Map<Integer, Integer> countMap = getFrequencyMap(arr);
  List<Map.Entry<Integer, Integer>> list = getSortedListFromMap(countMap);

  String[] result = new String[list.size()];
  int i = 0;

  for (Map.Entry<Integer, Integer> entry : list) {
   result[i++] = entry.getKey() + " repeated " + entry.getValue()
     + " times";
  }

  return result;
 }
}

If you are using Java8, you can use streams like following.

public static String[] getFrequencyInfo(int arr[]) {
 Objects.nonNull(arr);
 Map<Integer, Integer> countMap = getFrequencyMap(arr);

 Comparator<Entry<Integer, Integer>> comparator = (entry1, entry2) -> {
  int val1 = entry1.getValue();
  int val2 = entry2.getValue();

  if (val1 - val2 == 0)
   return entry1.getKey() - entry2.getKey();

  return val2 - val1;
 };

 List<Map.Entry<Integer, Integer>> list = countMap.entrySet().stream()
   .sorted(comparator).collect(Collectors.toList());

 String[] result = new String[list.size()];
 int i = 0;

 for (Map.Entry<Integer, Integer> entry : list) {
  result[i++] = entry.getKey() + " repeated " + entry.getValue()
    + " times";
 }

 return result;

}

Following is the junit test case for above application.

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class FrequencySortTest {

 @Test
 public void test1() {
  int arr[] = { 1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 7 };

  String[] result = FrequencySort.getFrequencyInfo(arr);

  assertEquals(result[0], "5 repeated 4 times");
  assertEquals(result[1], "7 repeated 2 times");
  assertEquals(result[2], "1 repeated 1 times");
  assertEquals(result[3], "2 repeated 1 times");
  assertEquals(result[4], "3 repeated 1 times");
  assertEquals(result[5], "4 repeated 1 times");
  assertEquals(result[6], "6 repeated 1 times");
 }

 @Test(expected = NullPointerException.class)
 public void test2() {
  FrequencySort.getFrequencyInfo(null);
 }

 @Test
 public void test3() {
  int arr[] = { 5, 4, 3, 2, 1, 4, 3, 2, 5, 5 };

  String[] result = FrequencySort.getFrequencyInfo(arr);

  assertEquals(result[0], "5 repeated 3 times");
  assertEquals(result[1], "2 repeated 2 times");
  assertEquals(result[2], "3 repeated 2 times");
  assertEquals(result[3], "4 repeated 2 times");
  assertEquals(result[4], "1 repeated 1 times");
 }

}