algoadvance

Leetcode 888. Fair Candy Swap

Problem Statement

Alice and Bob have candy bars of different sizes. Alice has A array of candy bars, and Bob has B array of candy bars. They want to swap exactly one candy bar each so that after the swap, they both have the same total amount of candy.

Return an integer array ans where ans[0] is the candy bar from Alice’s collection that she should swap, and ans[1] is the candy bar from Bob’s collection that she should receive. If there are multiple answers, you may return any one of them. It is guaranteed that at least one answer exists.

Clarifying Questions

  1. Input constraints:
    • A and B arrays have lengths that are between 1 and 10^4.
    • Each candy bar size within arrays A and B ranges from 1 to 10^4.
  2. Output requirements:
    • The returned array should be of length 2, containing one candy bar from Alice’s array and one from Bob’s array that they should swap.

Strategy

To solve the problem:

  1. Calculate the total sum of both Alice’s and Bob’s candy bars.
  2. Determine the difference between the two sums.
  3. Use a set for constant time lookups to see if the complement of a candy bar from Alice’s array exists in Bob’s array, that would balance the total candy sums.

Time Complexity

The target solution should ideally:

Code

Here’s the C++ implementation to solve the problem:

#include <vector>
#include <unordered_set>
#include <numeric>

std::vector<int> fairCandySwap(std::vector<int>& A, std::vector<int>& B) {
    // Calculate the sum of both arrays
    int sumA = std::accumulate(A.begin(), A.end(), 0);
    int sumB = std::accumulate(B.begin(), B.end(), 0);
    
    // Calculating the difference
    int diff = (sumA - sumB) / 2;
    
    // Store B's elements in a set for O(1) lookups
    std::unordered_set<int> setB(B.begin(), B.end());
    
    // Find a pair to swap
    for (int a : A) {
        if (setB.count(a - diff)) {
            return {a, a - diff};
        }
    }
    
    // If no valid pair is found, though guaranteed there is one.
    return {};
}

Explanation

  1. Sum Calculation: Using std::accumulate, the total sum of candy bars for both Alice and Bob is computed.
  2. Difference Calculation: The difference divided by 2 is the needed adjustment for the swap to balance the sums.
  3. Lookup for Swapping:
    • An unordered set of Bob’s candy sizes is created for quick lookups.
    • Iterate over Alice’s candy sizes and check if subtracting the precomputed difference from any of Alice’s candy sizes exists in Bob’s set. If found, return the pair.

This efficient approach ensures the solution is both time and space-optimal.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI