Assign Cookies

🎯

Assign Cookies

easyGREEDYAmazonGoogle

Imagine you have a group of children each with a greed factor for cookies, and a pile of cookies of various sizes. Your goal is to distribute cookies to maximize the number of satisfied children.

💡 This problem is a classic greedy assignment problem where beginners often struggle to see why sorting and a two-pointer approach leads to an optimal solution instead of trying all combinations.

📋

Problem Statement

You are given two integer arrays g and s representing the greed factor of each child and the size of each cookie respectively. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with. Each cookie j has a size s[j]. Your goal is to assign cookies to children such that the number of content children is maximized. Each cookie can be assigned to at most one child, and each child can receive at most one cookie. Return the maximum number of content children.

1 ≤ g.length, s.length ≤ 10^51 ≤ g[i], s[j] ≤ 10^9

💡

Example

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

Output1

Only one child with greed 1 can be content with a cookie of size 1.

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

Output2

Assign cookie size 1 to child with greed 1, cookie size 2 to child with greed 2.

• All children have greed larger than any cookie size → 0
• All cookies are larger than all greed factors → number of children
• Empty greed array or empty cookie array → 0
• Greed and cookie arrays of length 1 with equal values → 1

⚠️

Common Mistakes

Not sorting the greed and cookie arrays

Incorrect assignments leading to suboptimal number of content children

✅ Always sort both arrays before assignment

Assigning cookies without marking them used or moving pointers correctly

Cookies may be assigned multiple times or children skipped

✅ Use two pointers and move both after assignment

Using nested loops without marking cookies used

Overcounting assignments or runtime errors

✅ Use a used array or two-pointer approach to avoid reuse

Not handling empty input arrays

Runtime errors or incorrect output

✅ Check for empty arrays and return 0 if no children or cookies

🧠

Brute Force (Nested Loops)

💡 This approach tries every cookie for every child to find a match, which is intuitive but inefficient. It helps understand the problem's nature before optimizing.

Intuition

Try to assign each cookie to each child and count how many children can be satisfied by any cookie.

Algorithm

1. Initialize count of content children to 0.
2. For each child, iterate over all cookies to find a cookie that satisfies the child's greed.
3. If a suitable cookie is found, assign it and mark the cookie as used.
4. Return the total count of content children.

💡 This approach is straightforward but inefficient because it checks all possible assignments without any ordering or pruning.

</>

Code

def findContentChildren(g, s):
    used = [False] * len(s)
    count = 0
    for i in range(len(g)):
        for j in range(len(s)):
            if not used[j] and s[j] >= g[i]:
                used[j] = True
                count += 1
                break
    return count

# Driver code
if __name__ == '__main__':
    g = [1,2,3]
    s = [1,1]
    print(findContentChildren(g, s))  # Output: 1

Line Notes

used = [False] * len(s)Track which cookies have been assigned to avoid reuse.

for i in range(len(g))Iterate over each child to try to satisfy their greed.

for j in range(len(s))Check every cookie for suitability for the current child.

if not used[j] and s[j] >= g[i]Assign cookie only if unused and large enough to satisfy the child.

import java.util.*;
public class AssignCookies {
    public static int findContentChildren(int[] g, int[] s) {
        boolean[] used = new boolean[s.length];
        int count = 0;
        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < s.length; j++) {
                if (!used[j] && s[j] >= g[i]) {
                    used[j] = true;
                    count++;
                    break;
                }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int[] g = {1,2,3};
        int[] s = {1,1};
        System.out.println(findContentChildren(g, s)); // Output: 1
    }
}

Line Notes

boolean[] used = new boolean[s.length]Keep track of assigned cookies to prevent reuse.

for (int i = 0; i < g.length; i++)Loop over each child to find a matching cookie.

for (int j = 0; j < s.length; j++)Try every cookie for the current child.

if (!used[j] && s[j] >= g[i])Assign cookie if it satisfies the child's greed and is unused.

#include <iostream>
#include <vector>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    vector<bool> used(s.size(), false);
    int count = 0;
    for (int i = 0; i < g.size(); i++) {
        for (int j = 0; j < s.size(); j++) {
            if (!used[j] && s[j] >= g[i]) {
                used[j] = true;
                count++;
                break;
            }
        }
    }
    return count;
}

int main() {
    vector<int> g = {1,2,3};
    vector<int> s = {1,1};
    cout << findContentChildren(g, s) << endl; // Output: 1
    return 0;
}

Line Notes

vector<bool> used(s.size(), false)Track which cookies are already assigned.

for (int i = 0; i < g.size(); i++)Iterate over each child to find a cookie.

for (int j = 0; j < s.size(); j++)Check all cookies for suitability.

if (!used[j] && s[j] >= g[i])Assign cookie if it meets greed and is unused.

function findContentChildren(g, s) {
    const used = new Array(s.length).fill(false);
    let count = 0;
    for (let i = 0; i < g.length; i++) {
        for (let j = 0; j < s.length; j++) {
            if (!used[j] && s[j] >= g[i]) {
                used[j] = true;
                count++;
                break;
            }
        }
    }
    return count;
}

// Test
console.log(findContentChildren([1,2,3], [1,1])); // Output: 1

Line Notes

const used = new Array(s.length).fill(false)Mark cookies as assigned to avoid reuse.

for (let i = 0; i < g.length; i++)Loop through each child to assign a cookie.

for (let j = 0; j < s.length; j++)Try every cookie for the current child.

if (!used[j] && s[j] >= g[i])Assign cookie if it satisfies the child's greed and is unused.

⏱

Complexity

TimeO(n*m) where n = number of children, m = number of cookies

SpaceO(m) for the used array

We check every cookie for every child, resulting in a nested loop.

💡 For n=1000 children and m=1000 cookies, this means 1,000,000 checks, which is inefficient.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but helps understand the problem before optimizing.

🧠

Sorting + Two Pointers (Greedy)

💡 Sorting both arrays and using two pointers allows us to efficiently assign the smallest cookie that satisfies each child, improving performance drastically.

Intuition

Sort greed and cookie sizes. Use two pointers to assign cookies starting from the smallest greed and smallest cookie, moving forward greedily.

Algorithm

1. Sort the greed array and the cookie size array.
2. Initialize two pointers: one for children (i), one for cookies (j).
3. While both pointers are within their arrays, if cookie[j] satisfies child[i], assign and move both pointers forward.
4. Otherwise, move the cookie pointer forward to find a bigger cookie.
5. Return the count of assigned children.

💡 Sorting ensures we assign the smallest sufficient cookie to each child, avoiding waste and maximizing assignments.

</>

Code

def findContentChildren(g, s):
    g.sort()
    s.sort()
    i = j = 0
    count = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:
            count += 1
            i += 1
            j += 1
        else:
            j += 1
    return count

# Driver code
if __name__ == '__main__':
    g = [1,2,3]
    s = [1,1]
    print(findContentChildren(g, s))  # Output: 1

Line Notes

g.sort()Sort greed factors to assign smallest greed first.

s.sort()Sort cookies to assign smallest cookie first.

i = j = 0Initialize pointers for children and cookies.

if s[j] >= g[i]Assign cookie if it satisfies the child's greed.

import java.util.*;
public class AssignCookies {
    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0, count = 0;
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                count++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int[] g = {1,2,3};
        int[] s = {1,1};
        System.out.println(findContentChildren(g, s)); // Output: 1
    }
}

Line Notes

Arrays.sort(g)Sort greed array to process children from least to most greedy.

Arrays.sort(s)Sort cookies to assign smallest cookies first.

int i = 0, j = 0Initialize pointers for children and cookies arrays.

if (s[j] >= g[i])Assign cookie if it satisfies the child's greed.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int i = 0, j = 0, count = 0;
    while (i < g.size() && j < s.size()) {
        if (s[j] >= g[i]) {
            count++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    return count;
}

int main() {
    vector<int> g = {1,2,3};
    vector<int> s = {1,1};
    cout << findContentChildren(g, s) << endl; // Output: 1
    return 0;
}

Line Notes

sort(g.begin(), g.end())Sort greed factors to assign smallest greed first.

sort(s.begin(), s.end())Sort cookies to assign smallest cookie first.

int i = 0, j = 0Initialize two pointers for children and cookies.

if (s[j] >= g[i])Assign cookie if it satisfies the child's greed.

function findContentChildren(g, s) {
    g.sort((a,b) => a - b);
    s.sort((a,b) => a - b);
    let i = 0, j = 0, count = 0;
    while (i < g.length && j < s.length) {
        if (s[j] >= g[i]) {
            count++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    return count;
}

// Test
console.log(findContentChildren([1,2,3], [1,1])); // Output: 1

Line Notes

g.sort((a,b) => a - b)Sort greed array ascending to assign smallest greed first.

s.sort((a,b) => a - b)Sort cookies ascending to assign smallest cookie first.

let i = 0, j = 0Initialize pointers for children and cookies arrays.

if (s[j] >= g[i])Assign cookie if it satisfies the child's greed.

⏱

Complexity

TimeO(n log n + m log m) due to sorting, where n and m are lengths of g and s

SpaceO(1) or O(n + m) depending on sorting implementation

Sorting dominates the time complexity; the two-pointer assignment is linear.

💡 For n=100000, sorting takes about 1.5 million operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the standard efficient solution expected in interviews.

🧠

Greedy with Early Exit Optimization

💡 This approach is a minor optimization of the two-pointer method by exiting early when all children are assigned, improving runtime slightly.

Intuition

Once all children are assigned cookies, no need to continue checking remaining cookies.

Algorithm

1. Sort greed and cookie arrays.
2. Initialize two pointers and count.
3. While pointers are valid and count less than number of children, assign cookies greedily.
4. Return count.

💡 This approach avoids unnecessary iterations once all children are satisfied.

</>

Code

def findContentChildren(g, s):
    g.sort()
    s.sort()
    i = j = count = 0
    while i < len(g) and j < len(s) and count < len(g):
        if s[j] >= g[i]:
            count += 1
            i += 1
            j += 1
        else:
            j += 1
    return count

# Driver code
if __name__ == '__main__':
    g = [1,2,3]
    s = [1,1]
    print(findContentChildren(g, s))  # Output: 1

Line Notes

while i < len(g) and j < len(s) and count < len(g)Stop early if all children are assigned.

if s[j] >= g[i]Assign cookie if it satisfies the child's greed.

count += 1Increment count when a child is assigned a cookie.

i += 1; j += 1Move both pointers forward after assignment.

import java.util.*;
public class AssignCookies {
    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0, count = 0;
        while (i < g.length && j < s.length && count < g.length) {
            if (s[j] >= g[i]) {
                count++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int[] g = {1,2,3};
        int[] s = {1,1};
        System.out.println(findContentChildren(g, s)); // Output: 1
    }
}

Line Notes

while (i < g.length && j < s.length && count < g.length)Stop early when all children are assigned.

if (s[j] >= g[i])Assign cookie if it satisfies the child's greed.

count++Increment count for each successful assignment.

i++; j++;Move pointers forward after assignment.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int i = 0, j = 0, count = 0;
    while (i < g.size() && j < s.size() && count < g.size()) {
        if (s[j] >= g[i]) {
            count++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    return count;
}

int main() {
    vector<int> g = {1,2,3};
    vector<int> s = {1,1};
    cout << findContentChildren(g, s) << endl; // Output: 1
    return 0;
}

Line Notes

while (i < g.size() && j < s.size() && count < g.size())Stop early if all children are assigned.

if (s[j] >= g[i])Assign cookie if it satisfies the child's greed.

count++Increment count for each assignment.

i++; j++;Advance pointers after assignment.

function findContentChildren(g, s) {
    g.sort((a,b) => a - b);
    s.sort((a,b) => a - b);
    let i = 0, j = 0, count = 0;
    while (i < g.length && j < s.length && count < g.length) {
        if (s[j] >= g[i]) {
            count++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    return count;
}

// Test
console.log(findContentChildren([1,2,3], [1,1])); // Output: 1

Line Notes

while (i < g.length && j < s.length && count < g.length)Stop early when all children are assigned.

if (s[j] >= g[i])Assign cookie if it satisfies the child's greed.

count++Increment count for each successful assignment.

i++; j++;Move pointers forward after assignment.

⏱

Complexity

TimeO(n log n + m log m) due to sorting, with a slightly faster linear assignment

SpaceO(1) or O(n + m) depending on sorting implementation

Early exit can save some iterations but does not change asymptotic complexity.

💡 This optimization is useful in practice but not required to pass interviews.

Interview Verdict: Accepted

This is a minor optimization of the standard greedy approach.

📊

All Approaches - One-Glance Tradeoffs

💡 The sorting + two-pointer greedy approach is the best to code in interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*m)	O(m)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Two Pointers	O(n log n + m log m)	O(1) or O(n + m)	No	N/A	Code this approach for optimal solution
3. Greedy with Early Exit	O(n log n + m log m)	O(1) or O(n + m)	No	N/A	Mention as minor optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Present the brute force approach to show understanding.Step 3: Explain the inefficiency and introduce sorting + two pointers.Step 4: Code the optimized solution carefully.Step 5: Test with edge cases and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to recognize greedy patterns, optimize brute force, and write clean, correct code.

Common Follow-ups

• What if cookies can be split? → Use a different approach, possibly DP or greedy with fractions.
• What if children can have multiple cookies? → Adjust logic to assign multiple cookies per child.

💡 These follow-ups test your ability to adapt the greedy approach to variations.

🔍

Pattern Recognition

When to Use

1) You have two arrays representing demands and supplies. 2) You want to maximize assignments or satisfaction. 3) Each supply can be assigned at most once. 4) Greedy assignment by sorting is possible.

Signature Phrases

'maximize the number of content children''each cookie can be assigned to at most one child'

NOT This Pattern When

Knapsack problems - those require DP due to value-weight tradeoffs, not simple greedy assignment.

Similar Problems

Two Sum - both use two-pointer after sortingMeeting Rooms - scheduling with greedy assignmentMinimum Number of Arrows to Burst Balloons - greedy interval assignment

Practice

1. Consider the following BFS-based jump function. What is the returned value when calling jump([2,1,1,1,4])?

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace first BFS level

   Start at index 0 with jump length 2, enqueue indices 1 and 2, jumps = 1.

2. Step 2: Trace second BFS level

   From indices 1 and 2, enqueue reachable indices: from 1 (jump 1) -> 2 (visited), from 2 (jump 1) -> 3, jumps = 2.

3. Step 3: Trace third BFS level

   From index 3 (jump 1), enqueue index 4 (last index), jumps = 3, return 3.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Minimum jumps to reach end is 3 [OK]

Hint: Count BFS levels until last index reached [OK]

Common Mistakes:

• Off-by-one error in counting jumps
• Returning jumps too early
• Miscounting reachable indices

2. You have different types of boxes, each with a number of boxes and units per box. You want to load a truck with a limited capacity to maximize total units. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer by splitting box types and merging results

B. Greedy algorithm sorting box types by units per box in descending order and picking boxes until the truck is full

C. Breadth-first search exploring all possible box selections up to truck capacity

D. Dynamic programming considering all combinations of boxes and capacities

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing units loaded on a truck with limited capacity by selecting boxes with different units per box.

2. Step 2: Identify optimal approach

   Since the problem involves discrete box counts and a capacity constraint, the greedy approach does not always guarantee an optimal solution. Dynamic programming considering all combinations ensures the optimal solution by exploring all feasible selections.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP guarantees optimality for knapsack-like problems with discrete items [OK]

Hint: Use DP for discrete knapsack problems to guarantee optimality [OK]

Common Mistakes:

• Assuming greedy always works
• Trying BFS which is inefficient
• Ignoring capacity constraints

3. Consider the following buggy code for partitioning labels. Which line contains the subtle bug that can cause incorrect partitions?

def partitionLabels(s):
    last = [0] * 26
    for i, c in enumerate(s):
        last[ord(c) - ord('a')] = i
    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = last[ord(c) - ord('a')]  # Bug here: missing max()
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

medium

A. Line 3: Updating last occurrence map

B. Line 13: Calculating partition size with end - start + 1

C. Line 8: Initializing end to 0

D. Line 11: Updating end without taking max

Solution

1. Step 1: Understand role of end variable

   End must track the furthest last occurrence of any character seen so far to avoid premature partitioning.

2. Step 2: Identify bug in updating end

   Assigning end directly to last occurrence of current character without max() loses track of previous furthest last occurrence, causing incorrect partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing max() causes partitions to cut too early [OK]

Hint: Always update end = max(end, last[c]) [OK]

Common Mistakes:

• Forgetting max() when updating partition end
• Off-by-one errors in partition size calculation
• Not precomputing last occurrences

4. What is the time complexity of the optimal greedy algorithm for the wiggle subsequence problem, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because it scans the list once, updating counters based on difference signs

B. O(2^n) because it explores all subsequences recursively

C. O(n log n) due to sorting or binary search steps involved

D. O(n^2) because it compares each element with all previous elements

Solution

1. Step 1: Analyze algorithm operations

   The greedy algorithm iterates through the list once, computing differences and updating counters in O(1) time per element.

2. Step 2: Address common misconceptions

   Some candidates confuse it with brute force or DP approaches, thinking it compares pairs or explores subsequences exponentially, leading to O(n^2) or O(2^n) assumptions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant work per element -> O(n) [OK]

Hint: Single pass with constant updates -> O(n)

Common Mistakes:

• Confusing with brute force exponential time
• Assuming nested loops for comparisons
• Thinking sorting is involved

5. Suppose the problem is modified so that dominoes can be rotated multiple times (reused) to achieve uniformity, or the arrays can contain values outside 1-6. Which approach correctly adapts the solution?

hard

A. Check all unique values appearing in either array as candidates with early exit

B. Continue checking only the first domino's two values as candidates, ignoring others

C. Use dynamic programming to track rotations for all possible values 1 to 6 only

D. Sort arrays and greedily pick the most frequent value to minimize rotations

Solution

1. Step 1: Identify candidate values

   With values outside 1-6 and reuse allowed, candidates are all unique values in A and B, not just first domino.

2. Step 2: Check feasibility for each candidate

   For each candidate, verify if all dominoes can be rotated to match it, counting minimal rotations.

3. Step 3: Early exit optimization

   Stop checking candidates as soon as a valid minimal rotation count is found.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Checking all unique values covers extended domain and reuse [OK]

Hint: Check all unique values when domain expands [OK]

Common Mistakes:

• Checking only first domino candidates
• Limiting candidates to 1-6 values only