Find Frequency of each element in an unsorted array in Java

In this tutorial, we will learn to find how many times every element occurs in an array is required for solving many problems in competitive programming. If the array is not sorted it can take O(n2) time using a trivial approach. But hashing can reduce the time to O(n). This article explains how the frequency of every element in an unsorted array can be found in Java.

Finding frequency using Hashing

Approach

For every element e in an unsorted array,

  1. If the element e is not present in the hashmap, store it and set its value to 1.
  2. If the element e is already present in the hashmap, just increment its value.

After traversing the unsorted array just once, the frequencies of all the elements will be stored in the hashmap. Since hashing takes constant time, the frequencies can be found in linear time O(n), where n is the size of an unsorted array.

Here is the Java implementation of the above approach. Java’s provides HashMap which stores the elements in (key, value) pairs. It can be used to find the frequency of every element in an unsorted array. The elements can be used as the keys and the frequency of the elements can be used as values.

import java.util.HashMap;
import java.util.Random;

class freqElement {
    public static void main(String[] args) {
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
        Random random = new Random();
        Integer count = 0;
        Integer[] numbers = new Integer[20];
        for (int i=0; i<numbers.length; i++)
            numbers[i] = random.nextInt(20);
        for (int i=0; i<numbers.length; i++) {
            count = hashmap.getOrDefault(numbers[i], 0);
            hashmap.put(numbers[i], count+1);
        }
        for (int i=0; i<numbers.length; i++)
            System.out.print(numbers[i]+"\t");
        System.out.println("Frequencies:");
        for (Integer i: hashmap.keySet())
            System.out.println(i+": "+hashmap.get(i));
    }
}

The program above generates some random numbers between 0 to 20 and stores them in the array numbers. Since the HashMap class supports only object types, instead of the primitive type int, its equivalent wrapper class Integer is used. The getOrDefault method returns the value corresponding to the key if the key is present, the default value otherwise. The default value here is 0. So if the element is new to the hashmap, its frequency is set to 1 and if the element already exists, its frequency is incremented, using put method. Finally iterating through the hashmap will give the frequency of every element in the unsorted array.

It will produce an output that resembles the one below. Since the numbers are generated randomly, the output may vary every time.

14      6       12      14      3       18      2        2       16      6       17      16      12        2       9       12      16      12      11        13
Frequencies:
16: 3
17: 1
18: 1
2: 3
3: 1
6: 2
9: 1
11: 1
12: 4
13: 1
14: 2

Leave a Reply

Your email address will not be published. Required fields are marked *