algoadvance

Leetcode 888. Fair Candy Swap

Problem Statement

  1. Fair Candy Swap-out

Alice and Bob have candy bars of different sizes. They would like to swap one candy bar each so that after the swap, they both have the same total amount of candy.

You are given two integer arrays A and B where A[i] and B[i] are the sizes of the candy bars that Alice and Bob have, respectively. Return an integer array ans where ans[0] is the size of the candy bar Alice must exchange, and ans[1] is the size of the candy bar 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: A = [1,1], B = [2,2]
Output: [1,2]

Example 2:

Input: A = [1,2], B = [2,3]
Output: [1,2]

Example 3:

Input: A = [2], B = [1,3]
Output: [2,3]

Example 4:

Input: A = [1,2,5], B = [2,4]
Output: [5,4]

Constraints:

  1. 1 <= A.length, B.length <= 10000
  2. 1 <= A[i], B[i] <= 100000
  3. It is guaranteed that there exists an answer.

Clarifying Questions

  1. Can I assume the total sums of the candy arrays differ by an even number?
    • Yes, the problem guarantees at least one valid swap exists, implying that the total difference is even.
  2. Is the input always valid (i.e., non-empty arrays)?
    • Yes, input arrays will contain at least one element as per constraints.
  3. Are there any specific edge cases I should consider?
    • No specific edge cases are hinted in the problem; generic valid input should suffice.

Strategy

  1. Calculate the total sum of Alice’s A and Bob’s B candy bars.
  2. Find the difference in their sums and compute the target difference for the swap.
    • Target difference delta is given by (sumA - sumB) / 2.
  3. Use a set data structure to quickly determine if a valid swap exists.
    • Convert A into a set to leverage O(1) average-time complexity for lookup operations.
  4. Iterate through Bob’s list B, trying to find a corresponding element a in A such that the equality condition holds.
    • Specifically, if a - b = delta, then swapping these elements ensures equal sums.

Code

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA = 0;
        int sumB = 0;
        
        for (int a : A) {
            sumA += a;
        }
        
        for (int b : B) {
            sumB += b;
        }
        
        int delta = (sumA - sumB) / 2;
        
        Set<Integer> setA = new HashSet<>();
        for (int a : A) {
            setA.add(a);
        }
        
        for (int b : B) {
            int a = b + delta;
            if (setA.contains(a)) {
                return new int[]{a, b};
            }
        }
        
        return new int[0]; // This line is never reached.
    }
}

Time Complexity

This approach ensures the solution is efficient and meets the problem constraints.

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