Intersection of Two arrays with Duplicate Elements

JavaView on GFG

Intuition

Find intersection counting multiplicities. Sort both, two-pointer or frequency maps.

Algorithm

1Sort both. Two pointers: advance smaller, collect equal elements.

Common Pitfalls

•Same as LC 350. Each element in result appears as many times as it appears in both arrays.

Intersection of Two arrays with Duplicate Elements.java

Java

// Approach: Sort both arrays or use frequency maps; collect common elements.
// Time: O(n log n + m log m) Space: O(min(n,m))
class Solution {
    public ArrayList<Integer> intersectionWithDuplicates(int[] a, int[] b) {
        ArrayList<Integer> li = new ArrayList<>();
        int n = a.length;
        int m = b.length;
        HashSet<Integer> hs1 = new HashSet<>();
        HashSet<Integer> hs2 = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int temp = a[i];
            hs1.add(temp);
        }

        for (int i = 0; i < m; i++) {
            int temp = b[i];
            hs2.add(temp);
        }

        for (int key : hs1) {
            if (hs2.contains(key))
                li.add(key);
        }

        return li;
    }
}

Was this solution helpful?