Solution 1 - Greedy (Two Pointers)

Sort both the greed factors array g and the cookie sizes array s. Use two pointers to iterate through both arrays. For each child, find the smallest cookie that satisfies their greed factor. If the current cookie can satisfy the current child (s[j] >= g[i]), assign it and move both pointers. Otherwise, skip the cookie and try the next one.

TimeComplexity: O(n \log n + m \log m)

SpaceComplexity: O(1)

""" 0455.1 - Assign Cookies - Solution 1 - Greedy (Two Pointers) """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        """Assign Cookies Function"""
        g.sort()
        s.sort()
        child = 0
        cookie = 0
        while child < len(g) and cookie < len(s):
            if s[cookie] >= g[child]:
                child += 1
            cookie += 1
        return child


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findContentChildren([1, 2, 3], [1, 1]))       # Expected: 1
    print(Solution().findContentChildren([1, 2], [1, 2, 3]))       # Expected: 2
    print(Solution().findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]))  # Expected: 2


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Greedy (Reverse Sort, Largest First)

Sort both arrays in descending order and try to assign the largest cookies to the greediest children first. Iterate through cookies and children simultaneously — if the current cookie satisfies the current child, move to the next child. Always move to the next cookie.

TimeComplexity: O(n \log n + m \log m)

SpaceComplexity: O(1)

""" 0455.2 - Assign Cookies - Solution 2 - Greedy (Reverse Sort, Largest First) """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        """Assign Cookies Function"""
        g.sort(reverse=True)
        s.sort(reverse=True)
        child = 0
        cookie = 0
        while child < len(g) and cookie < len(s):
            if s[cookie] >= g[child]:
                child += 1
            cookie += 1
        return child


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().findContentChildren([1, 2, 3], [1, 1]))       # Expected: 1
    print(Solution().findContentChildren([1, 2], [1, 2, 3]))       # Expected: 2
    print(Solution().findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]))  # Expected: 2


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0455 - Assign Cookies

Solution 1 - Greedy (Two Pointers)

Solution 2 - Greedy (Reverse Sort, Largest First)