We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Beautiful Pairs
  5. Discussions

Beautiful Pairs

Sort by

recency

|

289 Discussions

|

  • alban_tyrex
     + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/coANgIdBKAk

    int beautifulPairs(vector<int> A, vector<int> B) {
    map<int, int> mp;
    int result = 0;
    for(int i = 0; i < A.size(); i++) mp[A[i]]++;
    for(int i = 0; i < B.size(); i++){
        if(mp[B[i]]){
            mp[B[i]]--;
            result++;
        }
    }
    return (result == A.size()) ? result - 1 : result + 1;
}

  • emhhacker
     + 0 comments

    My Java solution with linear time complexity and linear space complexity:

    public static int beautifulPairs(List<Integer> A, List<Integer> B) {
        // create a frequency map to get the count of eacg val
        Map<Integer, Integer> freqMap = new HashMap<>();
        for(int val : A) freqMap.put(val, freqMap.getOrDefault(val, 0) + 1);
        //iterate over each val in b and accoridngly increment the amt of pairs
        int pairs = 0;
        for(int val : B){
            if(freqMap.containsKey(val) && freqMap.get(val) > 0){
                pairs++;
                freqMap.put(val, freqMap.getOrDefault(val, 0) - 1);
            }
        }
        //if amt of pairs == a.size(), decrease it because by 1 bc an element must be changed
        //else add 1 bc an element isnt paired
        return (pairs == A.size()) ? pairs - 1 : pairs + 1;
    }

  • Kirkkm
     + 0 comments

    Here is my typescript solution:

    function beautifulPairs(A: number[], B: number[]): number {
    let counter: number = 0;
    
    /*
    * Looping through the A array and finding if there are any matched in the,
    * if there are then we count up and remove the element from the B array to
    * prevent duplicates being counted again
    */
    A.forEach((num) => {
        if (B.includes(num)) {
            counter ++;
            const indexToRemove: number = B.indexOf(num);
            B.splice(indexToRemove, 1)
        }
    })
    
    return counter === A.length ? counter -1 : counter +1;

}

  • pub_ashishk28
     + 0 comments

    Exhaustively, this problem can be considered in two cases

    1. A and B are similar. That is, for each item in A, there exists an item in B and there is no unmatched item in A. This directly implies vice-versa. In this case then, you will have to change something in B to something that's not in A. So you count no of paired items and reduce one.

    2. A and B are not similar. That is, there is at least one item in A that doesn't have its correponding pair in B which also implies vice-versa. In this case, you can change any one of those unmatched items in B back to something that already exists in A. So you count no of paired items and add one.

    Here is python3 solution. I must add this is not a greedy problem at all. A greedy approach requires making optimal choice at each pass of your solution. 

    def beautifulPairs(A, B):
    # Write your code here
    
    freq_A = Counter(A) # build a frequency dictionary
    
    paired = 0
    for i in B:
        if freq_A[i] > 0:
            paired += 1
            freq_A[i] -= 1
            
    common = freq_A.most_common(1)[0] #returns a tuple 
    
    if common[1] > 0:   #at least one unmatched item in A
        return paired + 1
    else:               # A and B are similar
        return paired - 1

  • deekshachauhan21
     + 0 comments

    can anyone help me out with this C# code its failing fro one testcase:

    public static int beautifulPairs(List A, List B) { HashSet setB = new HashSet(B); int bPairs = 0;

    foreach (int i in A)
{
    if (setB.Contains(i))
    {
        bPairs++;
        setB.Remove(i); // Ensures pairwise disjoint condition
    }
}

// If all elements are matched, changing any element reduces the count
if (bPairs == A.Count)
{
    return bPairs - 1; // Change one element in B to break a pair
}
else
{
    return bPairs + 1; // We can increase the count by changing one element in B
}

    }