Finding the Intersection of Two Arrays (With Repeats)

Finding the Intersection of Two Arrays

Imagine you have two shopping lists. You want to find only the items that appear on *both* lists. That shared part is called the intersection. In programming, an array is just an ordered list of values, and the intersection of two arrays is a new array containing only the values found in both.

There is one important twist in this problem: a value can appear as many times as it shows up in both arrays. So if a number appears twice in one array and three times in the other, it should appear twice in the answer — we take the smaller of the two counts.

The Goal

You are given two integer arrays, arr1 and arr2. You must write a function that returns a new array holding their intersection. The order of the result does not matter — any order is accepted.

Walking Through the Examples

Example 1

arr1 = [1, 2, 2, 1]
arr2 = [2, 2]
Output: [2, 2]

The number 2 shows up twice in arr1 and twice in arr2. The smaller count is 2, so 2 appears twice in the answer. The number 1 is in arr1 but not in arr2, so it is left out.

Example 2

arr1 = [4, 9, 5]
arr2 = [9, 4, 9, 8, 4]
Output: [4, 9]

The number 4 appears once in arr1 and twice in arr2 — the smaller count is 1, so 4 appears once. The number 9 appears once in arr1 and twice in arr2 — again the smaller count is 1, so 9 appears once. The number 5 is only in arr1, and 8 is only in arr2, so both are dropped.

How to Think About Solving It

The key insight is "take the smaller count of each value." A clean way to do this:

1. Count how many times each number appears in arr1. A good tool for this is a hash map (a structure that stores a value and a count linked together).
2. Go through arr2 one number at a time. For each number, check the map. If its count there is greater than 0, add that number to your result and reduce the count by 1.
3. Reducing the count makes sure each shared occurrence is matched only once, which is exactly why 2 came out twice — not three times — in Example 1.

The Code Skeleton

You need to fill in the body of this function:

class Solution {
public:
    vector<int> repeatedIntersections(
        vector<int> &arr1,
        vector<int> &arr2
    ) {

    }
};

It takes two integer vectors (C++'s name for a resizable array) and must return a vector<int> holding the intersection.