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.
A more optimized approach involves sorting both arrays first. After sorting, we can use a two-pointer technique to find the correct pair of candy boxes to swap. By moving the pointers intelligently based on the comparison, we can find the solution in a single pass through the sorted arrays, which is much faster than the nested loops of the brute-force method.
Algorithm
- Calculate
sumA(sum ofaliceSizes) andsumB(sum ofbobSizes). - Determine the required difference in the swapped items:
diff = (sumA - sumB) / 2. The goal is to findxfrom Alice andyfrom Bob such thatx - y = diff. - Sort both
aliceSizesandbobSizesarrays in ascending order. - Initialize two pointers,
i = 0foraliceSizesandj = 0forbobSizes. - Loop while both pointers are within their array bounds:
- If
aliceSizes[i] - bobSizes[j] == diff, a match is found. Return[aliceSizes[i], bobSizes[j]]. - If
aliceSizes[i] - bobSizes[j] < diff, the difference is too small. We need a largerxto increase it, so incrementi. - If
aliceSizes[i] - bobSizes[j] > diff, the difference is too large. We need a largeryto decrease it, so incrementj.
- If
Walkthrough
First, we establish the mathematical relationship for the swap. If Alice swaps x for y, her new total is sumA - x + y. Bob's is sumB - y + x. For these to be equal, sumA - x + y = sumB - y + x, which simplifies to x - y = (sumA - sumB) / 2. Let's call this target difference diff.
Our goal is to find an x in aliceSizes and a y in bobSizes that satisfy this equation. By sorting both arrays, we can search for this pair efficiently. We use two pointers, i starting at the beginning of the sorted aliceSizes and j at the beginning of the sorted bobSizes. We compare aliceSizes[i] - bobSizes[j] with our target diff. If the current difference is smaller than diff, we need to increase it by picking a larger x, so we advance pointer i. If it's larger, we need to decrease it by picking a larger y, so we advance pointer j. If they are equal, we've found our answer.
import java.util.Arrays; 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; int diff = (sumA - sumB) / 2; Arrays.sort(aliceSizes); Arrays.sort(bobSizes); int i = 0, j = 0; while (i < aliceSizes.length && j < bobSizes.length) { int currentDiff = aliceSizes[i] - bobSizes[j]; if (currentDiff == diff) { return new int[]{aliceSizes[i], bobSizes[j]}; } else if (currentDiff < diff) { i++; } else { j++; } } return null; // Should not be reached }}Complexity
Time
O(N log N + M log M). The sorting of `aliceSizes` takes O(N log N) and `bobSizes` takes O(M log M). The subsequent two-pointer scan takes O(N + M). The sorting steps are the bottleneck.
Space
O(log N + log M) to O(N + M), depending on the sorting algorithm's implementation. This space is for the recursion stack or temporary arrays used by sorting. For instance, Java's `Arrays.sort` for primitives has an average space complexity of O(log N).
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Space-efficient, as it typically uses O(log N + log M) space for sorting, which is better than the O(M) or O(N) space of the hash set approach.
Cons
The time complexity is dominated by sorting, making it slower than the linear-time hash set approach.
Modifies the input arrays by sorting them, which might not be desirable in some contexts (though a copy can be made).
The most time-efficient solution uses a hash set to optimize the search. The core idea is to transform the problem from a search in a nested loop (O(N*M)) to a series of lookups in a hash set (O(N) lookups at O(1) each). We can determine the exact value Bob needs to give for any given value Alice gives. Then, we can check if Bob possesses a candy box of that exact value in constant average time using the hash set.
Algorithm
- Calculate
sumAandsumB. - Calculate the target difference
diff = (sumB - sumA) / 2. The equation we need to satisfy isy = x + diff. - Create a
HashSetand populate it with all of Bob's candy sizes. This allows for O(1) average time lookups. - Iterate through each candy box
xinaliceSizes. - For each
x, calculate the required candy box sizeythat Bob must have:y = x + diff. - Check if the hash set contains
y. - If it does, we have found the correct pair. Return
[x, y].
Walkthrough
We start with the same mathematical foundation: sumA - x + y = sumB - y + x. This can be rearranged to solve for y in terms of x: 2y = sumB - sumA + 2x, which gives y = x + (sumB - sumA) / 2. Let diff = (sumB - sumA) / 2.
The algorithm is as follows:
- First, calculate
sumAandsumB. - To quickly check if Bob has the required candy
y, we first store all of Bob's candy sizes in aHashSet. This takes O(M) time and space, where M is the number of Bob's candy boxes. - Then, we iterate through Alice's candy boxes. For each box
x, we calculate the target valuey = x + diff. - We then check if this calculated
yexists in our hash set of Bob's candies. This check is, on average, an O(1) operation. - The first time we find such a
y, we have found our answer and can return[x, y].
import java.util.HashSet;import java.util.Set; class Solution { public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) { int sumA = 0; for (int x : aliceSizes) { sumA += x; } int sumB = 0; Set<Integer> setB = new HashSet<>(); for (int y : bobSizes) { sumB += y; setB.add(y); } int diff = (sumB - sumA) / 2; for (int x : aliceSizes) { int y = x + diff; if (setB.contains(y)) { return new int[]{x, y}; } } return null; // Should not be reached }}Complexity
Time
O(N + M), where N and M are the lengths of the arrays. It takes O(N) to calculate `sumA`, O(M) to calculate `sumB` and populate the set, and O(N) to iterate through `aliceSizes` with O(1) lookups. The total is O(N + M).
Space
O(M), where M is the length of `bobSizes`. This space is used to store Bob's candy sizes in the hash set. To optimize, we could choose to put the smaller of the two arrays into the set.
Trade-offs
Pros
Optimal time complexity of O(N + M).
Conceptually simple, leveraging a common data structure to optimize search.
Cons
Requires extra space to store one of the arrays in a hash set, which could be significant if the array is large.
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; }}class Solution {public: vector<int> fairCandySwap(vector<int> &aliceSizes, vector<int> &bobSizes) { int s1 = accumulate(aliceSizes.begin(), aliceSizes.end(), 0); int s2 = accumulate(bobSizes.begin(), bobSizes.end(), 0); int diff = (s1 - s2) >> 1; unordered_set<int> s(bobSizes.begin(), bobSizes.end()); vector<int> ans; for (int &a : aliceSizes) { int target = a - diff; if (s.count(target)) { ans = vector<int>{a, target}; break; } } return ans; }};class Solution: def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]: diff = (sum(aliceSizes) - sum(bobSizes)) >> 1 s = set(bobSizes) for a in aliceSizes: target = a - diff if target in s: return [a, target]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.