Assign Cookies — LeetCode 455 Python Solution

The problem

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

Example

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.

Python solution

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        j = 0
        for i, x in enumerate(g):
            while j < len(s) and s[j] < g[i]:
                j += 1
            if j >= len(s):
                return i
            j += 1
        return len(g)

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 455. Assign Cookies is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems