Abstract / Summary

Choose children to maximize total happiness from given toys and preferences.

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

Typical patterns to solve this problem:

• Array
• Greedy
• 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 implementation computes the maximum possible sum of happiness values after distributing a limited number of treats to children. Each child’s happiness decreases by one for each treat that has already been given to a previous child, reflecting a “waiting” penalty. The algorithm selects the children with the highest initial happiness, applies the decreasing penalty, and stops when further contributions would become non-positive.

Key Steps

Selecting the top candidates

wait = sorted(happiness, reverse = True)[ : k]

The list of happiness values is sorted in descending order so that the children with the greatest initial happiness are considered first. The slice [:k] extracts at most k elements, ensuring that the subsequent loop never processes more than the allowed number of treats. If k exceeds the length of happiness, the slice simply returns the entire sorted list, gracefully handling that situation.

Accumulating the adjusted happiness

for i, h in enumerate(wait):
    if i >= h:  # early exit
        break
    result += h - i

The loop iterates over the selected candidates, using enumerate to obtain both the position i (the number of previously served children) and the original happiness h. The expression h - i represents the effective happiness after accounting for the waiting penalty. The conditional if i >= h detects the point at which the penalty would erase any remaining contribution; when this condition is true, the loop terminates immediately, avoiding unnecessary work.

Returning the final sum

return result

After processing the viable candidates, the accumulated result is returned as the maximum achievable happiness sum.

Edge Cases Handled

When the input list happiness is empty, the sorting step yields an empty list, the slice produces an empty wait, and the loop body never executes, resulting in a return value of 0. This matches the expectation that no children means no happiness can be contributed.

If k is zero, the slice [:k] produces an empty list regardless of the contents of happiness. Consequently, the loop is skipped and the function returns 0, correctly reflecting that no treats are distributed.

When k is larger than the number of children, the slice returns the entire sorted list. The loop then processes each child, but the early-exit condition ensures that once the waiting penalty outweighs a child’s initial happiness, the remaining children (which would have even lower initial values) are not considered, preventing negative contributions.

For children whose initial happiness is very small (including zero or negative values), the early-exit condition i >= h triggers as soon as the index reaches or exceeds the happiness value. This prevents the algorithm from adding non-positive terms to the sum, effectively ignoring children who cannot contribute positively after waiting.

Performance Optimizations

The algorithm performs a single sort operation on the input list, which is the dominant cost but unavoidable for ordering the candidates. By immediately slicing the sorted list to the first k elements, the subsequent loop works on a reduced collection, limiting the number of iterations to at most k. This is especially beneficial when k is much smaller than the total number of children.

The early-exit check inside the loop provides a second layer of optimization. As soon as the waiting penalty makes further contributions non-positive, the loop terminates, potentially skipping many remaining iterations. In cases where the happiness values drop quickly, this can dramatically reduce the number of arithmetic operations performed.

Overall, the combination of sorting once, limiting the processed subset, and breaking out early when contributions become irrelevant yields an efficient solution that scales well with both the size of the input list and the value of k.

Imagine a big box filled with lots of toys, and each toy has a number on it that represents how much joy it brings. Some toys are very exciting with big numbers, while others are a little bit quieter. You want to pick out some toys, but there is a rule that says every time you pick one, all the other ones left in the box get just a tiny bit less exciting because they had to wait a turn.

The code starts by taking all those toy numbers and putting them in a line from the biggest one to the smallest one. This helps make sure the most exciting toys are picked first. Then, it only takes the top few toys that are allowed to be chosen.

Next, it visits each of those toys one by one. For the first toy, it gets to keep all its happiness. For the second toy, it has to lose a tiny bit of joy because it waited for the first one. For the third toy, it loses a little bit more, and so on. If a toy has waited so long that its happiness would drop down to zero, the code stops looking because there is no more joy left to gather. It keeps track of all the happiness points collected along the way to see how much total joy was achieved.

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		Java	C++	Python				TS
	WalkCCC		Java	C++	Python
	leetcode.ca		Java	C++	Python	C#	Go	Rust	TS
	Progiez		Java	C++	Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	shreymehul					C#
	trung-hn				Python
	varunu28		Java
	withaarzoo			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
shreymehul	C#
trung-hn	Python
varunu28	Java
withaarzoo	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