Problem 33.1 · Greedy AlgorithmsEasy

Assign Cookies

PatternGreedy Choice Two Pointers: Read and Write

What it teaches: Exchange argument: give each child the smallest cookie that satisfies them.

Practise it on judges as “Assign Cookies”.

The problem

Child i is content with a cookie of size ≥ g[i]. Each child gets at most one cookie. Return the maximum number of content children.

Example 1

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

Constraints

1 ≤ g, s ≤ 3 × 10⁴

Pattern clues in the wording

→ Match items to requirements, maximise matches

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	g = [1,2,3] s = [1,1]	1
2	g = [1,2] s = [1,2,3]	2

From slow to fast

Approaches

1. Sort + two pointers · O(n log n + m log m)

Sort + two pointers

Time O(n log n + m log m) Space O(1) extra

Walk cookies in increasing size; if the current cookie satisfies the current child, move to the next child.

Approach 1

import java.util.Arrays;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child = 0;
        for (int cookie = 0; cookie < s.length && child < g.length; cookie++)
            if (s[cookie] >= g[child]) child++;
        return child;
    }
}

Verdict: Optimal by exchange.

Before you submit

Edge cases and common mistakes

Test these inputs

No cookies
Cookies too small for everyone

Mistakes people make

Giving the biggest cookie to the first child.

Interview

Follow-up questions

Prove it with an exchange argument.

Command Palette

The problem

Approaches

Sort + two pointers

Edge cases and common mistakes

Follow-up questions