💬 Discord
Sign In
NeetCode #186LC-455EasyTwo Pointers
← Back to All Problems

#186 · #455 · Assign Cookies(分发饼干)

📌 Problem Statement & Constraints

You have children with greed factors g and cookies with sizes s. Each child gets at most one cookie, and a child is content if the cookie size is at least their greed factor. Return the maximum number of content children. Constraints: 1 <= g.length <= 3 * 10^4, 0 <= s.length <= 3 * 10^4, 1 <= g[i], s[j] <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. Sort both arrays. Then a two-pointer greedy works: try to satisfy the least greedy child with the smallest cookie that works.
  2. If the current cookie is large enough, assign it and advance both pointers.
  3. Otherwise the cookie is too small for even the least greedy child, so discard it and advance only the cookie pointer.
  4. This greedy is optimal by an exchange argument: using the smallest sufficient cookie never disadvantages a later child.

💻 Benchmark Python3 Implementation

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i = j = 0                      # i: child, j: cookie
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:           # cookie satisfies this child
                i += 1
            j += 1                     # this cookie is used up either way
        return i

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n + m log m): the sorts dominate; the scan is linear.
💾 Space Complexity
O(1) beyond the sorts.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting only one array: both must be sorted for the greedy to be valid.
  • Advancing the child pointer when the cookie is too small: the child stays and waits for a larger cookie.
  • Trying to maximise the total cookie size assigned: the objective is the number of content children, not the total size.
  • Handling an empty cookie array: the loop does not execute and i stays 0, which is correct.