Maximize Distinct Values with Cross-Array Swaps
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Maximize Distinct Values with Cross-Array Swaps
Given arrays a and b of equal length and an integer k, perform at most k swaps. Each swap chooses one index in a and one index in b and exchanges those values. Return the maximum possible number of distinct values in a.
## Function Contract
Implement `max_distinct_after_swaps(a, b, k) -> int`.
## Constraints
- 0 <= array length <= 200000.
- 0 <= k <= 200000.
- Values are integers between -10^9 and 10^9.
- Any index in a may be swapped with any index in b.
## Examples
```text
a = [2, 3, 3, 2, 2], b = [1, 3, 2, 4, 1], k = 2
output = 4
```
```text
a = [1, 2], b = [1, 2], k = 5
output = 2
```
```hint Do not spend every swap automatically
The limit is "at most" k, so an optimal result may use fewer swaps or none.
```
```hint Exercise multiplicity
Test arrays where `a` is already all distinct, where it contains only one repeated value, and where `b` offers no useful change.
```
Quick Answer: Given arrays a and b of equal length and an integer k, perform at most k swaps. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given equal-length integer arrays `a` and `b`, perform at most `k` exchanges. Each exchange selects any index in `a` and any index in `b` and swaps those two values. Return the maximum possible number of distinct values in `a`. You may use fewer than `k` exchanges when additional exchanges would not help.
Constraints
- 0 <= len(a) = len(b) <= 200000.
- 0 <= k <= 200000; values are integers from -10^9 through 10^9.
- Each exchange may use any one index from a and any one index from b, and at most k exchanges are allowed.
Examples
Input: ([], [], 0)
Expected Output: 0
Explanation: Empty arrays have zero distinct values.
Input: ([2, 3, 3, 2, 2], [1, 3, 2, 4, 1], 2)
Expected Output: 4
Explanation: Two useful exchanges raise the distinct count from two to four.
Hints
- Test k = 0, an already distinct first array, and a second array with no outside values.
- Include many repeated values in each array, especially repeated copies of the same outside value.
- Check a budget larger than the array length to confirm that the at-most rule is respected.