Assign Cookies - Leetcode Solution

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 gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, 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: Input: [1,2,3], [1,1] Output: 1 Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. The sizes of cookies are 1, 1. You can only give a cookie to the child with greed factor 1. So you should output 1.

Solution: To maximize the number of content children, we need to first sort the greed factor array(g[]) and also sort the cookie size array(s[]). We assign the largest cookie to greediest child and then so on. We can solve this problem by using two pointers.

1. Initialize two pointers (i and j) to start from first element of g[] and s[] respectively.
2. if s[j] >= g[i], that means we can assign cookie j to child i. a) Increment count, as we can assign cookie to child. b) Increment both pointers(i and j), as we move to next child and next cookie.
3. else if s[j] < g[i], that means we can't assign cookie j to child i. a) Increment pointer j, as current cookie can't be assigned to current child.
4. Repeat steps 2-3 until any of the pointer reaches end of their array. At the end, count will contain how many children got the cookie.

Code in Python:

class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() # sorting greed factor array s.sort() # sorting cookie size array i,j,count = 0,0,0 # initializing pointers and count

    while i<len(g) and j<len(s):
        if s[j] >= g[i]: # assign cookie j to child i as current cookie size is greater than or equal to greed factor
            count += 1
            i += 1
            j += 1
        else: # current cookie size is less than greed factor of child i
            j += 1
            
    return count # return the count of content children

Time Complexity: Sorting both arrays takes O(nlogn) time. Then iterating over both arrays takes O(n) time. So final time complexity is O(nlogn+n) = O(nlogn)

Space Complexity: Sorting algorithm generally takes O(logn) space. So final space complexity is O(logn) for sorting arrays.

1