Fair Candy Swap

Easy

Amazon

1 view

Topics:

ArraysTwo Pointers

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]

Formulate an algorithm to find the candy box sizes that Alice and Bob must exchange. What is the time and space complexity of your solution? Are there any edge cases to consider? Can you provide code implementing your solution in Python?

Fair Candy Swap

Easy

Amazon

1 view

Topics:

ArraysTwo Pointers

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]

Formulate an algorithm to find the candy box sizes that Alice and Bob must exchange. What is the time and space complexity of your solution? Are there any edge cases to consider? Can you provide code implementing your solution in Python?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values within `aliceSizes` and `bobSizes`?
Can the input arrays `aliceSizes` or `bobSizes` be empty or null?
If there are multiple possible candy exchanges that result in equal sums, is any valid pair acceptable as the output?
Is it guaranteed that a solution (a valid candy exchange) will always exist?
Are there any constraints on the size of `aliceSizes` and `bobSizes` that I should be aware of?

Brute Force Solution

Approach

The core idea is to try out every single combination of candy swaps between Alice and Bob. We painstakingly check each potential swap to see if it results in a fair exchange, meaning both Alice and Bob end up with an equal amount of candy.

Here's how the algorithm would work step-by-step:

For every piece of candy Alice has, consider swapping it with every piece of candy Bob has.
For each potential swap, calculate the total amount of candy Alice would have after giving one candy to Bob and receiving one from him.
Calculate the total amount of candy Bob would have after giving one candy to Alice and receiving one from her.
Check if, after this swap, Alice's total candy amount is equal to Bob's total candy amount.
If the amounts are equal, you've found a fair swap! This swap provides the answer.
If you go through every single possible swap and don't find one that makes the amounts equal, then you've exhausted all possibilities.

Code Implementation

def fair_candy_swap_brute_force(alice_sizes, bob_sizes):
    alice_total = sum(alice_sizes)
    bob_total = sum(bob_sizes)

    for alice_candy in alice_sizes:
        for bob_candy in bob_sizes:
            #Calculate new totals if a swap occurs
            new_alice_total = alice_total - alice_candy + bob_candy

            new_bob_total = bob_total - bob_candy + alice_candy

            # Check if totals are equal after potential swap
            if new_alice_total == new_bob_total:
                return [alice_candy, bob_candy]

    return []

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the size of Alice's candy array and m be the size of Bob's candy array. The algorithm iterates through each element in Alice's array (n elements) and, for each of those, iterates through each element in Bob's array (m elements). Inside the nested loops, there are constant-time operations for calculating the new sums and comparing them. Therefore, the time complexity is proportional to n*m, representing the product of the sizes of the two input arrays.

Space Complexity

O(1) – The provided algorithm iterates through Alice's candy and Bob's candy, calculating sums after potential swaps. It doesn't create any auxiliary data structures like lists, hash maps, or sets to store intermediate results or visited elements. The calculations are performed using simple variables to store temporary sums. Therefore, the space complexity remains constant regardless of the input size.

Optimal Solution

Approach

The key to efficiently solving this problem is to understand the relationship between the sums of the two sets of candies and find the right swap without trying every possibility. We figure out how much the sums need to change and look for the numbers that achieve that change.

Here's how the algorithm would work step-by-step:

First, calculate the total number of candies each person has.
Figure out the difference between the two totals. Since we want the totals to be equal after the swap, this difference tells us how much the totals need to change, and therefore what the difference between the numbers being swapped must be.
Take the difference and divide it by two. This tells us what one person needs to give and the other needs to receive to make the amounts equal.
For one person's candy collection, check to see if they have a candy that, when you add the number you calculated in the previous step, you find a matching candy in the other person's collection.
If you find such a pair, you've found the swap that makes the totals equal, and you can return those two candies.

Code Implementation

def fair_candy_swap(alice_candies, bob_candies):    alice_total_candies = sum(alice_candies)
    bob_total_candies = sum(bob_candies)

    # Calculate the difference needed for a fair swap.
    difference = (bob_total_candies - alice_total_candies) // 2

    alice_candies_set = set(alice_candies)

    # Iterate through Bob's candies to find the swap.
    for bob_candy in bob_candies:
        alice_needed = bob_candy - difference

        # Check if Alice has the candy needed for the swap.
        if alice_needed in alice_candies_set:

            # If found, return the pair of candies.
            return [alice_needed, bob_candy]

    return []

Big(O) Analysis

Time Complexity

O(n) – Calculating the sums of the two candy arrays (A and B) takes O(n) time where n is the total number of candies across both arrays. The crucial part is determining whether a swap exists. The described solution involves calculating a 'target' value and then effectively searching for a corresponding candy. If the candies in one person's set (say A) are placed in a hash set, the search becomes O(1) per candy in the other set (B). Thus the search is effectively iterating through all the candies once leading to O(n), hence a total of O(n) for the solution.

Space Complexity

O(N) – The provided plain English explanation suggests creating a set from one of the candy collections (either Alice's or Bob's). This set, used for checking if a target candy exists in the other person's collection, will store at most N elements, where N is the number of candies that person has. Therefore, the auxiliary space scales linearly with the size of the larger candy collection. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input arrays	Return an empty array or null, as no exchange is possible.
One array is empty and the other is not	Return an empty array or null, since no exchange is possible in this scenario.
Arrays with a single element each	Check if the single elements satisfy the condition after swapping; if not, return an empty array.
Arrays with identical values in one or both arrays	The solution should still find a valid swap if one exists, due to the sum calculation and the set check.
Large array sizes (potential performance bottleneck)	Using a HashSet or HashMap for `bobSizes` allows for O(1) lookup, improving performance over nested loops, aiming for O(n+m) complexity.
Integer overflow when calculating sums	Use long data type for storing sums to prevent integer overflow issues.
No valid swap exists	Return an empty array or null if no candy exchange can equalize the sums.
Arrays contain duplicate numbers, and multiple valid solutions exist	The solution will return the first valid swap it finds, as specified in the prompt, though other valid solutions might exist.