Count The Frequency Of Each Element Of An Array In Java

Analyzing data often involves understanding its composition. Counting the frequency of elements in an array is a fundamental operation in programming that provides insights into data distribution. In this article, you will learn various robust methods to efficiently count the frequency of each element within a Java array.

Problem Statement

Given an array of integers (or any comparable type), the task is to determine how many times each unique element appears in that array. For instance, in an array like [1, 2, 2, 3, 1], the desired output would be 1: 2, 2: 2, 3: 1. This problem is crucial for tasks like data analysis, optimizing algorithms, or preparing data for further processing, especially when dealing with large datasets where performance matters.

Example

Consider the following array: [10, 20, 20, 10, 10, 30, 40, 50, 20, 40] The expected frequency count would be:

• 10: 3 times
• 20: 3 times
• 30: 1 time
• 40: 2 times
• 50: 1 time

Background & Knowledge Prerequisites

To effectively understand the solutions presented, readers should have a basic understanding of:

• Java array fundamentals
• Basic loop constructs (for loops, while loops, enhanced for loops)
• Conditional statements (if-else)
• Understanding of the java.util.HashMap class (for one approach)
• Methods from the java.util.Arrays class, particularly sort() (for one approach)

Use Cases or Case Studies

Counting element frequencies is a versatile operation applicable in various scenarios:

• Data Analysis: Understanding the distribution of values in survey results, sensor readings, or financial transactions.
• Web Analytics: Counting unique visitor IP addresses or frequently visited pages on a website to identify popular content or potential attacks.
• Inventory Management: Tracking stock levels of different product IDs in a warehouse to identify fast-moving or slow-moving items.
• Text Processing: Determining the frequency of words in a document for natural language processing (NLP) tasks like sentiment analysis or keyword extraction.
• Performance Optimization: Identifying hot spots (frequently occurring values or events) in system logs to optimize resource allocation or debug common issues.

Solution Approaches

This section presents three distinct methods to count element frequencies, ranging from a basic approach to more optimized solutions.

1. Using Nested Loops (Brute-Force with Visited Array)

This method uses two nested loops to iterate through the array. An outer loop picks an element, and an inner loop counts its occurrences. A separate visited array ensures each element is counted only once.

// Array Element Frequency using Nested Loops
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Initialize the array
        int[] arr = {10, 20, 20, 10, 10, 30, 40, 50, 20, 40};
        int n = arr.length;

        // Step 2: Create a boolean array to keep track of visited elements
        // This helps avoid recounting elements that have already been processed.
        boolean[] visited = new boolean[n];

        // Step 3: Iterate through the array
        for (int i = 0; i < n; i++) {
            // Step 3a: Skip if the element at index 'i' has already been visited
            if (visited[i]) {
                continue;
            }

            // Step 3b: Initialize count for the current element
            int count = 1;

            // Step 3c: Iterate through the rest of the array (elements after 'i')
            // to find duplicates of arr[i]
            for (int j = i + 1; j < n; j++) {
                if (arr[i] == arr[j]) {
                    count++;
                    visited[j] = true; // Mark duplicate as visited to avoid recounting
                }
            }

            // Step 3d: Print the frequency of the current unique element
            System.out.println(arr[i] + ": " + count + " times");
        }
    }
}

Run

Sample Output:

10: 3 times
20: 3 times
30: 1 times
40: 2 times
50: 1 times

Stepwise Explanation:

1. An integer array arr is initialized, along with a boolean array visited of the same size, initially all false.
2. The outer for loop iterates from the first to the last element of arr.
3. Inside the outer loop, if the current element (arr[i]) has already been visited (marked true in visited[i]), it's skipped.
4. If not visited, a count is initialized to 1 for arr[i].
5. An inner for loop then iterates through the remaining elements (arr[j] where j > i).
6. If arr[i] matches arr[j], the count is incremented, and visited[j] is set to true to indicate that this duplicate has been counted.
7. After the inner loop completes, the frequency of arr[i] (the initial unique element) is printed. This approach is straightforward but less efficient for large arrays due to its O(N^2) time complexity.

2. Using HashMap

This is the most efficient and common Java approach. It leverages a HashMap to store each unique element as a key and its frequency as the corresponding value.

// Array Element Frequency using HashMap
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Initialize the array
        int[] arr = {10, 20, 20, 10, 10, 30, 40, 50, 20, 40};

        // Step 2: Create a HashMap to store element frequencies
        // The key will be the array element, and the value will be its count.
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        // Step 3: Iterate through the array and update frequencies in the map
        for (int element : arr) {
            // Using getOrDefault to simplify logic:
            // If element exists as a key, get its current count and increment.
            // If element does not exist, default count to 0 and then increment to 1.
            frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1);
        }

        // Step 4: Print the frequencies from the HashMap
        System.out.println("Element Frequencies:");
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue() + " times");
        }
    }
}

Run

Sample Output:

Element Frequencies:
50: 1 times
40: 2 times
10: 3 times
20: 3 times
30: 1 times

Stepwise Explanation:

1. An integer array arr is initialized.
2. An empty HashMap called frequencyMap is created. This map will store Integer elements as keys and their Integer counts as values.
3. The code iterates through each element in the arr using an enhanced for loop.
4. For each element, frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1) is called:

• getOrDefault(element, 0) retrieves the current count for element. If element is not yet in the map, it returns 0.
• This count is then incremented by 1.
• put(element, ...) inserts or updates the element's count in the map.

1. Finally, the code iterates through the entrySet() of the frequencyMap to print each unique element and its corresponding frequency. This approach offers an average time complexity of O(N), making it highly efficient for most scenarios.

3. Using Arrays.sort() and a Single Pass

This method first sorts the array, bringing identical elements together. Then, a single pass through the sorted array can count consecutive occurrences of each element.

// Array Element Frequency using Arrays.sort()
import java.util.Arrays;
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        // Step 1: Initialize the array
        int[] arr = {10, 20, 20, 10, 10, 30, 40, 50, 20, 40};

        // Step 2: Sort the array
        Arrays.sort(arr);
        // After sorting, arr becomes: [10, 10, 10, 20, 20, 20, 30, 40, 40, 50]

        // Step 3: Iterate through the sorted array to count frequencies
        System.out.println("Element Frequencies:");
        for (int i = 0; i < arr.length; i++) {
            // Step 3a: Initialize count for the current element
            int count = 1;

            // Step 3b: Count consecutive occurrences of the current element
            // while (i + 1 < arr.length) checks if there's a next element
            // arr[i] == arr[i + 1] checks if the next element is the same
            while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
                count++;
                i++; // Move to the next identical element
            }

            // Step 3c: Print the frequency of the unique element (arr[i] after counting)
            System.out.println(arr[i] + ": " + count + " times");
        }
    }
}

Run

Sample Output:

Element Frequencies:
10: 3 times
20: 3 times
30: 1 times
40: 2 times
50: 1 times

Stepwise Explanation:

1. An integer array arr is initialized.
2. Arrays.sort(arr) is called to sort the array in ascending order. This rearranges the array so that identical elements are adjacent to each other.
3. A for loop iterates through the sorted array.
4. Inside the loop, count is initialized to 1 for the current element arr[i].
5. A while loop then checks if there are consecutive identical elements (arr[i] == arr[i + 1]). If a match is found, count is incremented, and i is also incremented to move past the counted duplicate.
6. Once the while loop finishes (meaning arr[i] is no longer equal to arr[i + 1], or it's the last element), the frequency of arr[i] is printed. The for loop then continues from the next unique element. This approach offers an overall time complexity dominated by the sort, O(N log N).

Conclusion

Counting element frequencies in an array is a common programming challenge with multiple solutions, each offering distinct trade-offs in terms of complexity and performance. While the nested loop approach is intuitive for understanding the basic logic, it is less efficient for larger datasets. For optimal performance in Java, the HashMap approach is generally preferred due to its average O(N) time complexity. Sorting the array and then making a single pass offers a good alternative with O(N log N) complexity, especially when direct map usage might be restricted or if the data needs to be sorted for other purposes.

Summary

• Nested Loops: Simple to understand, uses O(N^2) time complexity. Best suited for very small arrays or as a pedagogical example due to its straightforward logic.
• HashMap: Most efficient for general use, offering average O(N) time complexity. It stores unique elements as keys and their counts as values, providing quick lookups and updates.
• Arrays.sort() and Single Pass: Efficient for primitive arrays, providing O(N log N) time complexity (dominated by the sorting step). It's a good alternative when sorting the array is acceptable or beneficial for other operations.
• The choice of method should align with array size, performance requirements, and available data structures.