Problem Description
Alice and Bob have a different total number of candies. You are given two integer arrays aliceSizes and bobSizes where aliceSizes[i] is the number of candies of the ith box of candy that Alice has and bobSizes[j] is the number of candies of the jth box of candy that Bob has. Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy. The total amount of candy a person has is the sum of the number of candies in each box they have. Return an integer array answer where answer[0] is the number of candies in the box that Alice must exchange, and answer[1] is the number of candies in the box that Bob must exchange. If there are multiple answers, you may return any one of them. It is guaranteed that at least one answer exists.
Key Insights
- Calculate the total number of candies for both Alice and Bob.
- Determine the difference in their total candies.
- To equalize their candies, find boxes to exchange based on the difference calculated.
- Use a hash set to store the candy counts of one person for quick lookup.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
The solution involves calculating the total number of candies for Alice and Bob. We then determine the difference that needs to be compensated through the exchange. For each candy count in one array, we check if there exists a corresponding count in the other array that would satisfy the equality condition after the exchange. A hash set is used to allow for O(1) average time complexity for lookups.