Exercise In intersection of two arrays problem, we have given two arrays, we need to print their intersection(common elements).

public class IntersectionOfTwoArrays {
    private static void printIntersection(int[] arr1, int[] arr2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        // Build the frequency map for arr1
        for (int i = 0; i < arr1.length; i  ) {
            if (map.containsKey(arr1[i])) {
                map.put(arr1[i], map.get(arr1[i])   1);
            } else {
                map.put(arr1[i], 1);
            }
        }
        // Traverse the elements of arr2 one by one
        for (int i = 0; i < arr2.length; i  ) {
            // If the map contains current element
            if (map.containsKey(arr2[i])) {
                // Reduce the frequency by 1
                int freq = map.get(arr2[i]);
                freq--;
                // If freq becomes 0, remove the element from the map
                if (freq == 0) {
                    map.remove(arr2[i]);
                } else {
                    map.put(arr2[i], freq);
                }
                // Print the element
                System.out.print(arr2[i]   " ");
            }
        }
        System.out.println();
    }

I have found this implementation which looks for me really nice. Unfortunately I do not understand deleting quantity in frequency in second part.

If map contains key from first array it should have frequency one, then if happens again it shoould go 1, why we remove element which exist in first map?

        for (int i = 0; i < arr2.length; i  ) {
            // If the map contains current element
            if (map.containsKey(arr2[i])) {
               // Reduce the frequency by 1
                int freq = map.get(arr2[i]);
                freq--;
                // If freq becomes 0, remove the element from the map
                if (freq == 0) {
                    map.remove(arr2[i]);
                } else {
                    map.put(arr2[i], freq);
                }

CodePudding user response：

The first loop counts the frequency of the elements of arr1 in a Map<Integer, Integer>. The second loop considers arr2, where we want to find the same elements.

The important part is that we don't want to include an element of arr2 more often than we found it in arr1. For example value 2 is included in arr1 three times and in arr2 four times. The intersection should only be three 2. In order to solve this problem, we decrease the frequency in the second loop.

Example for arr1={2,2,2] and arr2=[2,2,2,2] to make it clear. number before -> is the key of the map and number after -> is the frequency. In the first loop the frequency simply increases to three in three iterations.

Loop 1:

element 0: 2 -> 1
element 1: 2 -> 2
element 2: 2 -> 3

Loop2:

element 0: 2 -> 3-1; print("2")
element 1: 2 -> 2-1; print("2")
element 2: 2 -> 1-1; print("2")
element 3: 2 -> 0; 

As you can see the loop prints three times the value 2, which is the correct intersection. The last two is not printed as we know that in arr1 only three 2 are included.

CodePudding user response：

Removal from the frequency map is needed to keep the matching value V_i by the minimal frequency min(F1_i, F2_i) in both arrays.

Let's assume, array1 is [0, 1, 0] and array2 is [1, 0, 1].

Then the frequency map after iterating the first array looks like {0=2, 1=1}, and after counting the first 1 in array2, the frequency is decreased to 0, the key 1 is removed from the map, and therefore map.containsKey(1) is false and the subsequent occurrences of 1 in array2 are excluded from the intersection.

Actually removal from the map may be skipped, if the remaining frequency is just compared to 0 as shown below.

Also, regarding the implementation: using method Map::merge may help to make the method more concise:

private static void printIntersection(int[] arr1, int[] arr2) {
    HashMap<Integer, Integer> map = new HashMap<>();
    // Build the frequency map for arr1
    for (int i = 0; i < arr1.length; i  ) {
        map.merge(arr1[i], 1, Integer::sum); // adding occurrence in arr1
    }

    // Traverse the elements of arr2 one by one
    for (int i = 0; i < arr2.length; i  ) {
        // subtracting occurrence in arr2
        if (map.merge(arr2[i], -1, Integer::sum) >= 0) {
            System.out.print(arr2[i]   " ");
        }
    }
    System.out.println();
}