Assign Cookies | Leetcode 455 | Optimal Greedy Solution

When preparing for coding interviews, one of the common patterns you’ll come across is the Greedy Algorithm. A great example of this is the Assign Cookies problem on Leetcode.

In this blog, we’ll carefully break down the problem, understand the intuition behind solving it, and then look at the optimal Python solution with clear explanations.

Here’s the [Problem Link] to begin with.

Problem Statement – What Does the Problem Say?

You are given:

• An array g, where each element g[i] represents the greed factor of a child (the minimum size of a cookie they need to be content).
• An array s, where each element s[j] represents the size of a cookie.

Your task is to assign cookies to children in such a way that:

• Each child gets at most one cookie.
• A child is content if the cookie’s size is greater than or equal to their greed factor.
• You want to maximize the number of content children.

Example 1:

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: 
You have 3 children with greed factors [1,2,3] and 2 cookies of sizes [1,1].
- You can only make the child with greed 1 content.
So, the answer is 1.

Example 2:

Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation:
You have 2 children with greed factors [1,2] and 3 cookies [1,2,3].
- Assign cookie of size 1 to child with greed 1.
- Assign cookie of size 2 to child with greed 2.
Both children are satisfied → answer is 2.

So the challenge is: How do we maximize the number of content children using the available cookies?

Intuition and Approach (Optimal – Greedy)

The key idea here is:

• A smaller cookie should be given to the least greedy child (the one with the smallest greed factor).
• If we waste a big cookie on a child who only needs a small one, we might not have enough cookies left for greedier children.

Steps to Solve:

1. Sort both arraysg and s in ascending order.
   • This ensures we can always try to satisfy the least greedy child first.
2. Use two pointers:
   • One (left) for iterating over children.
   • One (right) for iterating over cookies.
3. Compare the current child’s greed g[left] with the current cookie size s[right].
   • If s[right] >= g[left], it means this cookie can satisfy the child → assign the cookie, move both pointers forward.
   • Otherwise, move the cookie pointer right forward to try the next (larger) cookie.
4. Continue until either all children are satisfied or all cookies are used.

This greedy method ensures that every child who can be satisfied gets the smallest possible cookie available, leaving bigger cookies for greedier children.

Code Implementation

Here’s the Python code provided for the optimal greedy solution (with added comments for clarity):

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        n = len(g)
        m = len(s)
        
        # Sort greed factors and cookie sizes
        g.sort()
        s.sort()
        
        left = 0   # Pointer for children
        right = 0  # Pointer for cookies
        count = 0  # Number of satisfied children
        
        # Assign cookies greedily
        while left < n and right < m:
            if g[left] <= s[right]:   # If cookie satisfies the child's greed
                count += 1            # Child is content
                left += 1             # Move to next child
            right += 1                # Move to next cookie
        
        return count

Code Explanation

• First, we sort the children by their greed and cookies by size.
• Then we start assigning cookies one by one:
  • If the current cookie is large enough for the current child → assign it and move to the next child.
  • If not, try the next cookie.
• The count variable keeps track of how many children have been made content.
• The loop continues until either all children are checked or all cookies are used.

This way, every child gets the smallest sufficient cookie, maximizing the total number of content children.

Time and Space Complexity

• Time Complexity:
  • Sorting children: O(n log n)
  • Sorting cookies: O(m log m)
  • Two-pointer assignment loop: O(n + m)
  • Overall: O(n log n + m log m)
• Space Complexity:
  • Sorting is done in-place, and we use only a few extra variables.
  • O(1) additional space.

In simpler terms: The solution is efficient because even though we sort both lists, the rest of the process only requires one pass.

Conclusion

The Assign Cookies problem is a classic example of a Greedy Algorithm where:

• We always assign the smallest available cookie that can satisfy a child.
• Sorting helps us efficiently match cookies with children.

This approach ensures we maximize the number of happy children in O(n log n + m log m) time, which is optimal for this problem.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.