Assign Cookies

TIP103 Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 15-20 mins
• 🛠️ Topics: Greedy Algorithms, Sorting, Two Pointers

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: When does a cookie satisfy a child?

  • A: A cookie of size s[j] satisfies child i only if s[j] >= g[i], where g[i] is the child's greed factor (the smallest cookie size that will satisfy them).

• Q: Can a child receive more than one cookie, or a cookie be shared between children?

  • A: No. Every child gets at most one cookie, and each cookie can be given to at most one child.

• Q: What are we maximizing?

  • A: The number of satisfied (content) children, not the amount of cookie handed out. Leftover cookies are fine.

HAPPY CASE
Input: g = [1, 2, 3], s = [1, 1]
Output: 1
Explanation: Both cookies have size 1, so only the child with greed factor 1 can be satisfied. The children with greed factors 2 and 3 go without.

Input: g = [1, 2], s = [1, 2, 3]
Output: 2
Explanation: There are enough cookies of sufficient size to satisfy both children (e.g., give the size-1 cookie to the first child and the size-2 cookie to the second). One cookie is left over.

EDGE CASE
Input: g = [2, 3], s = []
Output: 0
Explanation: There are no cookies, so no child can be satisfied.

Input: g = [10, 9, 8], s = [1, 1, 1]
Output: 0
Explanation: Every cookie is smaller than every greed factor, so no assignment satisfies anyone.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Assignment/Matching Problems, we can consider the following approaches:

• Greedy: Satisfy the least greedy child first, using the smallest cookie that works. Giving a small cookie to an easily-satisfied child preserves the larger cookies for greedier children, so a locally optimal choice is globally optimal.
• Sorting + Two Pointers: Sorting both lists lets one pointer walk the children and another walk the cookies in a single pass, which is the standard way to implement this greedy matching.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Sort both the greed factors and the cookie sizes in ascending order. Walk through the cookies from smallest to largest, always trying to satisfy the least greedy unsatisfied child. If the current cookie is big enough, that child is content and we advance to the next child; either way the cookie is consumed. The child pointer ends up equal to the number of satisfied children.

1) Sort `g` (greed factors) and `s` (cookie sizes) in ascending order.
2) Initialize two pointers: `child = 0` and `cookie = 0`.
3) While both pointers are in bounds:
   a) If `s[cookie] >= g[child]`, the cookie satisfies the child: increment `child`.
   b) Increment `cookie` regardless (the cookie is either used or too small for everyone remaining).
4) Return `child`, the count of satisfied children.

⚠️ Common Mistakes

• Forgetting to sort one (or both) of the lists, which breaks the greedy argument entirely.
• Advancing the child pointer when the cookie is too small, instead of only advancing the cookie pointer.
• Trying to give the largest cookie to the greediest child first without handling leftovers carefully — it works, but the smallest-first version is easier to get right.
• Assuming every child must be satisfied and returning True/False instead of the maximum count.

4: I-mplement

Implement the code to solve the algorithm.

def find_content_children(g, s):
    # Sort greed factors and cookie sizes in ascending order
    g.sort()
    s.sort()

    child = 0   # Pointer to the least greedy unsatisfied child
    cookie = 0  # Pointer to the smallest unused cookie

    # Try to satisfy each child with the smallest cookie that works
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1   # Child is content; move to the next child
        cookie += 1      # Cookie is consumed either way

    return child  # Number of satisfied children

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

  • After sorting: g = [1, 2, 3], s = [1, 1].
  • Cookie 1 (size 1) vs child with greed 1: 1 >= 1, child satisfied → child = 1, cookie = 1.
  • Cookie 2 (size 1) vs child with greed 2: 1 < 2, cookie discarded → cookie = 2.
  • Cookies exhausted.
  • Output: 1

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

  • After sorting: g = [1, 2], s = [1, 2, 3].
  • Cookie 1 (size 1) vs child with greed 1: 1 >= 1 → child = 1, cookie = 1.
  • Cookie 2 (size 2) vs child with greed 2: 2 >= 2 → child = 2, cookie = 2.
  • All children satisfied; the size-3 cookie is left over.
  • Output: 2

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

  • The while loop never runs because there are no cookies.
  • Output: 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of children (length of g) and M is the number of cookies (length of s).

• Time Complexity: O(N log N + M log M) to sort both lists; the two-pointer pass afterward is only O(N + M).
• Space Complexity: O(1) extra space beyond the input, since we sort in place and use only two pointers. (If the sort's internal space is counted, Python's Timsort uses up to O(N + M).)