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. You are given a string and need to rearrange its characters so that no two adjacent characters are the same. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm using a max heap (priority queue) to always pick the most frequent character available next

B. Dynamic Programming that counts character frequencies and tries all permutations

C. Simple sorting of characters and placing them in alternating positions without frequency checks

D. Backtracking by generating all permutations and checking adjacency constraints

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging characters so no two adjacent are the same, which demands careful ordering based on frequency.

2. Step 2: Identify approach that guarantees optimality

   Greedy approach with a max heap always picks the most frequent character available that is not the previously used one, ensuring no adjacency violation and optimal placement.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap approach is standard and optimal for this problem [OK]

Hint: Max heap greedily picks highest frequency char [OK]

Common Mistakes:

• Assuming simple sorting suffices
• Thinking backtracking is efficient here
• Confusing DP with greedy

2. What is the worst-case time complexity of the BFS-based solution for Jump Game II on an input array of length n?

medium

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(n^3)

Solution

1. Step 1: Identify outer and inner loops

   The BFS processes each index once, but for each index, it may enqueue up to nums[pos] next positions, which can be up to n.

2. Step 2: Analyze nested iteration

   In worst case (e.g., nums[i] = n for all i), inner loop runs O(n) times for each of O(n) indices -> O(n^2) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over n indices and jumps -> O(n^2) [OK]

Hint: Nested loops over n indices and jumps -> O(n^2) [OK]

Common Mistakes:

• Assuming BFS is always O(n)
• Confusing with greedy linear time
• Ignoring inner loop over jump range

3. What is the time complexity of the optimal single-pass greedy solution for the Minimum Domino Rotations problem, given arrays of length n?

medium

A. O(6 * n) because it checks all numbers 1 to 6

B. O(n^2) due to nested loops over dominoes and candidates

C. O(n) because it only checks two candidate values with a single pass

D. O(1) since it only checks the first domino values

Solution

1. Step 1: Identify loops in the code

   The code checks at most two candidates (A[0] and B[0]) and iterates once over all n dominoes per candidate.

2. Step 2: Calculate total operations

   Each candidate check is O(n), so total is O(2 * n) = O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only two passes over n elements -> linear time [OK]

Hint: Only two candidates checked, linear scan each [OK]

Common Mistakes:

• Assuming all 6 numbers checked -> O(6n)
• Confusing nested loops causing O(n^2)

4. What is the time complexity of the optimal greedy algorithm using a stack to remove k digits from a number string of length n to get the smallest number?

medium

A. O(n) because each digit is pushed and popped at most once

B. O(n^2) because nested loops are needed to find digits to remove

C. O(n log n) due to sorting digits internally

D. O(n * k) because each digit can cause up to k pops

Solution

1. Step 1: Identify operations per digit

   Each digit is pushed onto the stack once and can be popped at most once when a smaller digit arrives.

2. Step 2: Analyze total operations

   Since each push and pop happens at most once per digit, total operations are proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack operations are linear in n, no nested loops [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Confusing with sorting complexity
• Thinking nested loops are needed

5. Suppose the problem is modified: instead of finding the largest monotone increasing digits number ≤ n, you want the largest monotone increasing digits number ≤ n that can reuse digits any number of times (digits can be repeated arbitrarily). Which approach correctly adapts the algorithm?

hard

A. Use the original greedy algorithm but allow digits after marker to be any digit less than or equal to the digit at marker-1

B. Sort the digits of n and build the largest monotone number by repeating the smallest digit as many times as needed

C. Use a backtracking approach to generate all monotone numbers with digits ≤ those in n, allowing reuse, and pick the largest ≤ n

D. Modify the greedy algorithm to decrement digits and set trailing digits to the digit at marker-1 instead of 9

Solution

1. Step 1: Understand digit reuse changes problem nature

   Allowing reuse means digits can be repeated arbitrarily, so greedy digit decrement and trailing 9 assignment no longer guarantee largest monotone number ≤ n.

2. Step 2: Backtracking enumerates all monotone numbers with digit reuse

   Backtracking can generate all monotone numbers with digits ≤ those in n, allowing reuse, then pick the largest ≤ n.

3. Step 3: Other options fail to handle reuse or produce incorrect numbers

   Sorting digits or modifying trailing digits to marker-1 digit does not guarantee largest monotone number with reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Backtracking correctly handles reuse and monotonicity constraints [OK]

Hint: Digit reuse breaks greedy; backtracking needed for correctness [OK]

Common Mistakes:

• Trying to adapt greedy without full enumeration
• Assuming trailing digits can be set to 9 or marker digit
• Ignoring exponential complexity of reuse