The way the "disjoint pair" condition was phrased was, to me, very confusing.

As they explained it; "in order for a beautiful pair to be considered disjoint, its indices cannot appear in any other beautiful pairs". This, to me, meant that any indices with multiple value matches would be excluded from the final set.

What they MEANT was "each i and j index can only be used once in the result set".

Maybe if they used fewer mathematical expressions and actually spelled out what they were looking for from us.

If anyone gets caught up on test case 4 and 5. Know that the optimal amount of beautiful pairs does not always mean the maximum amount. You have to always change 1 element in B even if you end up with one less pair than if you didn't.

I curse the problem setter from the bottom of my heart. Very pathetic language and logic is used to form this question.

Java O(n) solution

From my HackerRank solutions.

For an element in A, if there's a matching element in B, this creates a "beautiful pair". Each element can only be used once to create a beautiful pair.

Additionaly, We MUST change exactly 1 element in B. We attempt to change it to create 1 more beautiful pair. In the special case where we already have the max number of beautiful pairs, being forced to change it gives us 1 less beautiful pair.

Time Complexity: O(n)
Space Complexity: O(1)

import java.util.Scanner;

public class Solution {
    
    private static final int MAX_NUM = 1000;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int [] bucketA = new int[MAX_NUM + 1];
        for (int i = 0; i < N; i++) {
            bucketA[scan.nextInt()]++;
        }
        int beautifulPairs = 0;
        for (int i = 0; i < N; i++) {
            int num = scan.nextInt();
            if (bucketA[num] > 0) {
                bucketA[num]--;
                beautifulPairs++;
            }
        }
        scan.close();
        
        /* Accounts for changing 1 element in B */
        if (beautifulPairs == N) {
            beautifulPairs--;
        } else {
            beautifulPairs++;
        }
        System.out.println(beautifulPairs);
    }
}

Let me know if you have any questions.

i've done many questions marked moderate on hackerrank which are easier than this.