In this post we'll see how to write Java program to find the frequency of elements in an array.
For example-
Input: int[] nums = {1,2,2,3,1,4};
Output-
1 2
2 2
3 1
4 1
Java program for counting the occurrences of each element in an array can be written using the following approaches.
- Using nested loops
- Using a frequency array
- Using HashMap
- Using Java Stream API
Java program to find the frequency of elements in an array using nested loops
With this approach you will have an outer loop, traversing the array one element at a time and an inner loop, starting from the next element (j=i+1) and traversing through the whole array to check if the element currently pointed by the outer loop is found again, if yes then increment the occurrence count for that element.
An extra boolean array is needed to mark the elements that are already visited so that the same element is not counted again.
public class FrequencyArray {
public static void main(String[] args) {
int[] nums = {1,2,2,3,1,4};
countOccurrencesNL(nums);
}
public static void countOccurrencesNL(int[] nums) {
int len = nums.length;
boolean[] visited = new boolean[len];
for(int i = 0; i < len; i++) {
if(visited[i]) {
continue;
}
int count = 1;
int n = nums[i];
for(int j = i + 1; j < len; j++) {
if(n == nums[j]) {
// mark as visited so that it is not picked again
visited[j] = true;
count++;
}
}
System.out.println(n + " " +count);
}
}
}
Output
1 2 2 2 3 1 4 1
Time and space complexity of this approach
Since there are nested loops with each traversing the whole array of size n therefore the time complexity of this approach is O(n2).
One Boolean array of the same size as the array is also needed so the time complexity is O(n).
Java program to find the frequency of elements in an array using frequency array
In order to count the occurrences of element in an array you can create another frequency array. For that the logic is as given below-
- Find the maximum element in the given array and create another frequencyArray with a size equal to maxElement + 1.
- The index of frequencyArray represents the element of the given array, and the value at that index stores its frequency. For that iterate through the given array and increment the count at the corresponding index in the frequecyArray.
This logic is suitable for an array with positive values and having values with in a limited range.
public class FrequencyArray {
public static void main(String[] args) {
int[] nums = {1,2,2,3,1,4};
int[] freqArray = countOccurrences(nums);
// iterate the frequency array
for(int i = 0; i < freqArray.length; i++) {
if(freqArray[i] != 0)
System.out.println(i + " " + freqArray[i]);
}
public static int[] countOccurrences(int[] nums) {
int max = Integer.MIN_VALUE;
// Find the max element in the array
for(int n : nums) {
max = Math.max(max, n);
}
// Create frequency array
int[] freqArray = new int[max + 1];
for (int n : nums) {
freqArray[n]++;
}
return freqArray;
}
}
Output
1 2 2 2 3 1 4 1
Time and space complexity of this approach
If the max element in the given array is k then in order to display the count for each element, we need three separate iterations as per the logic which means O(n) + O(n) + O(k).
Which can be taken as O(n) if the range is limited.
A frequency array of size k is needed so the space complexity is O(k).
Java program to find the frequency of elements in an array using HashMap
Another way to write a Java program to count the occurrences of each element in an array is to use a HashMap. Logic for this approach is as given below-
- Iterate over the array and store array element as key and its frequency as value in the HashMap.
- Check if key (array element) already exists in the Map, if yes then increment the value by 1. If not present then add the element as key and value as 1.
import java.util.HashMap;
import java.util.Map;
public class FrequencyArray {
public static void main(String[] args) {
int[] nums = {1,2,2,3,1,4};
countOccurrencesMap(nums);
}
public static void countOccurrencesMap(int[] nums) {
Map<Integer, Integer> freqMap = new HashMap<>();
for(int n : nums) {
freqMap.put(n, freqMap.getOrDefault(n, 0)+1);
}
for(Map.Entry<Integer,Integer> entry : freqMap.entrySet()){
System.out.println(entry.getKey() + " " + entry.getValue());
}
}
}
Output
1 2 2 2 3 1 4 1
Time and space complexity of this approach
There is one iteration of the array to store elements in the HashMap. For each element, the getOrDefault() and put() operations on a HashMap have an average time complexity of O(1). Therefore, the total time complexity of this logic is O(n).
Since HashMap stores only unique elements, so the space complexity is O(k), considering the number of unique elements is k.
Java program to find the frequency of elements in an array using Java Stream API
The Collectors.groupingBy() method in Java Stream API can be used to group element with their repective count. For counting another method Collectors.counting() is used.
boxed() method in Java Stream API is also required to convert primitive int to Integer for stream operations.
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public class FrequencyArray {
public static void main(String[] args) {
int[] nums = {1,2,2,3,1,4};
countOccurrencesStream(nums);
}
public static void countOccurrencesStream(int[] nums) {
//Map<Integer, Integer> freqMap = new HashMap<>();
Map<Integer, Long> freqMap = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
for(Map.Entry<Integer,Long> entry : freqMap.entrySet()){
System.out.println(entry.getKey() + " " + entry.getValue());
}
}
}
Output
1 2 2 2 3 1 4 1
Time and space complexity of this approach
Arrays.stream() traverses the whole array which is O(n), in the same pass boxed() converts int to Integer and grouping is done by incrementing the count in the HashMap or by adding a new element, put() and get() methods in HahsMap are considered O(1). Thus the time complexity of this approach is O(1).
Since HashMap stores only unique elements, so the space complexity is O(k), considering the number of unique elements is k. Worst case is O(n) if all the array elements are unique.
That's all for this topic Java Program to Find The Frequency of Array Elements. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
