EasyGreedy Techniques

Assign Cookies

Explanation & Solution

Description

Given two arrays g and s, where g[i] is the greed factor of the ith child and s[j] is the size of the jth cookie, return the maximum number of content children.

A child i is content if there exists a cookie j such that s[j] >= g[i] (the cookie size is at least as large as the child's greed factor). Each child can receive at most one cookie, and each cookie can be assigned to at most one child.

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

Output: 1

Explanation: Only one child can be content. The child with greed factor 1 gets a cookie of size 1. The other two children cannot be satisfied.

Constraints

1 <= g.length <= 3 * 10⁴
0 <= s.length <= 3 * 10⁴
1 <= g[i], s[j] <= 2³¹ - 1

Approach

Greedy Techniques pattern

1. Sort Both Arrays

Sort the greed factors array g in ascending order
Sort the cookie sizes array s in ascending order
Sorting lets us greedily assign the smallest sufficient cookie to the least greedy child first

2. Initialize Two Pointers

Set childIndex = 0 to track the current child (least greedy first)
Set cookieIndex = 0 to track the current cookie (smallest first)

3. Iterate Through Both Arrays

While there are still children and cookies to consider, compare the current cookie size with the current child's greed factor
If s[cookieIndex] >= g[childIndex], the cookie satisfies the child — advance childIndex to move to the next child
Always advance cookieIndex — the cookie is either used or too small for the current child (and therefore too small for all remaining children)

4. Return the Count

childIndex represents the number of children who were assigned a cookie
Return childIndex as the answer

Key Insight

The greedy strategy works because assigning the smallest sufficient cookie to each child in order of greed never wastes a larger cookie on a child who could have been satisfied with a smaller one. If a cookie is too small for the least greedy remaining child, it cannot satisfy any remaining child, so we skip it.

Time

O(n log n)dominated by sorting both arrays

Space

O(1)only pointer variables are used (ignoring sort space)

Solution Code

Candy

Lemonade Change