Sample Problem: Frequencies in Array in Java

In computer science, it is quite common to encounter problems related to frequency counting of elements in an array. In Java, there are several ways to tackle such problems, with varying degrees of efficiency.

One such problem involves printing all elements of an array along with their frequencies. The array may contain duplicates, and the order of elements in output doesn't matter. Let's take a closer look at how we can solve this problem in Java.

Naive Solution: One simple solution is to run two loops. For every item, we count the number of times it occurs. To avoid duplicate printing, we keep track of processed items. However, this approach can be quite inefficient, with a time complexity of O(N^2) in the worst case.

To avoid counting and printing frequencies of duplicate elements, we can simply run a loop on the left of that element to check if it has occurred previously. The time complexity of this improved approach is still O(N^2) in the worst case.

Efficient Solution: A more efficient solution to this problem involves using a HashMap in Java. The idea is to store the element as the key and its frequency as the value as a key-value pair in HashMap. Here are the steps we can take:

1. Traverse through the array.
2. If the current element exists in the HashMap, increment its frequency in the HashMap.
3. Otherwise, insert this element as key with value 1 in the HashMap.
4. Finally, traverse the HashMap and print all elements with frequency.

This solution has a time complexity of θ(N), which is much better than the previous solutions. Additionally, the space complexity of this solution is θ(N), which is also better than the previous solutions.

Implementation:

Here is the Java implementation of the above approach:

java
import java.util.*;

class FrequencyCounter {
    
    static void printFrequencies(int arr[])
    {
        HashMap<Integer, Integer> freqMap = new HashMap<Integer, Integer>();
        
        for(int i=0; i<arr.length; i++)
        {
            freqMap.put(arr[i], freqMap.getOrDefault(arr[i], 0) + 1);
        }
        
        for(Map.Entry<Integer, Integer> entry : freqMap.entrySet())
        {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
    
    public static void main(String args[])
    {
        int arr[] = {10, 20, 20, 10, 10, 20, 5, 20};
        printFrequencies(arr);
    }
}

In the main method, we have created an array with duplicate elements and passed it to the printFrequencies method. This method takes an array as input and prints all elements along with their frequencies using HashMap.

Conclusion:

In conclusion, we have learned how to efficiently count the frequencies of elements in an array in Java using a HashMap. By using this approach, we can solve the problem in θ(N) time complexity and θ(N) space complexity. This solution can be quite useful in situations where we need to analyze data quickly and efficiently.