Assign Cookies

Easy Subject: Greedy

Time Complexity

O(N log N + M log M)

Space Complexity

O(1)

Problem Description

Problem Statement

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]. Return the maximum number of content children.

Example 1:

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

Optimal Solution

Python

Approach: Two Pointers Greedy

Sort both arrays. Use two pointers. If the current cookie s[j] satisfies the current child g[i], move both pointers (child is fed). If not, move to a larger cookie. This ensures we feed children with the smallest possible cookies.

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i = j = 0

        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                i += 1
            j += 1

        return i