Brute Force Solution

A naive solution would involve iterating through all possible pairs of boxes, one from Alice and one from Bob, and checking if swapping them results in an equal total amount of candy for both. This approach has a time complexity of O(n*m), where n is the number of boxes Alice has and m is the number of boxes Bob has.

Code

def fair_candy_swap_brute_force(aliceSizes, bobSizes):
    sum_alice = sum(aliceSizes)
    sum_bob = sum(bobSizes)

    for a in aliceSizes:
        for b in bobSizes:
            if sum_alice - a + b == sum_bob - b + a:
                return [a, b]
    return []

Complexity Analysis

• Time Complexity: O(n*m), where n is the length of aliceSizes and m is the length of bobSizes.
• Space Complexity: O(1), as we use a constant amount of extra space.

Optimal Solution

To optimize, we can use a set to store the candy box sizes of Bob. This allows us to check in O(1) time whether a particular candy box size is present in Bob's collection. We can calculate the required difference between the total candy of Alice and Bob. Then iterate through Alice's candy sizes, check if Bob has the corresponding candy size that makes total equal for both.

Algorithm

1. Calculate the sum of Alice's candies (sum_alice) and the sum of Bob's candies (sum_bob).
2. Compute the difference diff = (sum_bob - sum_alice) // 2. The value diff represents the amount that Bob needs to give to Alice to make the totals equal after the exchange. In other words, bob_gives - alice_gives = diff or bob_gives = alice_gives + diff
3. Create a set of Bob's candy sizes for fast lookup.
4. Iterate through Alice's candy sizes. For each candy size a, check if a + diff exists in Bob's candy set. If found, return [a, a + diff].

Code

def fair_candy_swap_optimal(aliceSizes, bobSizes):
    sum_alice = sum(aliceSizes)
    sum_bob = sum(bobSizes)

    diff = (sum_bob - sum_alice) // 2
    bob_set = set(bobSizes)

    for a in aliceSizes:
        if a + diff in bob_set:
            return [a, a + diff]
    return []

Complexity Analysis

• Time Complexity: O(n + m), where n is the length of aliceSizes and m is the length of bobSizes. Building the set takes O(m) time, and iterating through Alice's candies takes O(n) time. The lookup in the set takes O(1) on average.
• Space Complexity: O(m), where m is the length of bobSizes, due to the space used by the set.

Edge Cases

• The problem statement guarantees that a solution exists, so we don't need to handle the case where no solution is found.
• The problem statement also guarantees that Alice and Bob have a different total number of candies, so diff can't be 0, and a non-empty result is possible.