Assign Cookies | Greedy Algorithm

Problem Statement

You are given:

• g[i] = greed factor of the ith child
• s[j] = size of the jth cookie

A child is satisfied if:

cookie size >= greed factor

Enter fullscreen mode Exit fullscreen mode

Each cookie can be assigned to only one child.

Return the maximum number of satisfied children.

Brute Force Intuition

For every child, try all available cookies and assign the smallest valid cookie that can satisfy the child.

To avoid reusing cookies, we need extra tracking.

This works but becomes inefficient because every child may scan all cookies.

Complexity

• Time Complexity: O(N × M)
• Space Complexity: O(M)

Brute Force Snippet

boolean[] used = new boolean[s.length];

int count = 0;

for (int child : g) {

    for (int j = 0; j < s.length; j++) {

        if (!used[j] && s[j] >= child) {
            used[j] = true;
            count++;
            break;
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Suppose we have:

Greed : [1,2,3]
Cookies : [1,2]

Enter fullscreen mode Exit fullscreen mode

Giving a larger cookie to a less greedy child can waste resources.

Instead:

Always satisfy the least greedy child using the smallest possible cookie.

This leaves larger cookies available for greedier children.

Greedy Pattern Recognition

Whenever you see:

• Matching two arrays
• Maximize number of successful assignments
• Smallest resource satisfying smallest requirement

Think:

Sort Both Arrays + Two Pointers

Optimal Approach

Algorithm

1. Sort greed array.
2. Sort cookie array.
3. Use two pointers:
   • One for children.
   • One for cookies.
4. If cookie can satisfy child:
   • Assign it.
   • Move both pointers.
5. Otherwise:
   • Try a larger cookie.

Optimal Java Solution

import java.util.*;

class Solution {

    public int findContentChildren(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);

        int child = 0;
        int cookie = 0;

        while (child < g.length && cookie < s.length) {

            if (s[cookie] >= g[child]) {
                child++;
                cookie++;
            } else {
                cookie++;
            }
        }

        return child;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

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

Enter fullscreen mode Exit fullscreen mode

After Sorting

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

Enter fullscreen mode Exit fullscreen mode

Assignment

Child 1 ← Cookie 1 ✓

Child 2 ← Cookie 1 ✗
No larger cookies left

Enter fullscreen mode Exit fullscreen mode

Result

Satisfied Children = 1

Enter fullscreen mode Exit fullscreen mode

Another Example

Input

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

Enter fullscreen mode Exit fullscreen mode

Assignment

1 ← 1 ✓

2 ← 2 ✓

Enter fullscreen mode Exit fullscreen mode

Result

Satisfied Children = 2

Enter fullscreen mode Exit fullscreen mode

Why Greedy Works?

Consider:

Child Greed = 1
Cookie = 5

Enter fullscreen mode Exit fullscreen mode

Using a large cookie here may prevent satisfying a greedier child later.

Instead:

Give the smallest possible cookie that satisfies the current smallest greed.

This preserves larger cookies for future children.

Complexity Analysis

Metric Complexity Time Complexity O(N log N + M log M) Space Complexity O(1)

Sorting dominates the runtime.

Interview One-Liner

Sort both arrays and use two pointers. Assign the smallest cookie capable of satisfying the least greedy child to maximize the total number of satisfied children.

Pattern Learned

Requirement Array
+
Resource Array
+
Maximum Assignments

=> Sort Both Arrays + Two Pointers

Enter fullscreen mode Exit fullscreen mode

Similar Problems

• Assign Cookies
• Boats to Save People
• Minimum Number of Arrows to Burst Balloons
• Matching Jobs to Workers
• Interval Scheduling Variations