Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count how many values A and B share as multisets — that is `Σ min(countA[v], countB[v])`, the maximum number of disjoint equal-value pairs. You must then change EXACTLY one element of B. If the multiset match already covers all n elements (every B element is paired), changing one element necessarily breaks a pair, so the answer is `matches − 1`. Otherwise there is an unmatched A value and a spare B element to retarget at it, giving `matches + 1`. O(n) with a hash map.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise the max matching as a multiset-intersection count, and whether you correctly handle the mandatory single change — especially the saturated case where the forced edit costs you a pair.
Where candidates slip
Forgetting the change is mandatory and just returning `matches`, or always returning `matches + 1` even when every element is already paired (which actually forces `matches − 1`).
How to stand out
Prove the cap: each value v contributes at most `min(countA[v], countB[v])` pairs, so the greedy count is optimal. Then case-split on whether slack exists for the forced edit.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewArrays A, B of size nmatches == n?Yes (saturated)No (slack exists)Explore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Try Every Single Edit
1Hint 1Explore hintHide hint
The rule says change exactly one element of B. The most literal plan is to try every possible single change and measure the result.
2Hint 2Explore hintHide hint
For each position j in B and each candidate value v (1..V), build the modified B and count the maximum disjoint equal-value matching.
3Hint 3Explore hintHide hint
Counting one matching is O(n) with a hash map; doing it for every (j, v) is O(n · V) builds × O(n) each → far too slow, but it makes the answer concrete.
A · Core idea
Take the rule at face value: you must change exactly one element of B. So enumerate every way to do that — pick a position j and a new value v — and for each resulting array compute the maximum number of beautiful pairs.
How to score one array. The maximum disjoint matching between two multisets is the intersection count: tally B's values in a hash map, then walk A and consume one matching count per element that is still available. That single count is O(n).
Why it's correct but wasteful. Every legal single edit is examined, so the maximum over all of them is exactly the answer. But the candidate-value range V and the n positions multiply with the O(n) scoring, giving O(n²·V). For n, V up to 1000 that's a billion operations.
The structure it exposes. Scanning the results, two facts pop out. (1) The best you can ever reach is bounded by the base intersection count plus one — a single edit can create at most one new pair. (2) Whether you actually gain that +1 depends only on whether the base matching already used every element. That collapses the whole search into one count and a case-split.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
A = [10, 16, 5], B = [5, 3, 1]no edit (baseline)
shared value {5} → 1 pair
base = 12 (any spare B element retargeted to an unmatched A value yields base + 1)C · Code with teaching comments
Reference implementation previewpublic int beautifulPairs(List<Integer> A, List<Integer> B) { int n = A.size(); int best = 0; for (int j = 0; j < n; j++) { for (int v = 1; v <= 1000; v++) {Explore the full codeHide the full code
D · Why it works and complexityO(n² · V) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Brute force reveals the answer is always within ±1 of the base intersection count, and which side you land on depends solely on saturation — turning an O(n²·V) search into an O(n) count.
ComplexityO(n² · V) time, O(n) space — There are n positions × V candidate values = n·V modified arrays, and scoring each matching is O(n). The product is O(n²·V) — only a teaching device.
E · Edge cases and pitfalls3O(n²·V) is far too slow for n, V up to 1000 — teaching device only.Explore edge casesHide edge cases
Pitfalls
- O(n²·V) is far too slow for n, V up to 1000 — teaching device only.
- Recomputing the full matching for every candidate value instead of reasoning about ±1.
- Forgetting the matching must be disjoint (consume each element once).
Approach 2 of 2 · Optimal
Greedy — Multiset Intersection Count, Then Forced ±1 (Optimal)
1Hint 1Explore hintHide hint
Forget the edit for a moment. What is the maximum number of disjoint equal-value pairs between A and B? It is fixed by how many of each value the two arrays share.
2Hint 2Explore hintHide hint
For each value v, you can form min(countA[v], countB[v]) pairs. Sum that over all values to get the base matching.
3Hint 3Explore hintHide hint
Now bring back the mandatory edit. If the base matching used every element (matches == n), the edit must break a pair → matches − 1. Otherwise a spare B element can be retargeted to an unmatched A value → matches + 1.
A · Core idea
Tally one array's values in a hash map, then walk the other array consuming one available count per matching element. That sum is the base matching matches = Σ min(countA[v], countB[v]). Finally apply the mandatory edit with a one-line case-split.
Why the count is the maximum — the exchange/upper-bound argument. Consider any valid disjoint matching. Group its pairs by their shared value v. Each pair on value v consumes one occurrence of v from A and one from B, so the number of v-pairs cannot exceed min(countA[v], countB[v]). Summing this ceiling over all values gives an upper bound, and the greedy 'consume while available' construction achieves it for every value simultaneously (the values don't compete — a pair on value v never blocks a pair on a different value). Bound met = optimal.
Why the forced edit gives +1 when there is slack. If matches < n, then after the base matching at least one A index is unpaired (its value had no remaining B partner) and at least one B index is unused. Set that spare B element equal to the unmatched A value: a brand-new pair appears, and no existing pair is touched. So we reach matches + 1, and we cannot do better — one edit creates at most one new pair.
Why the forced edit gives −1 when saturated. If matches == n, every B element is already part of a pair. The mandatory change rewrites one of them; whatever new value it takes, the pair it used to serve is destroyed and at most that one pair can be re-formed elsewhere — but every other element is already consumed, so nothing is free to re-pair with it. The net is one fewer pair: matches − 1.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
A = [1, 2, 3, 4], B = [1, 2, 3, 3]Hash-map state
b=1
1Match found
count[1] 1→0, matches=1
4C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Two independent ideas compose cleanly: (1) max equal-value matching = multiset intersection = Σ min(countA, countB), provable by a per-value capacity argument; (2) a single mandatory edit shifts the answer by exactly +1 (if slack) or −1 (if saturated). Recognising 'matching capped by per-key minimum' is the reusable greedy kernel.
ComplexityO(n) time, O(n) space — One pass to count B (or A), one pass to consume matches against the other — O(n) time, O(n) for the hash map. The ±1 decision is O(1).
E · Edge cases and pitfalls6A = [3,3,3], B = [3,3,3] — matches = 3 = n → saturated → forced change breaks a pair → 2.Explore edge casesHide edge cases
Edge cases handled
A = [3,3,3], B = [3,3,3]matches = 3 = n → saturated → forced change breaks a pair → 2.A and B share no valuematches = 0 < n → retarget any B element to an A value → 1.A = [1,2], B = [1,2]matches = 2 = n → saturated → 1.
Pitfalls
- Returning `matches` and forgetting the change is mandatory.
- Always returning `matches + 1` even when saturated — the saturated case is actually `matches − 1`.
- Counting plain set intersection instead of multiset (min of counts) — drops valid duplicate pairs.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int beautifulPairs(List<Integer> A, List<Integer> B) { Map<Integer, Integer> count = new HashMap<>(); for (int a : A) count.merge(a, 1, Integer::sum); int matches = 0; for (int b : B) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Ignoring the mandatory edit in the saturated case
When matches == n every element is already paired; a forced change must break a pair, so the answer is matches − 1, not matches or matches + 1.
Explore the code comparisonHide the code comparison
Ignoring the mandatory edit in the saturated case
When matches == n every element is already paired; a forced change must break a pair, so the answer is matches − 1, not matches or matches + 1.
Don't write this
matches = sum(min(ca[v], cb[v]) for v in ca)
return matches + 1Write this instead
matches = sum(min(ca[v], cb[v]) for v in ca)
return matches - 1 if matches == len(A) else matches + 12Set intersection instead of multiset
Using distinct shared values drops duplicate pairings. A = [3,3], B = [3,3] should give 2 base pairs, not 1.
Explore the code comparisonHide the code comparison
Set intersection instead of multiset
Using distinct shared values drops duplicate pairings. A = [3,3], B = [3,3] should give 2 base pairs, not 1.
Don't write this
Set<Integer> sa = new HashSet<>(A), sb = new HashSet<>(B);
sa.retainAll(sb);
int matches = sa.size();Write this instead
Map<Integer,Integer> count = new HashMap<>();
for (int a : A) count.merge(a, 1, Integer::sum);
int matches = 0;
for (int b : B) { Integer c = count.get(b); if (c != null && c > 0) { matches++; count.put(b, c - 1); } }3Python truthiness on a zero count
Counter returns 0 for missing keys; `if count[b]:` is fine, but `if count.get(b):` with a defaultless dict would KeyError, and writing `if count[b] is not None` is wrong since 0 is a real value. Use `count[b] > 0`.
Explore the code comparisonHide the code comparison
Python truthiness on a zero count
Counter returns 0 for missing keys; `if count[b]:` is fine, but `if count.get(b):` with a defaultless dict would KeyError, and writing `if count[b] is not None` is wrong since 0 is a real value. Use `count[b] > 0`.
Don't write this
if count.get(b):
matches += 1
count[b] -= 1Write this instead
if count[b] > 0:
matches += 1
count[b] -= 1Revise
Carry the pattern into the interview
Pattern to remember
Greedy multiset matching by value, then a forced ±1 from the mandatory single change
Code pattern to memorize
matches = Σ over values v of min(countA[v], countB[v])
if matches == n: return matches - 1 # everything paired, a change must break one
else: return matches + 1 # spare B element retargets an unmatched A valueRules to remember
- 1A 'beautiful pair' is a pairing of distinct indices (i, j) with
A[i] == B[j]; each index of A and each index of B is used at most once. - 2The maximum disjoint matching equals the multiset intersection size
Σ min(countA[v], countB[v])— never more, because each shared value v can back at mostmin(countA[v], countB[v])pairs. - 3You must change exactly one element of B — it is not optional. This is the whole twist of the problem.
- 4If
matches < nyou can always domatches + 1: some A value is unmatched and some B element is unused, so retarget that B element to the A value. - 5If
matches == nevery B element is already paired, so any change destroys a pair and the best you can reach ismatches − 1(then a re-pair recovers nothing because all were already used).
Use this pattern when
- Maximising equal-value pairings between two collections where each element is consumed once
- A multiset-intersection count is the core quantity
- A constraint forces exactly one mutation and you must reason about its marginal effect
- Pair counts are bounded by per-value minimum counts
Choose another pattern when
- Pairs are defined by an inequality or distance, not exact equality → sorting / two pointers, not counting
- Elements may be reused across multiple pairs → not a disjoint matching
- You may change any number of elements → the ±1 edge logic disappears
- Order/positions matter (i must relate to j) → this is a different, positional problem
Interview takeaway
Maximum equal-value matching between two multisets is just `Σ min(countA[v], countB[v])` — counting beats searching. The interview spice is the mandatory single edit: reason about whether that edit can ADD a pair (slack exists) or is forced to REMOVE one (already saturated).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternMultiset-intersection matching capped by per-value min counts, plus a forced single-edit ±1 case-split. Recognise it whenever maximum equal-value pairings between two collections is the core, and a mandatory mutation perturbs the answer by exactly one.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Permuting Two ArraysAnother two-array greedy — sort oppositely and check a per-index condition instead of counting.
- Sherlock and the Valid StringComing soonFrequency counting again, with a one-deletion adjustment reminiscent of the forced edit here.
- Two StringsComing soonMultiset/set intersection over characters — same counting idea, simpler decision.
- Priyanka and ToysGreedy over a sorted array; pairs counting gives way to interval covering.