← Back to Index

📚 Assign Cookies – Java Cheat Sheet

📌 What Is It?

The Assign Cookies problem involves distributing cookies to children such that the maximum number of children are satisfied. Each child has a greed factor, and each cookie has a size. A child is satisfied if the size of the cookie is greater than or equal to their greed factor.

🧱 Pattern Template

Greedy Algorithm

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g); // Sort greed factors
        Arrays.sort(s); // Sort cookie sizes
        int child = 0, cookie = 0;

        while (child < g.length && cookie < s.length) {
            if (s[cookie] >= g[child]) {
                child++; // Satisfy this child
            }
            cookie++; // Move to the next cookie
        }

        return child; // Number of satisfied children
    }
}

▶️ View Animation

📊 Time Complexity

• Sorting: O(M log M + N log N), where M is the number of children and N is the number of cookies.
• Greedy Selection: O(min(M, N)), for iterating through the arrays.
• Total Complexity: O(M log M + N log N).

✅ Use Cases

• Maximizing resource allocation efficiency.
• Solving problems involving matching or pairing with constraints.

📘 Common LeetCode Problems

• 455. Assign Cookies [Easy] Greedy

🧪 Example

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

Explanation:
- Only 1 child can be satisfied with the given cookies.

💡 Pro Tips

• Sort both arrays to efficiently match the smallest cookie with the least greedy child.
• Use a two-pointer approach to iterate through the children and cookies.
• Stop early if all children are satisfied or all cookies are used.