## Similar Problems

Similar Problems not available

# Assign Cookies - Leetcode Solution

## Companies:

LeetCode: Assign Cookies Leetcode Solution

Difficulty: Easy

Topics: greedy sorting array two-pointers

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.

- Initialize two pointers (i and j) to start from first element of g[] and s[] respectively.
- 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.
- 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.
- 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.

## Assign Cookies Solution Code

`1`