Assign Cookies | Greedy Algorithm

leetcode.com

Problem Statement

You are given:

• g[i] = greed factor of the ith child
• s[j] = size of the jth cookie

A child is satisfied if:

cookie size >= greed factor

Each cookie can be assigned to only one child.

Return the maximum number of satisfied children.

---

Brute Force Intuition

For every child, try all available cookies and assign the smallest valid cookie that can satisfy the child.

To avoid reusing cookies, we need extra tracking.

This works but becomes inefficient because every child may scan all cookies.

Complexity

• Time Complexity: O(N × M)
• Space Complexity: O(M)

Brute Force Snippet

boolean[] used = new boolean[s.length];

int count = 0;

for (int child : g) {

    for (int j = 0; j < s.length; j++) {

        if (!used[j] && s[j] >= child) {
            used[j] = true;
            count++;
            break;
        }
    }
}

---

Moving Towards the Optimal Approach

Suppose we have:

Greed : [1,2,3]
Cookies : [1,2]

Giving a larger cookie to a less greedy child can waste resources.

Instead:

Always satisfy the least greedy child using the smallest possible cookie.

This leaves larger cookies available for greedier children.

---

Greedy Pattern Recognition

Whenever you see:

• Matching two arrays
• Maximize number of successful assignments
• Smallest resource satisfying smallest requirement

Think:

Sort Both Arrays + Two Pointers

---

Optimal Approach

Algorithm

1. Sort greed array.
2. Sort cookie array.
3. Use two pointers:
   • One for children.
   • One for cookies.
4. If cookie can satisfy child:
   • Assign it.
   • Move both pointers.
5. Otherwise:
   • Try a larger cookie.

---

Optimal Java Solution

import java.util.*;

class Solution {

    public int findContentChildren(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);

        int child = 0;
        int cookie = 0;

        while (child < g.length && cookie < s.length) {

            if (s[cookie] >= g[child]) {
                child++;
                cookie++;
            } else {
                cookie++;
            }
        }

        return child;
    }
}

---

Dry Run

Input

g = [1, 2, 3]
s = [1, 1]

After Sorting

g = [1,2,3]
s = [1,1]

Assignment

Child 1 ← Cookie 1 ✓

Child 2 ← Cookie 1 ✗
No larger cookies left

Result

Satisfied Children = 1

---

Another Example

Input

g = [1,2]
s = [1,2,3]

Assignment

1 ← 1 ✓

2 ← 2 ✓

Result

Satisfied Children = 2

---

Why Greedy Works?

Consider:

Child Greed = 1
Cookie = 5

Using a large cookie here may prevent satisfying a greedier child later.

Instead:

Give the smallest possible cookie that satisfies the current smallest greed.

This preserves larger cookies for future children.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N log N + M log M)
Space Complexity	O(1)

Sorting dominates the runtime.

---

Interview One-Liner

Sort both arrays and use two pointers. Assign the smallest cookie capable of satisfying the least greedy child to maximize the total number of satisfied children.

---

Pattern Learned

Requirement Array
+
Resource Array
+
Maximum Assignments

=> Sort Both Arrays + Two Pointers

Similar Problems

• Assign Cookies
• Boats to Save People
• Minimum Number of Arrows to Burst Balloons
• Matching Jobs to Workers
• Interval Scheduling Variations