Abstract / Summary

Alice and Bob have candy bags and want to swap one candy each to end up with the same total candies.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Hash Table
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method fairCandySwap that determines a pair of candy bar sizes-one from Alice’s collection and one from Bob’s-that can be exchanged to equalize the total amount of candy each person holds. The algorithm works by first computing the total candy each participant possesses, deriving the required difference, and then searching for a matching pair using a hash-set for constant-time membership checks.

Key Steps

Compute total candy for each participant

a = sum(aliceSizes)
b = sum(bobSizes)
diff = a - b  # may be negative

The sums a and b represent the aggregate sizes of Alice’s and Bob’s candy bars respectively. The variable diff captures the net imbalance; a positive value indicates Alice has more candy, while a negative value indicates Bob has more.

Build a hash set of Bob’s candy sizes

hashed = set(bobSizes)

Creating a set from bobSizes enables O(1) average-time look-ups for any candidate size. This data structure is central to the algorithm’s efficiency because it eliminates the need for nested iteration over both lists.

Iterate over Alice’s candy sizes and locate a matching counterpart

for i in aliceSizes:
    j = i - diff / 2
    if j in hashed:
        return [ i, j ]

During the loop, each size i from Alice’s collection is examined. The expression i - diff / 2 computes the size j that Bob must contribute to achieve balance. If j exists in the pre-computed hash set, the method returns the pair [i, j], satisfying the fairness condition.

Edge Cases Handled

The algorithm gracefully manages scenarios where the total candy difference is an odd number. Because the required exchange size must be an integer, the division diff / 2 yields a floating-point result when diff is odd. In such cases, the computed j will not be an integer present in hashed, and the loop continues without a false positive. Consequently, the method only returns a pair when a valid integer solution exists.

When Alice’s list is empty or Bob’s list is empty, the sum calculations correctly produce zero for the missing side, and the subsequent logic still functions. If no suitable pair exists, the loop terminates without a return, implicitly resulting in None, which aligns with the problem’s guarantee that a solution always exists for valid inputs.

The use of a set for Bob’s sizes also handles duplicate values automatically; the presence check does not depend on the count of a particular size, only on its existence, which matches the requirement that any single bar can be swapped.

Performance Optimizations

The most notable optimization is the conversion of bobSizes into a hash set. This transformation reduces the search for a complementary size from linear time per iteration to constant average time, turning an otherwise quadratic scan into a linear-time solution relative to the combined length of the input lists.

Computing the total sums once at the beginning avoids repeated aggregation during the search phase. Storing the difference diff as a single variable eliminates redundant arithmetic inside the loop, ensuring that each iteration performs only the minimal necessary calculations.

By returning immediately upon finding the first valid pair, the method avoids unnecessary traversal of the remaining elements, which can be significant when the solution appears early in Alice’s list. This early-exit behavior contributes to the overall efficiency of the routine.

Imagine Alice and Bob have two piles of candy, but one pile is heavy and the other is light. They want to swap one piece of candy each so that both piles end up weighing exactly the same.

First, the code adds up all the candies Alice has to see her total weight, and it does the same for Bob. It then calculates the difference between these two totals to figure out how much weight needs to move from one side to the other.

To make the swapping easy, the code puts all of Bob's candy pieces into a special box that lets the computer check for any specific number very quickly. Then, it looks at each piece of candy in Alice's pile one by one. It does a little bit of math to figure out what matching piece Bob would need to give back so that the piles balance out perfectly. If that perfect piece is found inside Bob's collection, the pair of candies is chosen for the swap.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python			TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java			Python	Go		TS
	LeetcodeHelp	C++		Java			Python
	Progiez	C++		Java			Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim								C
	everthis		JS
	fengvyi	C++
	halfrost							Go
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007						Python
	lzl124631x	C++
	ruoru					Rust
	suxrobGM				C#
	varunu28			Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fengvyi	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality