Skip to main content
Talentd

Assign Cookies - Solution & Explanation

EasyArrayTwo PointersGreedySorting22 min readAsked at: Amazon, Microsoft, Apple +6
Practice this problem

Problem Statement

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 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= 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.

This C solution sorts both arrays and uses a two-pointer technique. It keeps a pointer on both the greed factors array and the cookie sizes array. By incrementing both pointers when a child is satisfied, it ensures that all possible cookies are used optimally.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n + m log m), where n is the number of children and m is the number of cookies (due to sorting).

Space Complexity: O(1), as it uses a constant amount of extra space apart from the input arrays.

Try this approach in the editor →

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).

This C solution follows the Binary Search technique. It leverages sorting both arrays, then searching for the smallest valid cookie for each child using binary search. It updates counters and marks cookies to avoid reuse improperly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n + n log m), where n is the number of the greed array, m is the number of cookie size array, originating from sorting and binary searching through the cookies.

Space Complexity: O(1) when not considering input arrays.

Try this approach in the editor →

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 cookie s[j] cannot satisfy the current child g[i]. We should allocate a larger cookie to the current child, so j should move to the right by one. If j goes out of bounds, it means that the current child cannot be satisfied. At this time, the number of successfully allocated children is i, and we can return directly.
  • If s[j] \ge g[i], it means that the current cookie s[j] can satisfy the current child g[i]. We allocate the current cookie to the current child, so both i and j should 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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach using Sorting

Time Complexity: O(n log n + m log m), where n is the number of children and m is the number of cookies (due to sorting).

Space Complexity: O(1), as it uses a constant amount of extra space apart from the input arrays.

Greedy Approach with Binary Search

Time Complexity: O(n log n + n log m), where n is the number of the greed array, m is the number of cookie size array, originating from sorting and binary searching through the cookies.

Space Complexity: O(1) when not considering input arrays.

Sorting + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Sorting + Two PointersO(n log n + m log m)O(1)Best general solution. Simple, optimal, and commonly expected in interviews.
Greedy with Sorting + Binary SearchO(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.

Video Solution

L1. Assign Cookies | Greedy Algorithm Playlist • take U forward • 471,529 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Assign Cookies with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays