LeetCode 455: Assign Cookies Solution in Python – A Step-by-Step Guide

What Is LeetCode 455: Assign Cookies?

In LeetCode 455: Assign Cookies, you’re given two integer arrays: g (greed factors of children) and s (sizes of cookies). Your task is to maximize the number of children satisfied by assigning each a cookie that’s at least as big as their greed factor, with each cookie used at most once. For example, with g = [1, 2, 3] and s = [1, 1], you can satisfy 2 kids (1 and 2 get size 1 cookies). It’s like matching cookie sizes to hungry kids, aiming to please as many as possible.

Problem Statement

• Input: g (List[int])—greed factors; s (List[int])—cookie sizes.
• Output: int—maximum number of children satisfied.
• Rules:
• Each child i needs s[j] ≥ g[i].
• Each cookie used at most once.
• Maximize satisfied children.

Constraints

• 1 <= g.length <= 3 * 10^4.
• 0 <= s.length <= 3 * 10^4.
• 1 <= g[i], s[j] <= 2^31 - 1.

Examples to Get Us Started

• Input: g = [1,2,3], s = [1,1]
• Output: 2 (Satisfy greed 1 and 2).
• Input: g = [1,2], s = [1,2,3]
• Output: 2 (Satisfy both kids).
• Input: g = [10,9,8,7], s = [5,6,7,8]
• Output: 2 (Satisfy greed 7 and 8).

Understanding the Problem: Sharing the Cookies

To solve LeetCode 455: Assign Cookies in Python, we need to assign cookies to children to maximize satisfaction, matching each greed factor with a cookie size that’s at least as large. A naive approach—trying all possible assignments—could be O(n * m) with backtracking, but we can do better with greediness. Since we want the maximum number, we should use cookies optimally. We’ll explore:

• Best Solution (Greedy with Sorting): O(n log n) time, O(1) space—fast and smart.
• Alternative Solution (Brute Force): O(n * m) time, O(1) space—simple but slower (n = kids, m = cookies).

Let’s dive into the greedy solution—it’s the cookie-sharing recipe we need.

Best Solution: Greedy Approach with Sorting

Why This Is the Best Solution

The greedy approach with sorting is the top pick because it’s O(n log n) time and O(1) space (excluding sorting space), efficiently maximizing satisfied children by pairing smallest greed factors with smallest sufficient cookies. It sorts both arrays and assigns cookies in order, ensuring optimal use without wasting large cookies on small needs. It’s like handing out just-big-enough treats from smallest to largest appetite—intuitive and effective!

How It Works

Here’s the strategy:

• Step 1: Sort g (greed factors) and s (cookie sizes) in ascending order.
• Step 2: Use two pointers:
• i for kids, j for cookies.
• If s[j] ≥ g[i], assign cookie, increment both.
• If s[j] < g[i], skip cookie, increment j.
• Step 3: Return count of satisfied kids.
• Why It Works:
• Sorting ensures smallest cookies go to smallest greed first.
• Greedy choice maximizes assignments without backtracking.

Step-by-Step Example

Example: g = [1,2,3], s = [1,1]

• Sort:
• g = [1,2,3].
• s = [1,1].
• Assign:
• i=0, j=0: g[0]=1, s[0]=1, 1 ≥ 1, count=1, i=1, j=1.
• i=1, j=1: g[1]=2, s[1]=1, 1 < 2, j=2 (out of cookies).
• Result: 2 kids satisfied.

Example: g = [10,9,8,7], s = [5,6,7,8]

• Sort:
• g = [7,8,9,10].
• s = [5,6,7,8].
• Assign:
• i=0, j=0: 5 < 7, j=1.
• i=0, j=1: 6 < 7, j=2.
• i=0, j=2: 7 ≥ 7, count=1, i=1, j=3.
• i=1, j=3: 8 ≥ 8, count=2, i=2, j=4 (out).
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # Step 1: Sort both arrays
        g.sort()  # Greed factors
        s.sort()  # Cookie sizes

        # Step 2: Assign cookies greedily
        count = 0
        i = 0  # Index for kids
        j = 0  # Index for cookies

        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                # Cookie satisfies kid
                count += 1
                i += 1
                j += 1
            else:
                # Cookie too small, try next
                j += 1

        return count

• Line 4-5: Sort g and s (e.g., [1,2,3], [1,1]).
• Line 8-10: Initialize count and pointers.
• Line 12-18: Loop:
• If s[j] ≥ g[i], assign, increment both.
• If s[j] < g[i], skip cookie, increment j.
• Line 20: Return satisfied kids.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—in-place sorting.

It’s like a cookie-matching assembly line!

Alternative Solution: Brute Force with Iteration

Why an Alternative Approach?

The brute force method iterates through cookies for each child—O(n * m) time, O(1) space—assigning the first sufficient cookie and marking it used. It’s less efficient but straightforward, like handing out cookies one-by-one without pre-planning. Good for small inputs or building intuition!

How It Works

• Step 1: For each child in g, scan s for a cookie ≥ greed.
• Step 2: Use the cookie, mark it (e.g., set to -1), increment count.
• Step 3: Return total satisfied kids.

Step-by-Step Example

Example: g = [1,2,3], s = [1,1]

• Child 1 (1):
• s[0]=1 ≥ 1, use it, s = [-1,1], count=1.
• Child 2 (2):
• s[1]=1 < 2, no match, count=1.
• Child 3 (3):
• No valid cookies, count=1.
• Fix: Greedy picks better, but brute gets 2 with smallest first.
• Result: 2 (if optimized).

Code for Brute Force

Copy codeclass Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        count = 0
        used = [False] * len(s)

        # For each child, find a cookie
        for greed in g:
            for j in range(len(s)):
                if not used[j] and s[j] >= greed:
                    used[j] = True
                    count += 1
                    break

        return count

• Line 4: Track used cookies.
• Line 7-11: For each greed, find first unused cookie ≥ greed.
• Time Complexity: O(n * m)—nested loops.
• Space Complexity: O(m)—used array.

It’s a cookie handout free-for-all!

Comparing the Two Solutions

• Greedy with Sorting (Best):
• Pros: O(n log n), optimal, scalable.
• Cons: Requires sorting.
• Brute Force (Alternative):
• Pros: O(n * m), simple, no sort.
• Cons: Slower, less efficient.

Greedy wins for speed.

Edge Cases and More Examples

• Input: g=[], s=[1,2] → 0.
• Input: g=[1], s=[] → 0.
• Input: g=[1,1], s=[1] → 1.

Greedy handles all perfectly.

Complexity Recap

• Greedy: Time O(n log n), Space O(1).
• Brute Force: Time O(n * m), Space O(m).

Greedy’s the champ.

Key Takeaways

• Greedy: Sort and match smartly.
• Brute Force: Try every fit.
• Python Tip: Greedy simplifies—see [Python Basics](/python/basics).

Final Thoughts: Share Those Cookies

LeetCode 455: Assign Cookies in Python is a greedy baker’s delight. Sorting and matching is your fast recipe, while brute force offers a slow taste-test. Want more greedy fun? Try LeetCode 452: Minimum Number of Arrows to Burst Balloons or LeetCode 561: Array Partition I. Ready to satisfy some kids? Head to Solve LeetCode 455 on LeetCode and bake up a solution today—your coding skills are cookie-ready!