Sample Problem: Print Frequencies in an Order

Problem: Given an array of integers, the task is to print the frequencies of elements of the array in the order they appear in the array. That is, the element that appeared first, print the frequency of it before the element which appeared after it in the array.

Example: Input: arr[] = {10, 15, 20, 15, 10, 15} Output: 10 2 15 3 20 1

Input: arr[] = {10, 10, 20, 20, 20, 10, 10} Output: 10 4 20 2

Approach:

The problem can be solved using a HashMap or a LinkedHashMap. The HashMap approach is discussed below:

• Create a HashMap to store the frequencies of the elements.
• Traverse through the array.
• If the current element exists in the HashMap, increment its frequency in the HashMap.
• Otherwise, insert this element as key with value 1 in the HashMap.
• Traverse the input array again, and initialize its frequency as -1 in the HashMap after printing it.
• By doing this, we can ensure that we don't print the frequency of it again for its further occurrences.

Code:

// Java implementation of the above approach import java.util.*;

class GfG {

java
static void printFrequencies(int arr[]) {
    
    // Create a HashMap to store the frequencies of the elements.
    HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
    
    // Traverse through the array and update the frequency of each element in the HashMap.
    for(int i=0; i<arr.length; i++) {
        m.put(arr[i], m.getOrDefault(arr[i], 0) + 1);
    }
    
    // Traverse the array again and print the frequencies of the elements in the order they appear in the array.
    for(int i=0; i<arr.length; i++) {
        int freq = m.get(arr[i]);
        
        // If the frequency of the element is not -1, print the element and its frequency, and set its frequency to -1.
        if(freq != -1) {
            System.out.println(arr[i] + " " + freq);
            m.put(arr[i], -1);
        }
    }
}

public static void main(String args[]) {
    int arr[] = {10, 20, 20, 10, 10, 20, 5, 20};
    printFrequencies(arr);
}}

Step-by-step explanation of the code:

1. The code imports the required Java utility package:

java
import java.util.*;

2. The code defines a class named GfG which contains a static method named printFrequencies and a main method.

java
class GfG {
    static void printFrequencies(int arr[]) {
        // code for printing frequency of elements
    }

    public static void main(String args[]) {
        // code for calling printFrequencies
    }
}

3. The printFrequencies method takes an integer array arr as input.

java
static void printFrequencies(int arr[]) {

4. Inside the printFrequencies method, a new HashMap is created to store the frequencies of the elements.

java
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

5. The code traverses through the array using a for loop and updates the frequency of each element in the HashMap using the put() method.

java
for(int i=0; i<arr.length; i++) {
    m.put(arr[i], m.getOrDefault(arr[i], 0) + 1);
}

6. The getOrDefault() method returns the value to which the specified key is mapped or the default value if the key is not present in the HashMap.

7. The code then traverses the array again and prints the frequencies of the elements in the order they appear in the array.

java
for(int i=0; i<arr.length; i++) {
    int freq = m.get(arr[i]);
    
    // If the frequency of the element is not -1, print the element and its frequency, and set its frequency to -1.
    if(freq != -1) {
        System.out.println(arr[i] + " " + freq);
        m.put(arr[i], -1);
    }
}

8. The code checks whether the frequency of the element is not equal to -1, and if true, it prints the element and its frequency, and sets its frequency to -1.

9. Finally, the main method calls the printFrequencies method with an example array.

java
public static void main(String args[]) {
    int arr[] = {10, 20, 20, 10, 10, 20, 5, 20};
    printFrequencies(arr);
}

10. The output of the program will be:

10 3
20 4
5 1

which shows the frequencies of each element in the array.

After updating the frequency of each element in the HashMap, we need to iterate through the array again to print the frequencies in the order they appear in the array. We can achieve this by using a for loop to iterate through the array and check the frequency of each element in the HashMap.

If the frequency of the current element is not equal to -1, it means that we haven't printed the frequency of this element yet. So, we print the element and its frequency, and then update the frequency of this element in the HashMap to -1.

Here is the updated Java code to solve the given problem:

java
import java.util.*;

public class FrequencyOrder {
    
    public static void printFrequencies(int[] arr) {
        // Create a HashMap to store the frequencies of the elements
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        
        // Traverse through the array and update the frequency of each element in the HashMap
        for (int i = 0; i < arr.length; i++) {
            int key = arr[i];
            if (freqMap.containsKey(key)) {
                freqMap.put(key, freqMap.get(key) + 1);
            } else {
                freqMap.put(key, 1);
            }
        }
        
        // Iterate through the array again to print the frequencies in the order they appear in the array
        for (int i = 0; i < arr.length; i++) {
            int key = arr[i];
            int freq = freqMap.get(key);
            if (freq != -1) {
                System.out.println(key + " " + freq);
                freqMap.put(key, -1);
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr1 = {10, 15, 20, 15, 10, 15};
        int[] arr2 = {10, 10, 20, 20, 20, 10, 10};
        
        System.out.println("Frequencies of elements in arr1:");
        printFrequencies(arr1);
        
        System.out.println("\nFrequencies of elements in arr2:");
        printFrequencies(arr2);
    }
}

Output:

java
Frequencies of elements in arr1:
10 2
15 3
20 1

Frequencies of elements in arr2:
10 4
20 2

In this solution, the time complexity of iterating through the array twice is O(N), where N is the length of the input array. The space complexity is O(N) because we need to store the frequencies of all the elements in the HashMap.