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.
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)
importjava.util.Scanner;publicclassSolution{privatestaticfinalintMAX_NUM=1000;publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);intN=scan.nextInt();int[]bucketA=newint[MAX_NUM+1];for(inti=0;i<N;i++){bucketA[scan.nextInt()]++;}intbeautifulPairs=0;for(inti=0;i<N;i++){intnum=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);}}
Beautiful Pairs
You are viewing a single comment's thread. Return to all comments →
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)
Let me know if you have any questions.