Fair Candy Swap
EasyPrompt
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] <= 105- Alice and Bob have a different total number of candies.
- There will be at least one valid answer for the given input.
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. We simply try every possible swap and check if it's a fair one. We calculate the initial total candies for Alice and Bob. Then, we use nested loops to iterate through every possible pair of candy boxes, one from Alice and one from Bob. For each pair, we check if swapping them would result in both having the same total amount of candy. The first such pair we find is our answer.
Algorithm
- Calculate
sumA, the sum of all elements inaliceSizes. - Calculate
sumB, the sum of all elements inbobSizes. - Iterate through each element
xinaliceSizesusing an outer loop. - Inside this loop, iterate through each element
yinbobSizesusing an inner loop. - For each pair
(x, y), check if swapping them makes the totals equal. The condition issumA - x + y == sumB - y + x. - Since an answer is guaranteed to exist, the first pair that satisfies this condition is a valid solution. Return
[x, y].
Walkthrough
The algorithm begins by computing the total sum of candies for Alice (sumA) and Bob (sumB). The core of the problem is to find a candy box x from Alice and y from Bob such that after the swap, their new totals are equal. The new total for Alice would be sumA - x + y, and for Bob, sumB - y + x. We need to find x and y that satisfy sumA - x + y = sumB - y + x.
To find this pair, we can iterate through all of Alice's boxes. For each of her boxes x, we iterate through all of Bob's boxes y and check if the equality holds. As soon as we find a pair (x, y) that satisfies the condition, we can return it as the answer.
class Solution { public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) { int sumA = 0; for (int x : aliceSizes) { sumA += x; } int sumB = 0; for (int y : bobSizes) { sumB += y; } for (int x : aliceSizes) { for (int y : bobSizes) { if (sumA - x + y == sumB - y + x) { return new int[]{x, y}; } } } return null; // Should not be reached as an answer is guaranteed }}Complexity
Time
O(N * M), where N is the length of `aliceSizes` and M is the length of `bobSizes`. Calculating the initial sums takes O(N + M), but this is dominated by the nested loops which perform N * M comparisons.
Space
O(1), as we only use a few variables to store the sums and loop indices, not dependent on the input size.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space, O(1).
Cons
Highly inefficient for large input arrays, with a quadratic time complexity.
Likely to cause a 'Time Limit Exceeded' error on most coding platforms.
Solutions
Solution
class Solution {public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) { int s1 = 0, s2 = 0; Set<Integer> s = new HashSet<>(); for (int a : aliceSizes) { s1 += a; } for (int b : bobSizes) { s.add(b); s2 += b; } int diff = (s1 - s2) >> 1; for (int a : aliceSizes) { int target = a - diff; if (s.contains(target)) { return new int[]{a, target}; } } return null; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.