Beautiful Pairs · Coding Gym

Solutions

For each element in \(A\), we have to find the same element in \(B\). This is basically like performing the intersection between \(A\) and \(B\).

Then, since we have to change one element in \(B\) in any case:

if the intersection is just \(A\), we return A.size() - 1
otherwise, we return inters.size() + 1

Here is the idea in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int beautifulPairs(vector<int>& A, vector<int>& B) 
{
    sort(begin(A), end(A));
    sort(begin(B), end(B));
    vector<int> inters;
    set_intersection(begin(A), end(A), begin(B), end(B), back_inserter(inters));
    if (inters.size() == A.size())
        return inters.size() - 1;
    return inters.size() + 1;
}

This solution costs \(O(N \cdot logN)\) because of using sort.

Since the domain is small we can either use a better sorting strategy (e.g. radix, counting sort) or we can just use a frequency table:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


int beautifulPairs(const vector<int>& A, const vector<int>& B) 
{
    array<int, 1000+1> freq{};
    for (auto i : B)
        freq[i]++;
    
    auto cnt = 0;
    for (auto i : A)
    {
        if (freq[i])
        {
            freq[i]--;
            cnt++;
        }
    }

    return cnt + (cnt == A.size() ? -1 : 1);
}

This solution is linear time and constant space. Consider the tradeoff: if the domain changes we might be forced to change the solution.

In Python we can simply use Counter:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def beautifulPairs(A, B):
    ac = Counter(A)
    bc = Counter(B)
    pairs = 0
    for val in ac:
        if val in bc:
            pairs += min(ac[val],bc[val])
    if pairs == len(A):
        return pairs - 1
    else:
        return pairs + 1

frequency table sort