Obsidian Notes

Assign Cookies

4 min read

Description

Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example 1:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:
Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

Constraints:

  • 1 <= g.length <= 3 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= g[i], s[j] <= 231 - 1

Note: This question is the same as 2410: Maximum Matching of Players With Trainers.

Approach - 2 pointer

  • sort and just check the only condition given in the problem and increment
  • Time & Space Complexity
    Time complexity: O(nlog⁡n+mlog⁡m)
    Space complexity: O(1) or O(n+m) depending on the sorting algorithm.
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int l = 0;
        for (int r = 0 ; l < g.length && r < s.length; r++)
            if(g[l] <= s[r])
                l++;
 
        return l;
    }
}

Brute-Force Solution

Intuition

For every child, we check all available cookies from left to right. If we find a cookie big enough to satisfy that child’s greed, we assign it, mark that cookie as used, and move on to the next child.

To try and satisfy as many children as possible, we can sort the cookies first so we give each child the smallest possible valid cookie.

Steps

  1. Sort the cookie array s in ascending order.
  2. Keep a boolean[] array to mark which cookies have already been given to a child.
  3. For each child in g, iterate through s. The first cookie that satisfies s[j] >= child_greed and isn’t used yet is given to that child.
  4. Increment the count of satisfied children and mark the cookie as used.
import java.util.Arrays;
 
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(s);
        boolean[] used = new boolean[s.length];
        int count = 0;
 
        for (int child : g) {
            for (int j = 0; j < s.length; j++) {
                if (!used[j] && s[j] >= child) {
                    used[j] = true;
                    count++;
                    break; // Move to the next child
                }
            }
        }
        return count;
    }
}
  • Time Complexity: where is the number of children and is the number of cookies.
  • Space Complexity: for tracking used cookies.

Most Optimized Solution (Greedy + Single for Loop)

Intuition (Easy to Remember)

Imagine a queue of least greedy children and a tray of smallest available cookies.

  • Always try to satisfy the child with the smallest greed using the smallest available cookie.
  • Iterate through every cookie one by one (j++).
  • If the current cookie s[j] is big enough to satisfy the current child g[i], we give it to them and move to the next child (i++).
  • If the cookie isn’t big enough, it gets skipped automatically as the loop moves to the next cookie, while i stays on the same child waiting for a larger cookie.

Steps

  1. Sort both arrays g (children) and s (cookies) in ascending order.
  2. Initialize pointer i = 0 to track the satisfied children.
  3. Use a single for loop to iterate through every cookie s[j].
  4. If g[i] <= s[j], increment i to move to the next child.
  5. Return i, which naturally counts the total number of content children.
import java.util.Arrays;
 
public class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
 
        int i = 0;
        for (int j = 0; i < g.length && j < s.length; j++) {
            if (g[i] <= s[j]) {
                i++;
            }
        }
        return i;
    }
}
  • Time Complexity: due to sorting both arrays. The traversal takes time.
  • Space Complexity: (or depending on the internal dual-pivot Quicksort implementation).

Backlinks