84. Fair Trade
Alice and Bob each own a collection of collectible cards. The array alice holds the value of each of Alice's cards and bob holds the value of each of Bob's cards. They agree to swap exactly one card of Alice's for exactly one card of Bob's, so that after the swap the total value Alice holds equals the total value Bob holds.
Return an array [a, b] where a is the value of the card Alice hands over and b is the value of the card Bob hands over. The input is guaranteed to admit at least one valid swap. If several swaps work, return any one of them.
Example 1
- Input:
- alice = [5,8,3], bob = [2,4,8]
- Output:
- [5,4]
- Explanation:
Alice holds 16 and Bob holds 14; Alice gives 3 and Bob gives 2, so both end with 15 (giving 5 and 4 also works).
Example 2
- Input:
- alice = [7,4,1], bob = [5,3]
- Output:
- [7,5]
- Explanation:
Alice holds 12 and Bob holds 8; swapping Alice's 7 for Bob's 5 leaves both with 10, and it is the only valid swap.
Constraints
1 ≤ alice.length, bob.length ≤ 104
1 ≤ alice[i], bob[j] ≤ 105
At least one valid swap exists.
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
Expected complexity
- Time
- O(n + m)
- Space
- O(m)