Skip to main content
DSA patterns

Assign Cookies

easyGreedy Must-doTCSInfosysWipro

Problem statement

You have g, a list where g[i] is the smallest cookie size that would satisfy child i, and s, a list of the cookie sizes you actually have. Each child can get at most one cookie, and a cookie of size s[j] only satisfies a child if s[j] >= g[i]. Hand out cookies to satisfy as many children as possible, and return that maximum count.

Swap "children" and "cookies" for "requests" and "server capacity slots": each request needs at least a certain amount of resource to be served, each slot offers a fixed amount, and a slot can only serve one request. This is the same matching question — how many requests can you satisfy given a fixed pool of differently-sized slots.

Examples

Example 1

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

Output: 1

Explanation: There are 3 children and only 2 cookies, both of size 1. A size-1 cookie can only satisfy the child with greed 1 — it's too small for greed 2 or greed 3 — so only one child ends up content, even though you technically have two cookies.

Example 2

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

Output: 2

Explanation: Both children can be satisfied — one cookie is enough for each of them, and there's a spare cookie (size 3) left over that nobody needed.

Hints

Hint 1: A child with a small greed factor is the easiest one to satisfy — almost any cookie will do. A child with a large greed factor needs a specific, bigger cookie. Which one should you try to satisfy first with your smallest usable cookies?

Approach

Optimal: Sort both, single two-pointer pass

Intuition

Sort both lists. Now walk through the cookies from smallest to largest, and keep a pointer at the least-greedy child who still hasn't been satisfied. Every time the current cookie is big enough for that child, the child is satisfied and the pointer moves to the next (more demanding) child; either way, move on to the next cookie. Because both lists are sorted, this single pass is guaranteed to find the same maximum as trying every combination — giving the least-greedy unsatisfied child the very next cookie that can reach them is never a worse choice than saving that cookie for later.

This is what makes it faster than the brute force: no re-scanning of remaining cookies for every child, just one linear sweep after the sort.

Steps

  1. Sort the greed factors and the cookie sizes.
  2. Start a pointer child at 0 (the least-greedy unsatisfied child).
  3. For each cookie, in increasing order:
    • If every child is already satisfied, stop early.
    • If the current cookie is big enough for the child at child, that child is now satisfied — advance the pointer.
    • Move to the next cookie either way.
  4. Return child — the number of children the pointer advanced past is exactly the number satisfied.

Dry run

g = [1, 2], s = [1, 2, 3] (already sorted)

cookie children[child] big enough? action child after
1 1 yes satisfy child 0 1
2 2 yes satisfy child 1 2
3 — — child == len(children), stop 2

Final count: 2 — matches the example.

Edge cases: an empty cookie list or an empty greed list both immediately return 0 — there's nothing to iterate, or nothing to satisfy. A cookie exactly equal to a child's greed factor still counts (the comparison is >=, not strict).

Complexity

Time O(n log n + m log m)

Space O(1) - extra, beyond the sort

class Solution:
    def findContentChildren(self, g: list[int], s: list[int]) -> int:
        children = sorted(g)
        cookies = sorted(s)
        child = 0
        for cookie in cookies:
            if child == len(children):
                break
            if children[child] <= cookie:
                child += 1
        return child


if __name__ == "__main__":
    print(Solution().findContentChildren([1, 2, 3], [1, 1]))
    print(Solution().findContentChildren([1, 2], [1, 2, 3]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: matching two sorted-by-size things to maximize how many "requests" get satisfied, each needing at least a minimum amount
  • Idea: sort both lists; walk cookies in increasing order, advancing to the next unsatisfied (least-greedy) child every time the current cookie is big enough
  • Cost: O(n log n + m log m) time (dominated by sorting), O(1) extra space beyond the sort
  • Trap: matching greedily without sorting first, or handing a child a bigger cookie than necessary — both waste cookies that a more demanding child could have used

Interview follow-ups

  • What if each child could receive more than one cookie, as long as their combined size meets the greed factor?

    This turns into a variant of the subset-sum / partition problem rather than a simple matching — you'd need to decide which subsets of cookies to combine for which children, and greedily assigning the smallest single cookie no longer works, since it might be better to save several small cookies to combine for one demanding child. It's a meaningfully harder problem, generally solved with dynamic programming or a more careful greedy plus exchange-argument proof depending on the exact constraints.

  • What if cookies could be split into smaller pieces?

    Then it becomes purely about total capacity: sort children by greed, and as long as the total remaining cookie size is enough to cover a child's requirement, you can always carve out exactly what's needed. The problem reduces to a running-sum feasibility check rather than a matching problem, and you'd typically maximize count by satisfying children in increasing order of greed for the same reason as the original problem — small needs first, to leave flexibility for bigger ones.

  • The lists are massive and arrive as sorted streams rather than arrays you can index into. Does the algorithm change?

    Not fundamentally — the two-pointer approach only ever reads each list once, moving forward, so it's already stream-friendly as long as both streams are pre-sorted. If they're not sorted going in, you'd need an external sort (or a streaming approach like a k-way merge over pre-sorted chunks) before the same two-pointer logic applies, since the correctness of the algorithm depends entirely on both sequences arriving in increasing order.

Frequently asked questions

Because saving a bigger cookie doesn't help — a cookie big enough for the current child is either big enough for a greedier child too, or it isn't needed by anyone smaller. Using the smallest sufficient cookie now never closes off an option you would have had otherwise: any cookie left over after this choice is still available for every child you haven't gotten to yet. This "exchange argument" is the standard way to justify a greedy strategy — any other valid assignment can be rearranged into this one without doing worse.

Sorting only the cookies (as the brute force does) still leaves you scanning for the best fit per child, which costs O(n·m) in the worst case. Sorting both lists is what makes the single linear pass possible — with both in increasing order, "does this cookie satisfy the current least-demanding child" is answered by one comparison, no scanning required.

The problem defines a child as content when s[j] >= g[i] — a cookie exactly equal to the greed factor counts. Using a strict < (or >) comparison would incorrectly skip a cookie that exactly meets a child's minimum, undercounting the result.

This is the shape of any "match limited resources to requests with minimum-size requirements" problem: assigning fixed-size compute slots to jobs with minimum memory needs, matching available IP blocks to subnet requests, or handing out worker threads with a minimum throughput guarantee to tasks that need at least that much. The greedy "smallest sufficient resource first" strategy generalizes directly.

Not for correctness or performance — the two-pointer approach dominates in both. The brute force is only useful as a stepping stone: it's the version most people naturally think of first, and walking through why the smallest-sufficient-cookie choice is always safe is what motivates sorting both lists and collapsing the search into one pass.