Introduction

Assign Cookies is one of the easiest Greedy Algorithm problems.

You are given:

  • g[i] = greed factor of child
  • s[i] = size of cookie

Goal:

Maximize the number of satisfied children.

Condition:

cookie size >= greed factor

Example

Input

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

Output

 1

Explanation

Child 1 gets cookie 1Satisfied = 1
Child 2 and Child 3 cannot be satisfied.

Key Observation

Give the smallest possible cookie to the least greedy child.

Sorting helps make optimal assignments.

Algorithm

  1. Sort greed array.
  2. Sort cookie array.
  3. Use two pointers.
  4. If cookie satisfies child:
    • Assign cookie.
    • Move both pointers.
  5. Otherwise:
    • Try larger cookie.
  6. Count satisfied children.

Dry Run

Input

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

Sort Arrays

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

First Cookie

 1 satisfies child 1

Satisfied

 1

Second Cookie

1 cannot satisfy child 2

Answer

1

Approach : Greedy

Always assign the smallest available cookie that can satisfy the current child.

This prevents wasting larger cookies on smaller greed factors.

Practice

Complexity Analysis

Time Complexity: O(n log n + m log m)Explanation: Both greed and cookie arrays are sorted before processing.

Space Complexity: O(1)
Explanation: Only a few extra variables are used apart from sorting.

Why This Problem is Important

This problem introduces the Greedy strategy of making locally optimal choices to achieve a globally optimal solution.

Common Beginner Mistakes

  • Not sorting arrays.
  • Using larger cookies first.
  • Incorrect pointer movement.
  • Trying all combinations unnecessarily.

Interview Tip

Always mention:

Assign the smallest cookie that can satisfy the current child to avoid wasting larger cookies.

Related Questions

  • Lemonade Change
  • Jump Game
  • Gas Station
  • Partition Labels
  • Best Time to Buy and Sell Stock II

Final Takeaway

Assign Cookies is a classic beginner Greedy problem. The key idea is to sort both arrays and always satisfy the least greedy child first using the smallest suitable cookie. This leads to the maximum number of satisfied children.