888. Fair Candy Swap

Problem Description

Alice and Bob each have a collection of candy boxes, with each box containing a certain number of candies. The total number of candies each of them has is different. Given two lists, aliceSizes representing the number of candies in Alice's boxes and bobSizes for Bob's boxes, the task is to find a pair of boxes (one from Alice and one from Bob) that they can exchange with each other so that they end up with the same total number of candies.

In other words, we need to find two values, one from each list, such that when Alice gives Bob the box with her value and Bob gives Alice the box with his value, the total candies they each have will be equal. The problem ensures that there is at least one such pair and asks us to return any one of them as a 2-element array: [Alice's box of candies, Bob's box of candies].

Intuition

The solution to this problem relies on the concept of the exchange itself and the resulting equality of candy totals for Alice and Bob. If x is the amount of candies in the box Alice gives to Bob, and y is the amount in the box Bob gives to Alice, after the exchange, the total candies for both should be the same. If we denote sumA as the total candies that Alice has and sumB for Bob, the equation after the exchange would be:

(sumA - x) + y = (sumB - y) + x

Which can be simplified to:

sumA - sumB = 2 * (x - y)

By rearranging the terms, we get the difference diff between the totals divided by 2 equals the difference between x and y:

diff = sumA - sumB

x - y = diff / 2

Given this, we can then iterate through Alice's boxes, and for each candy count a, we can calculate the corresponding count target = a - diff / 2 that we're looking for in Bob's boxes. Then by utilizing a Set in Python that contains all of Bob's candy box counts, we can quickly check whether this target exists. Because Set operations in Python are O(1) on average, this check is efficient.

If we find a match (target in Bob's Set), we return that pair [a, target] as our solution.

Learn more about Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The fairCandySwap algorithm takes two lists of integers as input: aliceSizes and bobSizes. Each list represents the sizes of candy boxes for Alice and Bob, respectively.

The approach starts by calculating the difference in total candy amounts between Alice and Bob and dividing it by 2. The division by 2 comes from rearranging the equation sumA - sumB = 2 * (x - y) into x - y = (sumA - sumB) / 2. This value is stored in the variable diff, signifying the amount of candy that needs to be compensated for in the swap to balance the totals:

1diff = (sum(aliceSizes) - sum(bobSizes)) >> 1

In the code, the right-shift operator >> 1 is used as an efficient way to divide the difference by 2.

Next, a Set called s is created from Bob's list of candy sizes. Sets allow for constant time complexity (O(1)) checks for the existence of an element, which is leveraged later:

1s = set(bobSizes)

The algorithm then iterates through the list of Alice's candy sizes. For each candy size a, it computes the corresponding candy size target that Bob needs to provide:

1for a in aliceSizes:
2    target = a - diff
3    if target in s:
4        return [a, target]

This loop checks whether the calculated target exists in Bob's set of candy sizes (s). If it does, that means there is a pair of candy boxes [a, target] that can be swapped to ensure both Alice and Bob end up with the same total amount of candy. The algorithm then returns this pair as soon as it's found.

In summary, the algorithm follows these steps:

Calculate the difference diff between Alice's and Bob's total candy amounts and divide it by 2.
Create a Set from Bob's candy sizes for efficient lookup.
Iterate through Alice's candy sizes, calculate the corresponding target size for Bob.
Check if target exists in Bob's Set.
Return the first pair [a, target] where target is in Bob's Set.

This approach leverages arithmetic to determine the needed exchange and a Set for efficient lookup, making the solution both straightforward and performant.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Example Walkthrough

Let's assume we have the following candy box sizes for Alice and Bob:

aliceSizes = [1, 2, 5]
bobSizes = [2, 4]

Here's how we would use the solution approach to find the pair of boxes to be exchanged:

Calculate the total candies and the difference diff:

We sum up the candies in Alice's and Bob's boxes:
- sumA = 1 + 2 + 5 = 8
- sumB = 2 + 4 = 6
Therefore, the difference diff = (sumA - sumB) / 2 = (8 - 6) / 2 = 1.
Create a Set of Bob's candy sizes for efficient lookup:

s = set(bobSizes), which gives us s = {2, 4}.
Iterate through Alice's candy sizes to find the corresponding target for Bob:

For a in [1, 2, 5], we calculate target as follows:
- When a = 1, target = 1 - diff = 1 - 1 = 0. Since 0 is not in set s, we continue.
- When a = 2, target = 2 - diff = 2 - 1 = 1. Since 1 is not in set s, we continue.
- When a = 5, target = 5 - diff = 5 - 1 = 4. 4 is in set s.
Return the first successful pair [a, target]:

Since we found 4 (which is target) in Bob's set when Alice's box size was 5, the pair [5, 4] is returned.

So, by utilizing the solution approach, we find that Alice can give Bob a box of 5 candies, and Bob can give Alice a box of 4 candies, and they will both end up with 7 candies total, achieving a fair candy swap.

Solution Implementation

1class Solution:
2    def fairCandySwap(self, alice_sizes: List[int], bob_sizes: List[int]) -> List[int]:
3        # Compute the difference in candy sizes between Alice and Bob, divided by 2
4        # because any swap should compensate for half of the total size difference.
5        size_difference = (sum(alice_sizes) - sum(bob_sizes)) // 2
6      
7        # Create a set of Bob's candy sizes for constant-time look-up
8        bob_sizes_set = set(bob_sizes)
9      
10        # Iterate through Alice's candy sizes to find the fair swap
11        for candy_size_alice in alice_sizes:
12            # Calculate the target size of Bob's candy that would make the swap fair
13            target_size_bob = candy_size_alice - size_difference
14          
15            # Check if Bob has a candy of the target size
16            if target_size_bob in bob_sizes_set:
17                # Return a list containing Alice's candy size and the corresponding
18                # Bob's candy size for a fair swap
19                return [candy_size_alice, target_size_bob]
20
21        # Note: no need for an explicit return statement for no match scenario
22        # because the question implies there is always a valid swap.
23

1class Solution {
2  
3    // Method to find the fair candy swap between Alice and Bob
4    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
5        int sumAlice = 0, sumBob = 0; // Initialize sums of Alice's and Bob's candies
6        Set<Integer> bobCandies = new HashSet<>(); // Create a set to store Bob's candy sizes
7      
8        // Calculate sum of candies for Alice
9        for (int candySize : aliceSizes) {
10            sumAlice += candySize;
11        }
12      
13        // Calculate sum of candies for Bob and populate the set with Bob's candy sizes
14        for (int candySize : bobSizes) {
15            bobCandies.add(candySize);
16            sumBob += candySize;
17        }
18      
19        // Compute the difference to be balanced, divided by 2
20        int balanceDiff = (sumAlice - sumBob) >> 1;
21      
22        // Iterate through Alice's candies to find the fair swap
23        for (int aliceCandySize : aliceSizes) {
24            int targetSize = aliceCandySize - balanceDiff;
25            // Check if Bob has the candy size that would balance the swap
26            if (bobCandies.contains(targetSize)) {
27                // Return the pair that represents the fair swap
28                return new int[]{aliceCandySize, targetSize};
29            }
30        }
31      
32        // If no fair swap is possible, return null
33        return null;
34    }
35}
36

1#include <vector>    // Include necessary library for vector usage
2#include <numeric>   // Include library for accumulate function
3#include <unordered_set> // Include library for unordered_set
4
5class Solution {
6public:
7    // Method to find a fair swap of candies between Alice and Bob
8    vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
9        // Calculate the total sum of candies Alice has.
10        int aliceCandySum = accumulate(aliceSizes.begin(), aliceSizes.end(), 0);
11        // Calculate the total sum of candies Bob has.
12        int bobCandySum = accumulate(bobSizes.begin(), bobSizes.end(), 0);
13      
14        // Calculate the difference between Alice's and Bob's candy sums divided by 2.
15        int sizeDifference = (aliceCandySum - bobCandySum) / 2;
16      
17        // Create a set for Bob's candy sizes for efficient look-up.
18        unordered_set<int> bobSizeSet(bobSizes.begin(), bobSizes.end());
19      
20        // Store the answer in a vector.
21        vector<int> result;
22      
23        // Iterate through Alice's candy sizes to find a matching size in Bob's set.
24        for (int aliceCandy : aliceSizes) {
25            // The target size for Bob that would balance the swap.
26            int targetSize = aliceCandy - sizeDifference;
27          
28            // If the target size is in Bob's set, a fair swap is possible.
29            if (bobSizeSet.count(targetSize)) {
30                result = vector<int>{aliceCandy, targetSize};
31                break; // Found the correct swap, exit the loop.
32            }
33        }
34      
35        return result; // Return the pair representing a fair swap.
36    }
37};
38

1function fairCandySwap(aliceCandySizes: number[], bobCandySizes: number[]): number[] {
2    // Calculate the sum of candies for both Alice and Bob.
3    let sumAlice = aliceCandySizes.reduce((accumulated, current) => accumulated + current, 0);
4    let sumBob = bobCandySizes.reduce((accumulated, current) => accumulated + current, 0);
5
6    // Calculate the difference in candies between Alice and Bob, divided by 2.
7    let halfDiff = (sumAlice - sumBob) >> 1;
8
9    // Create a set from Bob's candy sizes for constant-time lookups.
10    let bobSizesSet = new Set(bobCandySizes);
11
12    // Loop through each of Alice's candy sizes to find a fair swap.
13    for (let aliceCandy of aliceCandySizes) {
14        // Calculate the target size for Bob that would equalize the sum.
15        let targetBobCandy = aliceCandy - halfDiff;
16
17        // Check if the target candy size exists in Bob's collection.
18        if (bobSizesSet.has(targetBobCandy)) {
19            // If found, return the pair of candy sizes for Alice and Bob.
20            return [aliceCandy, targetBobCandy];
21        }
22    }
23  
24    // If no fair swap is found, return an empty array.
25    // (The problem statement assures a solution always exists, so this line is never expected to be reached in practice.)
26    return [];
27}
28

Not Sure What to Study? Take the 2-min Quiz：

What's the relationship between a tree and a graph?

A graph is a special treeA tree is a special graphNo relationshipThey are the same thing

I don’t know

Time and Space Complexity

Time Complexity: The time complexity of the given code is O(A + B), where A is the number of elements in aliceSizes and B is the number of elements in bobSizes. Here's the breakdown: calculating the sum of both arrays takes O(A) and O(B) time respectively; creating the set s of bobSizes takes O(B) time; and the for loop runs for every element in aliceSizes, giving another O(A). Since set look-up is O(1) on average, checking if target is in s does not significantly add to the complexity. Thus, the overall time complexity is the sum of these operations, which simplifies to O(A + B).

Space Complexity: The space complexity of the code is O(B). This is because we create a set s consisting of all elements in bobSizes, which takes up space proportional to the number of elements in bobSizes. No other significant space is used as the rest of the variables use constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

888. Fair Candy Swap

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings