287. Assign Cookies
🔗 LeetCode Problem: 455. Assign Cookies
📊 Difficulty: Easy
🏷️ Topics: Array, Two Pointers, Greedy, Sorting
Problem Statement
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Example 1:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
Constraints:
- 1 <= g.length <= 3 * 10^4
- 0 <= s.length <= 3 * 10^4
- 1 <= g[i], s[j] <= 2^31 - 1
🌟 Understanding the Problem
What are we trying to maximize?
Goal: Maximum number of CONTENT children
Rules:
- Each child gets AT MOST one cookie
- Each cookie used for AT MOST one child
- Child i content if: cookie size >= greed factor
Example:
Children greed: [1, 2, 3]
Cookie sizes: [1, 1]
Child 1 (greed=1): Can be satisfied by cookie size 1 ✓
Child 2 (greed=2): Needs cookie size ≥ 2, only have size 1 ✗
Child 3 (greed=3): Needs cookie size ≥ 3, only have size 1 ✗
Maximum content children: 1
Key Observations:
1. Each child has a MINIMUM requirement (greed factor)
Cookie must be at least this big
2. Larger cookies can satisfy smaller greed
Cookie size 5 can satisfy greed 1, 2, 3, 4, or 5
3. We want to MAXIMIZE count
Not minimize waste, not anything else
Just: how many children can we make happy?
4. Order doesn't matter in input
We can rearrange children and cookies!
5. Greedy intuition:
Give smallest sufficient cookie to each child
Don't waste large cookies on small greed!
The Waste Problem:
BAD strategy: Give any cookie that fits
Example:
Children: [1, 2, 3]
Cookies: [1, 2, 3]
Bad assignment:
Child 1 (greed=1) gets cookie size 3
Child 2 (greed=2) gets cookie size 2
Child 3 (greed=3) gets cookie size 1 ✗ (doesn't fit!)
Result: 2 content children (wasted large cookie!)
Good assignment:
Child 1 (greed=1) gets cookie size 1 ✓
Child 2 (greed=2) gets cookie size 2 ✓
Child 3 (greed=3) gets cookie size 3 ✓
Result: 3 content children!
Lesson: Match efficiently, don't waste!
🌟 The Natural Thinking Process
When you first see this problem:
Question: Maximize number of content children
First Thought: "Try all possible assignments"
- Try every way to assign cookies to children
- Count content children for each
- Return maximum
Is this optimal? NO (exponential combinations!), but it WORKS!
The Evolution:
BRUTE FORCE THINKING:
"Try all possible cookie assignments"
Time: O(2^n × m) - exponential!
Problem: Way too many combinations!
⬇
REALIZATION 1:
"Order doesn't matter!"
"I can sort both arrays!"
"Maybe greedy works..."
⬇
OBSERVATION:
"Give smallest cookie that satisfies each child"
"Start from smallest greed to largest"
"Use smallest sufficient cookie each time"
⬇
OPTIMIZATION: Greedy with Sorting
"Sort both arrays"
"Two pointers: match smallest to smallest"
Time: O(n log n + m log m) - for sorting
⬇
OPTIMAL: Simple greedy matching! ✨
🎯 Approach 1: Brute Force - Try All Assignments ⭐
The First Natural Solution
The Thought Process:
For each child, try assigning each available cookie
Use backtracking:
- Try assigning cookie to child
- Recursively solve for remaining
- Backtrack and try next cookie
- Take maximum across all attempts
Simple conceptually but exponential time!
Visual Tracking - Small Example
Children: g = [1, 2]
Cookies: s = [1, 2]
═══════════════════════════════════════════════════════════════
TRY ALL ASSIGNMENTS
═══════════════════════════════════════════════════════════════
Assignment 1:
Child 0 (greed=1) → Cookie 0 (size=1) ✓
Child 1 (greed=2) → Cookie 1 (size=2) ✓
Content: 2
Assignment 2:
Child 0 (greed=1) → Cookie 1 (size=2) ✓
Child 1 (greed=2) → Cookie 0 (size=1) ✗
Content: 1
Assignment 3:
Child 0 (greed=1) → No cookie
Child 1 (greed=2) → Cookie 0 (size=1) ✗
Content: 0
Assignment 4:
Child 0 (greed=1) → No cookie
Child 1 (greed=2) → Cookie 1 (size=2) ✓
Content: 1
...many more combinations...
Maximum: 2 ✓
Problem: For larger inputs, combinations explode!
Implementation (Conceptual)
/**
* Brute Force - Try all assignments
* Time: O(2^(n+m)) - exponential
* Space: O(n) for recursion
*
* NOT RECOMMENDED - Too slow for constraints!
*/
class Solution {
public int findContentChildren(int[] g, int[] s) {
return backtrack(g, s, 0, new boolean[s.length]);
}
private int backtrack(int[] g, int[] s, int childIdx, boolean[] used) {
// Base case: all children considered
if (childIdx >= g.length) {
return 0;
}
int maxContent = 0;
// Try assigning each unused cookie to current child
for (int i = 0; i < s.length; i++) {
if (!used[i] && s[i] >= g[childIdx]) {
used[i] = true;
int content = 1 + backtrack(g, s, childIdx + 1, used);
maxContent = Math.max(maxContent, content);
used[i] = false; // Backtrack
}
}
// Or skip this child (don't give cookie)
maxContent = Math.max(maxContent, backtrack(g, s, childIdx + 1, used));
return maxContent;
}
}
⏰ Time: O(2^(n+m)) - Exponential
💾 Space: O(n) - Recursion depth
Why This is Inefficient:
Problem: Explores ALL possible assignments!
Example: n=10 children, m=10 cookies
Combinations: ~2^20 = 1,000,000+
For n=30, m=30:
Combinations: ~2^60 = 10^18
Would take years!
Need smarter approach!
💡 The AHA Moment
CRITICAL REALIZATION:
"Why try ALL assignments?"
"If I sort both arrays..."
"Give smallest cookie to smallest greed!"
"Work through both sorted lists!"
Greedy strategy:
Sort children by greed (ascending)
Sort cookies by size (ascending)
For each child (small to large greed):
Find smallest cookie that satisfies
Move to next cookie
This is OPTIMAL!
Why?
- Giving larger cookie to smaller greed is wasteful
- Giving smallest sufficient cookie is always best
- Two pointers can match efficiently
Greedy works! ✨
🎯 Approach 2: Greedy with Sorting (Optimal) ⭐⭐⭐
The Optimal Solution
The Evolution of Thought:
Brute force: Try all assignments
⬇
Observation: "Order doesn't matter, can sort!"
⬇
Greedy insight: "Match smallest to smallest!"
⬇
Implementation: "Two pointers on sorted arrays!"
⬇
Optimal: O(n log n + m log m) for sorting! ✨
Understanding Greedy - Complete Reasoning
The Core Question:
Why does greedy work?
Why is matching smallest-to-smallest optimal?
Answer Through Detailed Reasoning:
PRINCIPLE 1: No Benefit to Waste
═══════════════════════════════════════════════════════════════
Claim: Giving larger cookie than necessary is wasteful
Proof by exchange:
Suppose optimal solution gives:
Small greed gets large cookie
Large greed gets appropriate cookie
We can SWAP:
Small greed gets small cookie (still satisfied)
Large greed gets large cookie (still satisfied)
Result: Same number content, but better utilization
Therefore: No benefit to waste!
Example:
Greed: [1, 3]
Cookies: [2, 4]
Wasteful:
Child 1 (greed=1) → cookie 4 ✓
Child 2 (greed=3) → cookie 2 ✗
Content: 1
Efficient:
Child 1 (greed=1) → cookie 2 ✓
Child 2 (greed=3) → cookie 4 ✓
Content: 2 (better!)
═══════════════════════════════════════════════════════════════
PRINCIPLE 2: Greedy Choice Property
═══════════════════════════════════════════════════════════════
Greedy choice: For smallest greed, use smallest sufficient cookie
Why optimal?
- This cookie can't satisfy larger greed anyway
- If we don't use it for smallest greed, it might go unused
- Using it doesn't prevent satisfying larger greed
Example:
Greed: [1, 5]
Cookies: [2, 6]
Greedy: Give cookie 2 to child 1 (greed=1)
Leaves cookie 6 for child 2 (greed=5) ✓
Content: 2
Alternative: Give cookie 6 to child 1 (greed=1)
Cookie 2 can't satisfy child 2 (greed=5) ✗
Content: 1 (worse!)
═══════════════════════════════════════════════════════════════
PRINCIPLE 3: Optimal Substructure
═══════════════════════════════════════════════════════════════
After making greedy choice for first child:
Remaining problem: Same structure, smaller size
Optimal for remaining children
Proof:
If we optimally solve for remaining children,
And we made greedy choice for first,
Then overall solution is optimal!
This is the hallmark of greedy algorithms! ✓
═══════════════════════════════════════════════════════════════
ALGORITHM
═══════════════════════════════════════════════════════════════
Strategy:
1. Sort greed array (children)
2. Sort size array (cookies)
3. Two pointers: i for children, j for cookies
4. For each child i:
While j < cookies.length:
If cookie[j] >= greed[i]:
Match! Increment both i and j
Increment count
Break
Else:
Cookie too small, try next cookie
Increment j only
5. Return count
Why this works:
- Sorted: ensures we consider smallest first
- Two pointers: efficient single pass
- Greedy: always use smallest sufficient cookie
Time: O(n log n + m log m) for sorting
Space: O(1) if sorting in-place
OPTIMAL! ✨
Visual Tracking - Complete Example
Input: g = [1, 2, 3], s = [1, 1]
═══════════════════════════════════════════════════════════════
STEP 1: Sort Both Arrays
═══════════════════════════════════════════════════════════════
Greed (already sorted): [1, 2, 3]
Cookies (already sorted): [1, 1]
═══════════════════════════════════════════════════════════════
STEP 2: Initialize Pointers
═══════════════════════════════════════════════════════════════
i = 0 (child pointer)
j = 0 (cookie pointer)
count = 0
Children: [1, 2, 3]
↑
i
Cookies: [1, 1]
↑
j
═══════════════════════════════════════════════════════════════
ITERATION 1: Try to satisfy child i=0 (greed=1)
═══════════════════════════════════════════════════════════════
Current child greed: g[0] = 1
Current cookie size: s[0] = 1
Check: s[0] >= g[0]?
1 >= 1? YES ✓
Action: MATCH!
Child 0 gets cookie 0
count = 1
i = 1 (next child)
j = 1 (next cookie)
State after:
count = 1
Children: [1, 2, 3]
↑
i
Cookies: [1, 1]
↑
j
═══════════════════════════════════════════════════════════════
ITERATION 2: Try to satisfy child i=1 (greed=2)
═══════════════════════════════════════════════════════════════
Current child greed: g[1] = 2
Current cookie size: s[1] = 1
Check: s[1] >= g[1]?
1 >= 2? NO ✗
Action: Cookie too small
j = 2 (try next cookie)
i stays 1 (same child)
State after:
count = 1
Children: [1, 2, 3]
↑
i
Cookies: [1, 1]
↑
j (out of bounds!)
═══════════════════════════════════════════════════════════════
TERMINATION
═══════════════════════════════════════════════════════════════
j >= cookies.length (2 >= 2)
No more cookies available
Stop!
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
count = 1
Maximum content children: 1 ✓
Explanation:
Only 1 child can be satisfied
Child with greed=1 gets cookie size 1
Children with greed 2,3 cannot be satisfied (cookies too small)
Another Complete Example - Success Case
Input: g = [1, 2], s = [1, 2, 3]
═══════════════════════════════════════════════════════════════
INITIALIZATION
═══════════════════════════════════════════════════════════════
After sorting:
Greed: [1, 2]
Cookies: [1, 2, 3]
i = 0, j = 0, count = 0
═══════════════════════════════════════════════════════════════
ITERATION 1: Child i=0 (greed=1)
═══════════════════════════════════════════════════════════════
g[0] = 1, s[0] = 1
Check: 1 >= 1? YES ✓
Match:
Child 0 → cookie 0
count = 1
i = 1, j = 1
═══════════════════════════════════════════════════════════════
ITERATION 2: Child i=1 (greed=2)
═══════════════════════════════════════════════════════════════
g[1] = 2, s[1] = 2
Check: 2 >= 2? YES ✓
Match:
Child 1 → cookie 1
count = 2
i = 2, j = 2
═══════════════════════════════════════════════════════════════
TERMINATION
═══════════════════════════════════════════════════════════════
i >= children.length (2 >= 2)
All children considered!
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
count = 2
All children content! ✓
Note: Cookie s[2]=3 unused, but that's okay!
Goal is to maximize content children, not minimize waste.
Implementation with Detailed Code Walkthrough
import java.util.Arrays;
/**
* Greedy with Sorting - Optimal
* Time: O(n log n + m log m)
* Space: O(1) or O(log n) for sorting
*/
class Solution {
public int findContentChildren(int[] g, int[] s) {
// Sort both arrays
Arrays.sort(g); // Sort children by greed (ascending)
Arrays.sort(s); // Sort cookies by size (ascending)
int i = 0; // Pointer for children
int j = 0; // Pointer for cookies
int count = 0; // Number of content children
// Try to satisfy each child
while (i < g.length && j < s.length) {
// Current child needs cookie of size >= g[i]
// Current cookie has size s[j]
if (s[j] >= g[i]) {
// This cookie satisfies this child!
count++;
i++; // Move to next child
j++; // Move to next cookie (this one used)
} else {
// Cookie too small for this child
// Try next cookie (bigger)
j++;
}
}
return count;
}
}
Detailed Code Walkthrough:
Example: g = [1, 2, 3], s = [1, 1]
═══════════════════════════════════════════════════════════════
Code Execution Step-by-Step
═══════════════════════════════════════════════════════════════
Arrays.sort(g): [1, 2, 3]
Arrays.sort(s): [1, 1]
i = 0, j = 0, count = 0
─────────────────────────────────────────────────────────────
Loop iteration 1:
─────────────────────────────────────────────────────────────
Condition: i < g.length && j < s.length
→ 0 < 3 && 0 < 2? YES, enter loop
Code:
if (s[j] >= g[i])
→ if (s[0] >= g[0])
→ if (1 >= 1)? YES
Execute if block:
count++ → count = 1
i++ → i = 1
j++ → j = 1
State:
i=1, j=1, count=1
─────────────────────────────────────────────────────────────
Loop iteration 2:
─────────────────────────────────────────────────────────────
Condition: i < g.length && j < s.length
→ 1 < 3 && 1 < 2? YES, enter loop
Code:
if (s[j] >= g[i])
→ if (s[1] >= g[1])
→ if (1 >= 2)? NO
Execute else block:
j++ → j = 2
State:
i=1, j=2, count=1
─────────────────────────────────────────────────────────────
Loop condition check:
─────────────────────────────────────────────────────────────
Condition: i < g.length && j < s.length
→ 1 < 3 && 2 < 2? NO (j reached end)
Exit loop!
─────────────────────────────────────────────────────────────
Return
─────────────────────────────────────────────────────────────
return count → return 1 ✓
Alternative Implementation - While Loop Style:
/**
* Alternative: Explicit while with nested loop
* Same logic, different style
*/
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int cookieIndex = 0;
// For each child (in order of increasing greed)
for (int i = 0; i < g.length; i++) {
// Find smallest cookie that satisfies this child
while (cookieIndex < s.length) {
if (s[cookieIndex] >= g[i]) {
// Found suitable cookie!
count++;
cookieIndex++; // Use this cookie
break; // Move to next child
}
// This cookie too small, try next
cookieIndex++;
}
// If no more cookies, can't satisfy remaining children
if (cookieIndex >= s.length) {
break;
}
}
return count;
}
}
Code Walkthrough for Alternative:
Example: g = [1, 2], s = [1, 2, 3]
After sorting: same
count = 0, cookieIndex = 0
─────────────────────────────────────────────────────────────
For loop: i = 0
─────────────────────────────────────────────────────────────
Child greed: g[0] = 1
Inner while loop:
cookieIndex = 0 < 3? YES
if (s[0] >= g[0])
→ if (1 >= 1)? YES
count++ → count = 1
cookieIndex++ → cookieIndex = 1
break (exit inner loop)
Check: cookieIndex >= s.length?
1 >= 3? NO, continue
State: count=1, cookieIndex=1
─────────────────────────────────────────────────────────────
For loop: i = 1
─────────────────────────────────────────────────────────────
Child greed: g[1] = 2
Inner while loop:
cookieIndex = 1 < 3? YES
if (s[1] >= g[1])
→ if (2 >= 2)? YES
count++ → count = 2
cookieIndex++ → cookieIndex = 2
break
Check: cookieIndex >= s.length?
2 >= 3? NO, continue
State: count=2, cookieIndex=2
─────────────────────────────────────────────────────────────
For loop: i = 2 (beyond array)
─────────────────────────────────────────────────────────────
Exit for loop (i >= g.length)
return count → return 2 ✓
⏰ Time Complexity:
Sorting:
Sort g: O(n log n)
Sort s: O(m log m)
Total sorting: O(n log n + m log m)
Matching (two pointers):
Each pointer advances at most once per iteration
i advances at most n times
j advances at most m times
Total: O(n + m)
Overall: O(n log n + m log m)
Dominated by sorting! ✓
For n=10,000, m=10,000:
Sorting: ~130,000 ops each
Matching: ~20,000 ops
Total: ~280,000 ops
Very efficient! ✨
💾 Space: O(1) auxiliary (or O(log n) for sorting)
Why This is Optimal:
✓ Greedy choice is optimal (proven above)
✓ Single pass matching (two pointers)
✓ Can't do better than sorting (need order)
✓ Clean and simple implementation
This is the best we can do! ✨
📊 Approach Comparison
┌──────────────────┬─────────────────┬──────────┬─────────────┐
│ Approach │ Time │ Space │ Key Insight │
├──────────────────┼─────────────────┼──────────┼─────────────┤
│ Brute Force │ O(2^(n+m)) │ O(n) │ Try all │
│ Greedy + Sort │ O(n log n + │ O(1) │ Match small │
│ │ m log m) │ │ to small │
└──────────────────┴─────────────────┴──────────┴─────────────┘
Greedy is clearly optimal! ✨
💡 Key Learnings
1. GREEDY WORKS:
✓ Proven by exchange argument
✓ No benefit to waste
✓ Smallest-to-smallest matching optimal
2. SORTING ENABLES GREEDY:
✓ Need order to apply greedy
✓ Two pointers on sorted arrays
✓ Clean single-pass matching
3. WHY GREEDY:
✓ Greedy choice property
✓ Optimal substructure
✓ No need to consider future choices
4. PATTERN:
✓ Appears in: Task Scheduler, Meeting Rooms
✓ Matching/allocation problems
✓ Greedy + sorting common pattern
5. PROOF TECHNIQUES:
✓ Exchange argument (swap doesn't hurt)
✓ Show greedy ≥ optimal
✓ Show greedy doesn't block better solutions
⚠️ Common Mistakes
// Mistake 1: Not sorting
public int findContentChildren(int[] g, int[] s) {
// ❌ Forgot to sort!
int i = 0, j = 0, count = 0;
// ... rest of code
}
// ✓ CORRECT
Arrays.sort(g);
Arrays.sort(s);
// Mistake 2: Wrong comparison
if (s[j] > g[i]) { // ❌ Should be >= not >
count++;
}
// ✓ CORRECT
if (s[j] >= g[i]) { // Equal size works!
count++;
}
// Mistake 3: Incrementing wrong pointer
if (s[j] >= g[i]) {
count++;
j++; // ❌ Forgot to increment i!
}
// ✓ CORRECT
if (s[j] >= g[i]) {
count++;
i++; // Next child
j++; // Next cookie
}
// Mistake 4: Wrong loop condition
while (i < g.length || j < s.length) { // ❌ OR should be AND
}
// ✓ CORRECT
while (i < g.length && j < s.length) { // Need BOTH
}
🎯 Pattern Recognition
Problem Type: Greedy Matching/Allocation
Core Pattern: Sort + Two Pointers
When to Apply:
✓ Maximize/minimize count with constraints
✓ One-to-one assignment/matching
✓ Can sort input without losing info
✓ Greedy choice doesn't block optimal
Recognition Keywords:
- "maximize number"
- "assign"
- "content" / "satisfied"
- "minimum requirement"
- "at most one"
Similar Problems:
- Meeting Rooms (LC 252)
- Non-overlapping Intervals (LC 435)
- Two City Scheduling (LC 1029)
- Task Scheduler (LC 621)
Key Components:
┌────────────────────────────────────────────┐
│ Sort both arrays │
│ Two pointers (one for each array) │
│ Greedy matching (smallest to smallest) │
│ Result: Maximum matches │
└────────────────────────────────────────────┘
When greedy works:
- Optimal substructure
- Greedy choice property
- Exchange argument possible
📝 Quick Revision
🎯 Core: Maximize content children by assigning cookies. Greedy: Sort both arrays. Two pointers. Match smallest greed to smallest sufficient cookie. Don't waste large cookies on small greed!
import java.util.Arrays;
public class Solution {
public int findContentChildren(int[] g, int[] s) {
return sorting(g, s);
}
private int sorting(int[] g, int[] s) {
// step 1: sort both arrays.
Arrays.sort(g);
Arrays.sort(s);
int i = 0;
int j = 0;
int count = 0;
while (i < g.length && j < s.length) {
if (g[i] <= s[j]) {
// step 2: if greedy gets satisfied, move to next
i++; // next child
j++; // next cookie
count++;
} else {
// step 3: if greedy does not satisfy, check next cookie
j++; // next cookie
}
}
return count;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findContentChildren(new int[] { 1, 2, 3 }, new int[] { 1, 1 }));
System.out.println(s.findContentChildren(new int[] { 1, 2 }, new int[] { 1, 2, 3 }));
}
}
🔑 Key: Greedy works! Sort + two pointers. Match small to small. O(n log n + m log m). ✨
Happy practicing! 🎯💪✨
Note: This problem demonstrates classic greedy matching with proof! You learn: (1) WHY greedy works (exchange argument, no benefit to waste), (2) Greedy choice property and optimal substructure, (3) Sort + two pointers pattern, (4) How to prove greedy correctness. The detailed walkthroughs show both success and failure cases with exact pointer movements and state transitions - true mastery through complete reasoning and visualization! 💪✨🏆