Assign Cookies solution and explanation
Google
TCS
9 more videos on this problem
L1. Assign Cookies | Greedy Algorithm Playlisttake U forward · 10:51 · 471K views
Assign Cookies - Leetcode 455 - PythonNeetCodeIO · 9:06 · 24K views
Assign Cookies | Google | C++ | JAVA | Leetcode 455codestorywithMIK · 14:49 · 11K views
LeetCode 455. Assign Cookies Solution Explained - JavaNick White · 7:34 · 9K views
455. Assign Cookies | Leetcode | Easy | Java | Greedy Algorithm | Striver's A to Z DSA Sheet/CourseAlgorithmHQ · 10:25 · 2K views
455. Assign Cookies | GreedyAryan Mittal · 12:21 · 2K views
Leetcode | 455. Assign Cookies | Easy | Java SolutionDeveloper Docs · 4:04 · 1K views
455. Assign Cookies - LeetCode JavaScriptBecoming A Better Dev (with David) · 11:42 · 247 views
455. Assign Cookies (Leetcode Easy)Programming Live with Larry · 14:12 · 244 views
HOW TO Assign Cookies - Leetcode 455Lit Code · 5:03 · 183 views
The 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.
Example 1:
Input: g = [1,2,3], s = [1,1] Output: 1 Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.
Example 2:
Input: g = [1,2], s = [1,2,3] Output: 2 Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. You have 3 cookies and their sizes are big enough to gratify all of the children, You need to output 2.
Constraints:
1 <= g.length <= 3 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 1
Note: This question is the same as 2410: Maximum Matching of Players With Trainers.
Approach overview
Problem Overview: Each child has a greed factor g[i] and each cookie has a size s[j]. A child is satisfied only if the cookie size is greater than or equal to their greed factor. Each cookie can be assigned to only one child. The task is to maximize the number of satisfied children.
Approach 1: Greedy with Sorting + Two Pointers (O(n log n + m log m) time, O(1) space)
The key observation: smaller cookies should go to children with the smallest greed first. If you give a large cookie to a less greedy child early, you may waste it and fail to satisfy a greedier child later. Sort both arrays, then walk through them using two pointers. One pointer tracks children, the other tracks cookies. If the current cookie satisfies the child (s[j] >= g[i]), assign it and move both pointers. Otherwise, move the cookie pointer to try a larger cookie. Sorting ensures you always attempt the smallest feasible assignment first.
This approach relies on a classic greedy strategy combined with sorting. Each cookie and child is processed once after sorting, so the pointer traversal is linear. The sorting step dominates the runtime.
Approach 2: Greedy with Sorting + Binary Search (O(n log n + m log m + n log m) time, O(1) space)
Another strategy is to still sort both arrays but locate cookies using binary search. For each child (processed from smallest greed to largest), perform a binary search on the cookie array to find the smallest unused cookie that satisfies the greed factor. Once found, mark it as used and move to the next child. This works because sorting keeps the cookies ordered, allowing efficient lookup.
This version replaces the linear two‑pointer scan with repeated binary searches. While conceptually straightforward, it is slightly slower because each child may trigger a log m search. The method still follows the same greedy rule: assign the smallest valid cookie so larger ones remain available for greedier children. It demonstrates how array ordering enables efficient selection strategies.
Recommended for interviews: The sorting + two pointers greedy solution is the expected answer. It is simple, optimal, and demonstrates clear greedy reasoning. Interviewers usually want to see the insight that matching the smallest cookie with the least greedy child avoids wasting resources. The binary search variant works but adds unnecessary overhead compared to the clean linear scan.
Approach 1: Greedy Approach using Sorting
This approach involves sorting the greed factors and cookie sizes. By sorting, the goal is to try to satisfy the least greedy child first with the smallest satisfying cookie. By continuing this way, the solution can maximize the number of content children.
The solution uses two pointers, one for the greed list (g) and one for the cookie size list (s). It increments the pointer for the children only when a matching cookie is found.
def findContentChildren(g, s):
g.sort()
s.sort()
i, j = 0, 0
while i < len(g) and j < len(s):
if s[j] >= g[i]:
i += 1
j += 1
return i
print(findContentChildren([1, 2, 3], [1, 1]))import java.util.Arrays;
public class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) {
i++;
}
j++;
}
return i;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] g = {1, 2, 3};
int[] s = {1, 1};
System.out.println(solution.findContentChildren(g, s));
}
}#include <vector>
#include <algorithm>
#include <iostream>
class Solution {
public:
int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
std::sort(g.begin(), g.end());
std::sort(s.begin(), s.end());
int i = 0, j = 0;
while (i < g.size() && j < s.size()) {
if (s[j] >= g[i]) {
i++;
}
j++;
}
return i;
}
};
int main() {
Solution solution;
std::vector<int> g = {1, 2, 3};
std::vector<int> s = {1, 1};
int result = solution.findContentChildren(g, s);
std::cout << result << std::endl;
return 0;
}function findContentChildren(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let i = 0, j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) {
i++;
}
j++;
}
return i;
}
console.log(findContentChildren([1, 2, 3], [1, 1]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int findContentChildren(int* g, int gSize, int* s, int sSize) {
qsort(g, gSize, sizeof(int), compare);
qsort(s, sSize, sizeof(int), compare);
int i = 0, j = 0;
while (i < gSize && j < sSize) {
if (s[j] >= g[i]) {
i++;
}
j++;
}
return i;
}
int main() {
int g[] = {1, 2, 3};
int s[] = {1, 1};
int result = findContentChildren(g, 3, s, 2);
printf("%d\n", result);
return 0;
}using System;
class Program {
public static int FindContentChildren(int[] g, int[] s) {
Array.Sort(g);
Array.Sort(s);
int i = 0, j = 0;
while (i < g.Length && j < s.Length) {
if (s[j] >= g[i]) {
i++;
}
j++;
}
return i;
}
static void Main() {
int[] g = {1, 2, 3};
int[] s = {1, 1};
Console.WriteLine(FindContentChildren(g, s));
}
}In this Python solution, the arrays are sorted and simple loop through both arrays is employed. The Python built-in sorting function is used to handle the sorting, and pointer increments help us track satisfied children.
Time Complexity: O(n log n + m log m), as it depends on sorting both arrays.
Space Complexity: O(1) additional space from the solution logic.
Approach 2: Greedy Approach with Binary Search
This involves using binary search to attempt to find the proper index in the sorted list `s` where a given greed factor `g[i]` meets the condition.
For each child in the sorted greed list, perform binary search over the sorted cookie sizes to find the smallest suitable cookie. We'll mark the cookie as used by logically removing it from the pool (using an increment of the index pointer).
import bisect
def findContentChildren(g, s):
g.sort()
s.sort()
content_children = 0
for greed in g:
index = bisect.bisect_left(s, greed)
if index < len(s):
content_children += 1
s.pop(index)
return content_children
print(findContentChildren([1, 2, 3], [1, 1]))import java.util.*;
public class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int contentChildren = 0, cookieIndex = 0;
for (int i = 0; i < g.length; i++) {
while (cookieIndex < s.length && s[cookieIndex] < g[i]) {
cookieIndex++;
}
if (cookieIndex < s.length) {
contentChildren++;
cookieIndex++;
}
}
return contentChildren;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] g = {1, 2, 3};
int[] s = {1, 1};
System.out.println(solution.findContentChildren(g, s));
}
}#include <vector>
#include <algorithm>
#include <iostream>
class Solution {
public:
int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
std::sort(g.begin(), g.end());
std::sort(s.begin(), s.end());
size_t j = 0;
int i = 0;
for(i = 0; i < g.size() && j < s.size(); ++i){
j = std::lower_bound(s.begin() + j, s.end(), g[i]) - s.begin();
if(j < s.size()) j++;
}
return i - (j <= s.size());
}
};
int main() {
Solution solution;
std::vector<int> g = {1, 2, 3};
std::vector<int> s = {1, 1};
int result = solution.findContentChildren(g, s);
std::cout << result << std::endl;
return 0;
}function findContentChildren(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let contentChildren = 0;
let cookieIndex = 0;
for (let greedy of g) {
while (cookieIndex < s.length && s[cookieIndex] < greedy) {
cookieIndex++;
}
if (cookieIndex < s.length) {
contentChildren++;
cookieIndex++;
}
}
return contentChildren;
}
console.log(findContentChildren([1, 2, 3], [1, 1]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int binarySearch(int *s, int size, int target) {
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (s[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
int findContentChildren(int* g, int gSize, int* s, int sSize) {
qsort(g, gSize, sizeof(int), compare);
qsort(s, sSize, sizeof(int), compare);
int content = 0;
for (int i = 0; i < gSize; i++) {
int index = binarySearch(s, sSize, g[i]);
if (index < sSize) {
content++;
s[index] = 0; // Mark as used, or move index forward.
}
}
return content;
}
int main() {
int g[] = {1, 2, 3};
int s[] = {1, 1};
int result = findContentChildren(g, 3, s, 2);
printf("%d\n", result);
return 0;
}using System;
class Program {
public static int FindContentChildren(int[] g, int[] s) {
Array.Sort(g);
Array.Sort(s);
int contentChildrenCount = 0;
int cookieIndex = 0;
foreach (int greed in g) {
while (cookieIndex < s.Length && s[cookieIndex] < greed) {
cookieIndex++;
}
if (cookieIndex < s.Length) {
contentChildrenCount++;
cookieIndex++;
}
}
return contentChildrenCount;
}
static void Main() {
int[] g = {1, 2, 3};
int[] s = {1, 1};
Console.WriteLine(FindContentChildren(g, s)); // Output: 1
}
}The Python solution exemplifies Binary Search by using the `bisect` library for search to check within the cookies, ensuring each satisfied greed instantly reduces the total sizes at that state.
Time Complexity: O(n log n + n log m), on account of array order and searching.
Space Complexity: O(1) plus input size.
Approach 3: Sorting + Two Pointers
According to the problem description, we should prioritize giving cookies to children with smaller appetites, so as to satisfy as many children as possible.
Therefore, we first sort the two arrays, and then use two pointers i and j to point to the head of arrays g and s respectively. Each time we compare the size of g[i] and s[j]:
- If
s[j] < g[i], it means that the current cookies[j]cannot satisfy the current childg[i]. We should allocate a larger cookie to the current child, sojshould move to the right by one. Ifjgoes out of bounds, it means that the current child cannot be satisfied. At this time, the number of successfully allocated children isi, and we can return directly. - If
s[j] \ge g[i], it means that the current cookies[j]can satisfy the current childg[i]. We allocate the current cookie to the current child, so bothiandjshould move to the right by one.
If we have traversed the array g, it means that all children have been allocated cookies, and we can return the total number of children.
The time complexity is O(m times log m + n times log n), and the space complexity is O(log m + log n). Where m and n are the lengths of arrays g and s respectively.
function findContentChildren(g: number[], s: number[]): number {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
const m = g.length;
const n = s.length;
for (let i = 0, j = 0; i < m; ++i) {
while (j < n && s[j] < g[i]) {
++j;
}
if (j++ >= n) {
return i;
}
}
return m;
}func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
j := 0
for i, x := range g {
for j < len(s) && s[j] < x {
j++
}
if j >= len(s) {
return i
}
j++
}
return len(g)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach using Sorting | Time Complexity: O(n log n + m log m), as it depends on sorting both arrays. Space Complexity: O(1) additional space from the solution logic. |
| Greedy Approach with Binary Search | Time Complexity: O(n log n + n log m), on account of array order and searching. Space Complexity: O(1) plus input size. |
| Sorting + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting + Two Pointers | O(n log n + m log m) | O(1) | Best general solution. Simple, optimal, and commonly expected in interviews. |
| Greedy with Sorting + Binary Search | O(n log n + m log m + n log m) | O(1) | Useful when demonstrating binary search over sorted arrays or when direct pointer scanning is not used. |
Frequently asked questions
Is Assign Cookies easy or hard?
Assign Cookies is classified as an easy problem on LeetCode. The main challenge is recognizing the greedy insight that smaller cookies should satisfy less greedy children first. Once that idea is clear, the implementation using sorting and two pointers is straightforward.
Assign Cookies Python/Java solution
In Python or Java, the standard solution sorts both arrays and uses two indices to iterate through children and cookies. When the cookie size is greater than or equal to the greed factor, increment the satisfied count and move both pointers. Otherwise move only the cookie pointer. This implementation runs in O(n log n) time.
How to solve Assign Cookies in O(n)?
A pure O(n) solution is only possible if both arrays are already sorted. In that case, use a two‑pointer greedy scan: move through children and cookies simultaneously and assign a cookie whenever its size meets the child's greed factor. Without pre-sorted arrays, sorting is required, which increases complexity to O(n log n).
What is the best approach for Assign Cookies?
The best approach uses a greedy strategy with sorting and two pointers. Sort the greed array and the cookie sizes, then iterate through both while assigning the smallest cookie that satisfies the current child. This avoids wasting large cookies on less greedy children and maximizes the number of satisfied kids. The time complexity is O(n log n + m log m) due to sorting.
Is Assign Cookies asked at Google/Amazon/Meta?
Assign Cookies is a common easy-level greedy problem frequently used in coding screens and practice sets. Variants of resource allocation and greedy matching appear in interviews at companies like Amazon and Google. The problem tests understanding of sorting, greedy decisions, and two-pointer techniques.
What data structure is used in Assign Cookies?
The solution primarily uses arrays along with sorting and a two-pointer traversal. No advanced data structures are required. The greedy logic depends on ordering the arrays and scanning them efficiently.
What is the time complexity of Assign Cookies?
The optimal solution runs in O(n log n + m log m) time because both the greed array and cookie array must be sorted. After sorting, a single linear scan with two pointers processes each child and cookie once. The space complexity is O(1) if sorting is done in place.