Abstract / Summary

Given sorted arrays of candy piles and child preferences, find the maximum total candies that can be given to k children so each gets at least their minimum preference.

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 50% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search

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 implementation defines a class Solution with a single method maximumCandies. The method receives a list of integers candies, each representing the number of candies in a bag, and an integer k denoting the number of children. The goal is to compute the largest integer size such that each child can receive a pile of exactly that many candies, obtained by splitting the original bags without mixing candies from different bags. The algorithm employs a binary-search-style approach built on Python’s bisect_left function, combined with a helper predicate that determines whether a candidate pile size is infeasible.

Core Logic

Predicate Definition

def impossible(size):
    return sum(c // size for c in candies) < k

The nested function impossible evaluates a candidate pile size size. For each bag c it computes how many whole piles of that size can be produced (c // size). The sum across all bags yields the total number of piles achievable with the current size. If this total is less than the required number of children k, the predicate returns True, indicating that the size is too large to satisfy all children.

Early Termination Check

total = sum(candies)
if total < k:
    return 0

Before invoking the binary search, the method aggregates the total number of candies across all bags. If the aggregate is smaller than the number of children, even a pile size of one candy cannot be distributed to every child, so the function returns 0 immediately. This guard eliminates unnecessary work for clearly impossible scenarios.

Binary Search via bisect_left

return bisect_left(range(1, total + 1), True, key=impossible)

The final step uses bisect_left to locate the smallest index in the virtual sequence range(1, total + 1) for which the predicate impossible evaluates to True. Because the predicate is monotonic-once a size becomes impossible, all larger sizes remain impossible-the leftmost true position corresponds to the first size that cannot satisfy the children. The algorithm therefore returns the predecessor of that position, which is the maximum feasible pile size. The comment in the source clarifies that the off-by-one adjustment inherent in the bisect_left call cancels out the earlier “avoid size 0” concern.

Edge Cases Handled

The code explicitly addresses the situation where the total number of candies is insufficient for a one-candy per child distribution. By checking total < k and returning 0, it avoids a division-by-zero error that would arise if the binary search attempted to evaluate size = 0.

The predicate impossible also gracefully handles bag values that are smaller than the candidate size. In such cases c // size yields 0, contributing nothing to the pile count, which correctly reflects that those bags cannot produce a pile of the current size.

Because bisect_left operates over a range object, the search space is bounded by 1 and total, guaranteeing that the candidate size never exceeds the total candy count, thereby preventing overflow or unnecessary iterations.

Performance Optimizations

The implementation leverages a generator expression inside sum(c // size for c in candies). This construct computes the division results lazily, avoiding the creation of an intermediate list and reducing memory pressure, especially when the input list is large.

The early return based on the aggregate candy count eliminates the binary search entirely for trivially impossible inputs, saving the cost of multiple predicate evaluations.

Using bisect_left with a custom key function provides a built-in binary search that runs in logarithmic time with respect to the size of the search interval. The search interval is defined by range(1, total + 1), but because bisect_left works with the range object directly, it does not materialize the full list of candidate sizes. This approach yields a fast convergence to the answer without the overhead of manual loop constructs.

Overall, the combination of lazy evaluation, early exit, and a library-provided binary search results in a solution that scales efficiently with both the number of bags and the magnitude of candy counts.

Imagine there are many bags of candy, and each bag has a different number of sweets inside. There is a big group of friends waiting to get their fair share, and every child needs to receive a pile of candy that is exactly the same size as everyone else's pile. Even better, every child must get a full pile, and any extra candy left over in the bags just gets put away.

The goal is to find the biggest possible pile size that lets every single friend get their own pile. To figure this out, the code acts like a detective playing a guessing game. It tries different pile sizes to see if they work. If it picks a size that makes it impossible for everyone to have a pile, it knows the piles are too big and moves to a smaller range. If the size works well, it tries to see if it can make the piles even bigger.

Instead of checking every single number one by one, which would take a very long time, it uses a smart shortcut. It looks at the middle of all the possible numbers, checks if that size is okay, and then cuts the list of numbers in half to throw away the ones that do not fit. By doing this over and over, it zooms in on the largest possible number that works for all the friends. Once it narrows everything down to that one perfect number, it knows exactly how much candy to put in each pile for the group.

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

Time: loglinear
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++			Python	Java			TS
	WalkCCC	C++			Python	Java
	leetcode.ca	C++			Python	Java		Go	TS
	Progiez	C++			Python	Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	Shamik07						Dart
	shreymehul			C#
	suxrobGM			C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
shreymehul	C#
suxrobGM	C#
wisdompeak	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