Assign Cookies - Practice Coding Problems

Assign Cookies - Problem

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j].

If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Input & Output

Example 1 — Basic Case

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

› Output: 1

💡 Note: Child with greed factor 1 can be satisfied with cookie of size 1. Children with greed factors 2 and 3 cannot be satisfied with remaining cookies.

Example 2 — Perfect Match

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

› Output: 2

💡 Note: Child with greed factor 1 gets cookie of size 1, child with greed factor 2 gets cookie of size 2. Both children are satisfied.

Example 3 — No Satisfaction

$ Input: g = [5,6,7], s = [1,2,3]

› Output: 0

💡 Note: All children have greed factors larger than any available cookie size, so no child can be satisfied.

Constraints

1 ≤ g.length ≤ 3 × 10⁴
0 ≤ s.length ≤ 3 × 10⁴
1 ≤ g[i] ≤ 2³¹ - 1
1 ≤ s[j] ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Children with greed factors [1,2,3] and cookies with sizes [1,1]

Process

Match children with cookies using greedy strategy

Output

Maximum number of satisfied children: 1

Key Takeaway

🎯 Key Insight: Greedy strategy of satisfying least greedy children first maximizes total satisfaction

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use a greedy approach: sort both arrays and always satisfy the least greedy child first with the smallest sufficient cookie. This leaves more options for greedier children. Best approach is Greedy Sort and Match: Time O(n log n + m log m), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Sort and Match	O(n log n + m log m)	O(1)	Sort both arrays and greedily match smallest sufficient cookie to least greedy child
Brute Force - Try All Combinations	O(2^n × m!)	O(n + m)	Generate all possible assignments and find the one that maximizes satisfied children

Greedy Sort and Match — Algorithm Steps

Sort children array by greed factor (ascending)
Sort cookies array by size (ascending)
Use two pointers to match least greedy child with smallest sufficient cookie

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Arrays

Sort children by greed and cookies by size

Two Pointers

Match least greedy child with smallest sufficient cookie

Optimal Result

Greedy choice leads to maximum satisfaction

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* g, int gSize, int* s, int sSize) {
    qsort(g, gSize, sizeof(int), compare);  // Sort children by greed factor
    qsort(s, sSize, sizeof(int), compare);  // Sort cookies by size
    
    int childPtr = 0;
    int cookiePtr = 0;
    int satisfied = 0;
    
    while (childPtr < gSize && cookiePtr < sSize) {
        if (s[cookiePtr] >= g[childPtr]) {
            // Cookie satisfies child
            satisfied++;
            childPtr++;
        }
        cookiePtr++;
    }
    
    return satisfied;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int g[1000], s[1000];
    int gSize = 0, sSize = 0;
    
    char* token = strtok(line1 + 1, ",]");
    while (token != NULL) {
        g[gSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    token = strtok(line2 + 1, ",]");
    while (token != NULL) {
        s[sSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(g, gSize, s, sSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log m)

Sorting both arrays dominates, matching takes O(n + m)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for pointers and variables

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Sort and Match — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler