Find Frequency of Each Element in a Limited Range Array in Java
Given an array arr[] of N positive integers which can contain integers from 1 to N where elements can be repeated or can be absent from the array. The task is to count the frequency of all elements.
Example 1
Input: arr[] = [1, 2, 1, 3, 2, 1, 4, 5, 5, 4]
Output:
Element 1 occurs 3 times
Element 2 occurs 2 times
Element 3 occurs 1 time
Element 4 occurs 2 times
Element 5 occurs 2 times
Example 2
Input: arr[] = [3, 1, 2, 3, 4, 1, 2, 3, 4, 5]
Output:
Element 1 occurs 2 times
Element 2 occurs 2 times
Element 3 occurs 3 times
Element 4 occurs 2 times
Element 5 occurs 1 time
Example 3
Input: arr[] = [1, 1, 1, 2, 3, 3, 5, 5, 8, 8, 8, 9, 9, 10]
Output:
Element 1 occurs 3 times
Element 2 occurs 1 times
Element 3 occurs 2 times
Element 5 occurs 2 times
Element 8 occurs 3 times
Element 9 occurs 2 times
Element 10 occurs 1 times
Approach 1: Using HashMap
The program counts the occurrences of each element in the array and then prints out the frequency of each unique element. It traverse the input array and for each distinct element of the array, store its frequency in a HashMap.
Algorithm
Step 1: Initialize a HashMap to store the frequency of each element.
Step 2: Iterate through the array.
Step 3: For each element in the array:
Step 4: If the element is already present in the HashMap, increment its frequency by 1.
Step 5: If the element is not present, add it to the HashMap with a frequency of 1.
Step 6: Iterate through the HashMap and print out the frequency of each element.
Filename: ElementFrequencyUsingHashMap.java
import java.util.HashMap;
public class ElementFrequencyUsingHashMap {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
findFrequency(array);
}
public static void findFrequency(int[] array) {
HashMap<Integer, Integer> frequencyMap = new HashMap<>();
// Counting frequency of each element
for (int num : array) {
if (frequencyMap.containsKey(num)) {
frequencyMap.put(num, frequencyMap.get(num) + 1);
} else {
frequencyMap.put(num, 1);
}
}
// Printing frequency of each element
for (int key : frequencyMap.keySet()) {
System.out.println("Element " + key + " occurs " + frequencyMap.get(key) + " times");
}
}
}
Output
Element 1 occurs 3 times
Element 2 occurs 3 times
Element 3 occurs 3 times
Element 4 occurs 3 times
Element 5 occurs 3 times
Time Complexity: The time complexity of this approach is O(n), where n is the number of elements in the array. This is because we iterate through the array once to count the frequency of each element.
Space Complexity: The space complexity of this approach is also O(n), where n is the number of unique elements in the array. This is because we use a HashMap to store the frequency of each element, and the size of the HashMap depends on the number of unique elements in the array.
Approach 2: Using Linear Search
The program demonstrates how to find the frequency of each element in a given array using linear search. The program iterates through the array, and for each element, it scans the array again to count the number of occurrences. It marks each visited element to avoid recounting.
Algorithm
Step 1: Iterate through each element of the array.
Step 2: Initialize a counter variable count to 1.
Step 3: If the current element has not been marked as visited (by setting it to -1), enter a nested loop to search for its occurrences.
Step 4: Within the nested loop, iterate through the array starting from the next index (i + 1).
Step 5: If any element matches the current element, increment the count variable and mark the matching element as visited by setting it to -1.
Step 6: After scanning through the array, print out the element along with its frequency (count).
Filename: ElementFrequencyUsingLinearSeach.java
import java.util.*;
public class ElementFrequencyUsingLinearSeach {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
findFrequency(array);
}
public static void findFrequency(int[] array) {
for (int i = 0; i < array.length; i++) {
int count = 1;
if (array[i] != -1) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] == array[j]) {
count++;
array[j] = -1; // Mark as visited
}
}
System.out.println("Element " + array[i] + " occurs " + count + " times");
}
}
}
}
Output
Element 1 occurs 3 times
Element 2 occurs 3 times
Element 3 occurs 3 times
Element 4 occurs 3 times
Element 5 occurs 3 times
Time Complexity: The time complexity of this approach is O(n^2), where n is the number of elements in the array. This is because for each element in the array, we scan through the remaining array to count its occurrences.
Space Complexity: The space complexity of this approach is O(1), as it doesn't require any additional space proportional to the input size. It modifies the input array in-place to mark visited elements, which doesn't increase the overall space complexity.
Approach 3: Using Binary Search
The program demonstrates how to find the frequency of each element in a given array using binary search. It first sorts the array to ensure that all occurrences of each element are contiguous. Then, it iterates through the sorted array and uses binary search to find the first and last occurrence of each element. By subtracting the indices of the first and last occurrence of an element and adding 1, it calculates the frequency of that element.
Algorithm
Step 1: Sort the input array to ensure that all occurrences of each element are contiguous.
Step 2: Iterate through the sorted array.
Step 3: Use binary search to find the first occurrence of the element.
Step 4: Use binary search to find the last occurrence of the element.
Step 5: Calculate the frequency of the element by subtracting the indices of the first and last occurrence and adding 1.
Step 6: Print the element along with its frequency.
Step 7: Skip elements for which frequency has already been counted by updating the loop variable to the index of the last occurrence.
Filename: ElementFrequencyUsingBinarySearch.java
import java.util.Arrays;
public class ElementFrequencyUsingBinarySearch {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5}; // Example array
Arrays.sort(arr); // Sort the array
// Finding frequency of each element
int n = arr.length;
for (int i = 0; i < n; i++) {
int firstOccurrence = findFirstOccurrence(arr, arr[i]);
int lastOccurrence = findLastOccurrence(arr, arr[i]);
int frequency = lastOccurrence - firstOccurrence + 1;
System.out.println(arr[i] + " occurs " + frequency + " times");
// Skip elements for which frequency has already been counted
i = lastOccurrence;
}
}
// Binary search to find the first occurrence of x in the array
private static int findFirstOccurrence(int[] arr, int x) {
int low = 0;
int high = arr.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
result = mid;
high = mid - 1; // Continue searching on the left side for the first occurrence
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
// Binary search to find the last occurrence of x in the array
private static int findLastOccurrence(int[] arr, int x) {
int low = 0;
int high = arr.length - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
result = mid;
low = mid + 1; // Continue searching on the right side for the last occurrence
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
}
Output
1 occurs 3 times
2 occurs 3 times
3 occurs 3 times
4 occurs 3 times
5 occurs 3 times
Time Complexity: The time complexity of this approach is O(n log n), where n is the number of elements in the array. This is because sorting the array takes O(n log n) time and finding the first and last occurrence of each element takes O(log n) time. So, the complexity is O(n log n).
Space Complexity: The space complexity is O(1) because the program uses only a constant amount of extra space regardless of the input size.
Approach 4: Using Counting Sort
The program demonstrates how to find the frequency of each element in a given array using counting sort. Counting sort is a non-comparison based sorting algorithm that works well when the range of elements in the array is limited. In this program, we first determine the maximum element in the array to determine the size of the frequency array. Then, we iterate through the input array to count the frequency of each element using counting sort.
Algorithm
Step 1: Find the maximum element in the input array to determine the size of the frequency array.
Step 2: Create a frequency array of size maxElement + 1.
Step 3: Iterate through the input array and count the frequency of each element by incrementing the corresponding index in the frequency array.
Step 4: Iterate through the frequency array and print the frequency of each element that has a count greater than 0.
Filename: ElementFrequencyUsingCountingSort.java
import java.util.Arrays;
public class ElementFrequencyUsingCountingSort {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
findFrequency(array);
}
public static void findFrequency(int[] array) {
int maxElement = Arrays.stream(array).max().getAsInt();
int[] frequency = new int[maxElement + 1];
// Counting frequency using Counting Sort
for (int num : array) {
frequency[num]++;
}
// Printing frequency of each element
for (int i = 0; i < frequency.length; i++) {
if (frequency[i] > 0) {
System.out.println("Element " + i + " occurs " + frequency[i] + " times");
}
}
}
}
Output
Element 1 occurs 3 times
Element 2 occurs 3 times
Element 3 occurs 3 times
Element 4 occurs 3 times
Element 5 occurs 3 times
Time Complexity: The time complexity of this approach is O(n), where n is the length of the input array. This is because the function iterates over the entire array once to calculate the frequency of each element.
Space Complexity: The space complexity is O(maxElement) because we use an extra array of size maxElement + 1 to store the frequency counts.
Approach 5: Using Java Streams
The program demonstrates how to find the frequency of each element in a given array using Java 8 Streams. It utilizes Java 8's Stream API along with collectors to efficiently collect the frequencies of elements in the array. By using streams and collectors, the code becomes concise and readable.
Algorithm
Step 1: Convert the primitive integer array to a stream using Arrays.stream(array).
Step 2: Box each integer in the stream to convert them into their corresponding wrapper objects using .boxed().
Step 3: Use the Collectors.groupingBy() collector along with Collectors.counting() downstream collector to group elements by their identity and count their occurrences.
Step 4: Collect the frequencies into a Map where the keys represent elements and values represent their frequencies.
Step 5: Iterate through the frequency map and print the frequency of each element.
Filename: ElementFrequencyUsing8Streams.java
import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public class ElementFrequencyUsing8Streams {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
findFrequency(array);
}
public static void findFrequency(int[] array) {
// Using Java Streams to collect frequencies
Map frequencyMap = Arrays.stream(array)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
// Printing frequency of each element
frequencyMap.forEach((element, frequency) ->
System.out.println("Element " + element + " occurs " + frequency + " times"));
}
}
Output
Element 1 occurs 3 times
Element 2 occurs 3 times
Element 3 occurs 3 times
Element 4 occurs 3 times
Element 5 occurs 3 times
Time Complexity: The time complexity of this approach is O(n), where n is the length of the input array. This is because grouping elements and counting their occurrences using streams takes O(n) time.
Space Complexity: The space complexity is O(n) due to the creation of the frequency map to store the counts of elements.