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.
Example 1:
Input: aliceSizes = [1,1], bobSizes = [2,2] Output: [1,2]
Example 2:
Input: aliceSizes = [1,2], bobSizes = [2,3] Output: [1,2]
Example 3:
Input: aliceSizes = [2], bobSizes = [1,3] Output: [2,3]
Constraints:
1 <= aliceSizes.length, bobSizes.length <= 1041 <= aliceSizes[i], bobSizes[j] <= 105In this approach, we first calculate the total number of candies Alice and Bob have, respectively. Let this be sumA for Alice and sumB for Bob. If Alice swaps a candy box with x candies and Bob swaps a box with y candies, the condition to balance their total candies after swap can be derived as: sumA - x + y = sumB - y + x. Simplifying this, we get y = x + (sumB - sumA) / 2. Using this equation, we can loop through one person's candy sizes array and for each candy size, compute the necessary size from the other person's array and check if it exists using a set for quick lookup.
The C code initializes the required sums for Alice and Bob. Then it computes the difference in candies needed (delta) and uses an array to act as a set for Bob's candy sizes. Finally, it attempts to find a suitable swap by iterating over Alice's candy sizes and checking if Bob has the necessary candy size using the array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the length of aliceSizes and m is the length of bobSizes. This is because we iterate over each list once and use constant time checks for the existence of an element in Bob's collection.
Space Complexity: O(m), due to the additional space used for storing Bob's candy sizes in a set.
This approach involves first sorting both the candy size arrays of Alice and Bob. The idea is to use a two-pointer technique to find a suitable pair of candy boxes such that swapping them would balance Alice's and Bob's total candies. Once both lists are sorted, use two pointers, starting at the beginnings of Alice's and Bob's lists, and adjust them based on the comparison of their sums to find the correct swap.
This C solution first sorts both arrays and calculates the required delta. Two pointers are used to traverse both arrays, adjusting based on whether the sum of Bob's current candy size minus Alice's is less than, equal to, or greater than the delta. If an equal delta is found, it denotes a valid swap, and the function returns the pair.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n + m log m), due to the sorting step. The subsequent linear scan is O(n + m).
Space Complexity: O(1), with only a few additional variables used.
| Approach | Complexity |
|---|---|
| Approach 1: Calculating based on difference | Time Complexity: O(n + m), where n is the length of aliceSizes and m is the length of bobSizes. This is because we iterate over each list once and use constant time checks for the existence of an element in Bob's collection. |
| Approach 2: Sorting and Two-Pointer Technique | Time Complexity: O(n log n + m log m), due to the sorting step. The subsequent linear scan is O(n + m). |
Leetcode 888. Fair Candy Swap [Java] • if else statement • 5,568 views views
Watch 9 more video solutions →Practice Fair Candy Swap with our built-in code editor and test cases.
Practice on FleetCode