Fair Candy Swap

Difficulty: Easy | Acceptance: 64.90% | Paid: No Topics: Array, Hash Table, Binary Search, Sorting

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 in the ith box of candy that Alice has and bobSizes[j] is the number of candies in 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 sizes of candy boxes 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.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Hash Set
• Approach 3: Sorting + Binary Search
• Approach 4: Sorting + Two Pointers

Examples

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 <= 10^4
- 1 <= aliceSizes[i], bobSizes[j] <= 10^5
- Alice and Bob have a different total number of candies.
- There will be at least one valid answer for the given input.

Approach 1: Brute Force

Intuition Check every possible pair of candy boxes (one from Alice, one from Bob) to see if swapping them balances the total amounts.

Steps

• Calculate the total sum of candies for Alice (sumA) and Bob (sumB).
• Calculate the target difference delta = (sumA - sumB) / 2.
• Iterate through every candy size a in aliceSizes.
• Iterate through every candy size b in bobSizes.
• If a - b equals delta, return [a, b].

class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sumA, sumB = sum(aliceSizes), sum(bobSizes)
        delta = (sumA - sumB) // 2
        for a in aliceSizes:
            for b in bobSizes:
                if a - b == delta:
                    return [a, b]
        return []

Complexity

• Time: O(N * M), where N and M are the lengths of the arrays.
• Space: O(1)
• Notes: Simple but inefficient for large inputs.

Approach 2: Hash Set

Intuition Store Bob’s candy sizes in a hash set for O(1) lookups. For each candy Alice has, calculate the required candy size Bob needs to give and check if it exists in the set.

Steps

• Calculate sumA, sumB, and delta.
• Convert bobSizes into a set setB.
• Iterate through a in aliceSizes.
• Calculate target = a - delta.
• If target exists in setB, return [a, target].

class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sumA, sumB = sum(aliceSizes), sum(bobSizes)
        delta = (sumA - sumB) // 2
        setB = set(bobSizes)
        for a in aliceSizes:
            if a - delta in setB:
                return [a, a - delta]
        return []

Complexity

• Time: O(N + M)
• Space: O(M) to store the set.
• Notes: Optimal time complexity solution.

Approach 3: Sorting + Binary Search

Intuition Sort Bob’s array. For each candy Alice has, use binary search to check if the required candy size exists in Bob’s sorted array.

Steps

• Calculate sumA, sumB, and delta.
• Sort bobSizes.
• Iterate through a in aliceSizes.
• Calculate target = a - delta.
• Perform binary search for target in bobSizes.
• If found, return [a, target].

import bisect

class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sumA, sumB = sum(aliceSizes), sum(bobSizes)
        delta = (sumA - sumB) // 2
        bobSizes.sort()
        for a in aliceSizes:
            target = a - delta
            i = bisect.bisect_left(bobSizes, target)
            if i < len(bobSizes) and bobSizes[i] == target:
                return [a, target]
        return []

Complexity

• Time: O(M log M + N log M)
• Space: O(1) or O(M) depending on sorting implementation.
• Notes: Good alternative if space is tight, though generally slower than Hash Set due to sorting.

Approach 4: Sorting + Two Pointers

Intuition Sort both arrays. Use two pointers to traverse the arrays simultaneously to find the pair where the difference matches the required delta.

Steps

• Calculate sumA, sumB, and delta.
• Sort aliceSizes and bobSizes.
• Initialize pointers i = 0, j = 0.
• While i < len(aliceSizes) and j < len(bobSizes):
  • Calculate diff = aliceSizes[i] - bobSizes[j].
  • If diff == delta, return [aliceSizes[i], bobSizes[j]].
  • If diff > delta, increment j (need a larger Bob candy to reduce diff).
  • If diff < delta, increment i (need a larger Alice candy to increase diff).

class Solution:
    def fairCandySwap(self, aliceSizes: list[int], bobSizes: list[int]) -> list[int]:
        sumA, sumB = sum(aliceSizes), sum(bobSizes)
        delta = (sumA - sumB) // 2
        aliceSizes.sort()
        bobSizes.sort()
        i = j = 0
        while i < len(aliceSizes) and j < len(bobSizes):
            a = aliceSizes[i]
            b = bobSizes[j]
            if a - b == delta:
                return [a, b]
            elif a - b > delta:
                j += 1
            else:
                i += 1
        return []

Complexity

• Time: O(N log N + M log M)
• Space: O(1) or O(N + M) depending on sorting implementation.
• Notes: Efficient if data is already sorted.