LeetCode 455: Assign Cookies Solution in Python – A Step-by-Step Guide
Imagine you’re a baker at a cookie party with a tray of cookies—say, sizes [1, 2, 3]—and a line of kids with different cookie cravings, like [1, 2, 10]. Each kid needs a cookie at least as big as their greed factor to be happy, and each cookie can only go to one kid. How many kids can you satisfy? Here, it’s 2: give size 1 to greed 1, size 2 to greed 2, but size 3 won’t cut it for greed 10. That’s the tasty challenge of LeetCode 455: Assign Cookies, an easy-level problem that’s a sweet introduction to greedy algorithms. Using Python, we’ll solve it two ways: the Best Solution, a greedy approach with sorting that’s fast and intuitive, and an Alternative Solution, a brute force method that’s simpler but less efficient. With examples, code breakdowns, and a friendly tone, this guide will help you hand out those cookies—whether you’re new to coding or baking up your skills. Let’s pass out the treats and dive in!
Best Solution: Greedy Approach with Sorting
Why This Is the Best Solution
The greedy approach with sorting is the top pick because it’s O(n log n) time and O(1) space (excluding sorting space), efficiently maximizing satisfied children by pairing smallest greed factors with smallest sufficient cookies. It sorts both arrays and assigns cookies in order, ensuring optimal use without wasting large cookies on small needs. It’s like handing out just-big-enough treats from smallest to largest appetite—intuitive and effective!
How It Works
Here’s the strategy:
- Step 1: Sort g (greed factors) and s (cookie sizes) in ascending order.
- Step 2: Use two pointers:
- i for kids, j for cookies.
- If s[j] ≥ g[i], assign cookie, increment both.
- If s[j] < g[i], skip cookie, increment j.
- Step 3: Return count of satisfied kids.
- Why It Works:
- Sorting ensures smallest cookies go to smallest greed first.
- Greedy choice maximizes assignments without backtracking.
Step-by-Step Example
Example: g = [1,2,3], s = [1,1]
- Sort:
- g = [1,2,3].
- s = [1,1].
- Assign:
- i=0, j=0: g[0]=1, s[0]=1, 1 ≥ 1, count=1, i=1, j=1.
- i=1, j=1: g[1]=2, s[1]=1, 1 < 2, j=2 (out of cookies).
- Result: 2 kids satisfied.
Example: g = [10,9,8,7], s = [5,6,7,8]
- Sort:
- g = [7,8,9,10].
- s = [5,6,7,8].
- Assign:
- i=0, j=0: 5 < 7, j=1.
- i=0, j=1: 6 < 7, j=2.
- i=0, j=2: 7 ≥ 7, count=1, i=1, j=3.
- i=1, j=3: 8 ≥ 8, count=2, i=2, j=4 (out).
- Result: 2.
Code with Detailed Line-by-Line Explanation
Here’s the Python code, broken down clearly:
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# Step 1: Sort both arrays
g.sort() # Greed factors
s.sort() # Cookie sizes
# Step 2: Assign cookies greedily
count = 0
i = 0 # Index for kids
j = 0 # Index for cookies
while i < len(g) and j < len(s):
if s[j] >= g[i]:
# Cookie satisfies kid
count += 1
i += 1
j += 1
else:
# Cookie too small, try next
j += 1
return count
- Line 4-5: Sort g and s (e.g., [1,2,3], [1,1]).
- Line 8-10: Initialize count and pointers.
- Line 12-18: Loop:
- If s[j] ≥ g[i], assign, increment both.
- If s[j] < g[i], skip cookie, increment j.
- Line 20: Return satisfied kids.
- Time Complexity: O(n log n)—sorting dominates.
- Space Complexity: O(1)—in-place sorting.
It’s like a cookie-matching assembly line!
Alternative Solution: Brute Force with Iteration
Why an Alternative Approach?
The brute force method iterates through cookies for each child—O(n * m) time, O(1) space—assigning the first sufficient cookie and marking it used. It’s less efficient but straightforward, like handing out cookies one-by-one without pre-planning. Good for small inputs or building intuition!
How It Works
- Step 1: For each child in g, scan s for a cookie ≥ greed.
- Step 2: Use the cookie, mark it (e.g., set to -1), increment count.
- Step 3: Return total satisfied kids.
Step-by-Step Example
Example: g = [1,2,3], s = [1,1]
- Child 1 (1):
- s[0]=1 ≥ 1, use it, s = [-1,1], count=1.
- Child 2 (2):
- s[1]=1 < 2, no match, count=1.
- Child 3 (3):
- No valid cookies, count=1.
- Fix: Greedy picks better, but brute gets 2 with smallest first.
- Result: 2 (if optimized).
Code for Brute Force
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
count = 0
used = [False] * len(s)
# For each child, find a cookie
for greed in g:
for j in range(len(s)):
if not used[j] and s[j] >= greed:
used[j] = True
count += 1
break
return count
- Line 4: Track used cookies.
- Line 7-11: For each greed, find first unused cookie ≥ greed.
- Time Complexity: O(n * m)—nested loops.
- Space Complexity: O(m)—used array.
It’s a cookie handout free-for-all!
Comparing the Two Solutions
- Greedy with Sorting (Best):
- Pros: O(n log n), optimal, scalable.
- Cons: Requires sorting.
- Brute Force (Alternative):
- Pros: O(n * m), simple, no sort.
- Cons: Slower, less efficient.
Greedy wins for speed.
Edge Cases and More Examples
- Input: g=[], s=[1,2] → 0.
- Input: g=[1], s=[] → 0.
- Input: g=[1,1], s=[1] → 1.
Greedy handles all perfectly.
Complexity Recap
- Greedy: Time O(n log n), Space O(1).
- Brute Force: Time O(n * m), Space O(m).
Greedy’s the champ.
Key Takeaways
- Greedy: Sort and match smartly.
- Brute Force: Try every fit.
- Python Tip: Greedy simplifies—see [Python Basics](/python/basics).