Beautiful Pairs

See the original problem on HackerRank.

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
We've worked on this challenge in these gyms: modena 
comments powered by Disqus