Abstract / Summary

Given children with different cookie size needs and available cookies of certain sizes, decide who gets a cookie.

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 55% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Sorting
• Two Pointers

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 solves the classic “assign cookies” problem: given a list of children’s greed factors (g) and a list of cookie sizes (s), it determines the maximum number of children that can be satisfied by giving each child at most one cookie whose size meets or exceeds the child’s greed. The algorithm follows a greedy strategy that first orders both input arrays and then walks through them with two pointers, counting successful assignments.

Key Steps

Sorting the input arrays

g.sort()
s.sort()

Both the greed factors and the cookie sizes are sorted in non-decreasing order. Sorting enables a linear scan that always matches the smallest remaining greedy child with the smallest cookie that can satisfy it. This ordering eliminates the need for nested searches and ensures that larger cookies are reserved for children with larger greed factors.

Initializing counters

result = 0
cookie = 0

result tracks the number of satisfied children, while cookie serves as an index into the sorted cookie list. The index starts at the first cookie and moves forward only when a cookie is examined or assigned.

Iterating over each child

for greed in g:
    while cookie < len(s) and greed > s[cookie]:
        cookie += 1
    if cookie < len(s):
        result += 1
    cookie += 1

The outer loop processes each child in order of increasing greed. Inside the loop, a while loop advances the cookie pointer past any cookies that are too small for the current child (greed > s[cookie]). When the loop exits, either a suitable cookie has been found or the pointer has reached the end of the cookie list.

If a suitable cookie exists (cookie < len(s)), the child is counted as satisfied (result += 1). Regardless of whether a match was made, the pointer is incremented (cookie += 1) to move past the cookie that was just considered, guaranteeing that each cookie is used at most once.

Returning the final count

return result

After all children have been processed, the method returns the total number of children that received an appropriate cookie.

Edge Cases Handled

When the list of children is empty, the outer for loop does not execute, and the method returns 0, correctly indicating that no children can be satisfied.

If the cookie list is empty, the while condition cookie < len(s) fails immediately, the if check also fails, and the pointer is still incremented. The loop continues without ever increasing result, ultimately returning 0.

When all children have greed factors larger than any available cookie, the inner while loop advances the cookie pointer to the end of the cookie list for each child. The subsequent if condition never succeeds, and the algorithm correctly reports that no child can be satisfied.

Conversely, when there are more cookies than children, the algorithm stops after processing all children, leaving any remaining cookies unused. The pointer may advance beyond the last used cookie, but because the loop terminates, no out-of-range access occurs.

Performance Optimizations

The primary optimization is the use of a two-pointer technique after sorting. By moving the cookie pointer forward only when necessary, each element of both arrays is examined at most once after sorting. This eliminates redundant comparisons that a naïve nested-loop approach would incur.

Sorting is performed in-place, avoiding additional memory allocation for copies of the input lists. The subsequent linear scan operates with constant extra space, using only a few integer variables.

The placement of cookie += 1 after the if block ensures that the pointer always moves forward, preventing the algorithm from revisiting the same cookie in later iterations. This subtle ordering contributes to the overall linear pass after sorting.

Overall, the combination of in-place sorting and a single forward scan yields an efficient solution that scales well with the size of the input arrays.

Imagine there is a big group of hungry friends and a big pile of yummy cookies. Some friends are very hungry and need big cookies to be happy, while other friends only need a tiny nibble to be full.

The first thing this code does is line everyone up by how hungry they are, starting with the friend who is the least hungry and ending with the friend who is the hungriest. It also lines all the cookies up from the smallest one to the biggest one.

Next, it looks at the friend who is the least hungry and tries to find a cookie that is at least as big as what they need. If the current cookie is too small, it moves to the next cookie in the pile until it finds one that is big enough.

Whenever a friend gets a cookie that is big enough to satisfy their hunger, the code counts that as a happy friend. It then keeps moving through the line to see how many more friends can be made happy with the remaining cookies. It continues this process until it has checked all the friends or run out of cookies to give out.

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		JS	Go				TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	everthis					JS
	fartem								Ruby
	halfrost						Go
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	muhammadfarhankt						Go
	pruthvikp		Python
	ruoru							Rust
	shreymehul				C#
	suxrobGM				C#
	varunu28			Java
	vthwang			Java
	yuanliu666									Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
muhammadfarhankt	Go
pruthvikp	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
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