Assign Cookies

Share

Assign cookies to children where each child needs minimum greed factor. Maximize satisfied children.

Example 1
Input: g=[1,2,3], s=[1,1] → Output: 1. Only child with greed 1 can be satisfied.
Example 2
Input: g=[1,2], s=[1,2,3] → Output: 2. Both children can be satisfied.

Solution Approach

Sort both arrays. Use two pointers: try to satisfy each child with the smallest sufficient cookie.

  • Sort greed array g and size array s
  • Use pointer i for children, j for cookies
  • If s[j] >= g[i], satisfy child i and advance both pointers
  • Otherwise advance j only
  • Return i (satisfied count)
Java
public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int i = 0, j = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) i++;
        j++;
    }
    return i;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)