Assign Cookies
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 greed[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size cookies[j]. If cookies[j] >= greed[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.
Examples
Input: greed = [1,2,3], cookies = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, and 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.
Input: greed = [1,2], cookies = [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 <= greed.length <= 3 * 10⁴
0 <= cookies.length <= 3 * 10⁴
1 <= greed[i], cookies[j] <= 2³¹ - 1
Brute Force Approach
After reading the question, we understand that it asks us to find the number of children whose greed can be satisfied.
Given the greed factor of each child and the sizes of the cookies, we need to assign the cookies in such a way that the maximum number of children are satisfied with their greed.
So how can we do that?
Here comes the intuition behind the problem
Intuition
To assign the cookies to the children, the greedy approach suggests that for each child, we should find the smallest cookie that is large enough to satisfy their greed, ensuring that the number of satisfied children is maximized. By always assigning the smallest valid cookie, larger cookies are preserved for greedier children, ensuring optimal distribution and maximizing the number of satisfied children.
So now how can we find the smallest cookie for each children?
Approach
The approach starts by initializing a visited array (vis), where each index corresponds to a cookie. The value at each index is initially set to 0, indicating that the cookie has not been assigned yet. This array will help track which cookies have been used and prevent them from being reassigned to other children.
For each child, the algorithm searches through all available cookies to find the smallest cookie that satisfies the child's greed. This is done by comparing the child's greed factor greed[i] with the size of each cookie cookies[j]. If the current cookie is large enough to satisfy the child and hasn't been used yet (i.e., vis[j] == 0), the algorithm selects that cookie for the child.
Once a valid cookie is found, it is marked as "used" by updating the vis array at the corresponding index (vis[j] = 1). This prevents the same cookie from being assigned to another child. After assigning the cookie to the current child, the algorithm moves on to the next child and repeats the process.
By using the visited array, the algorithm ensures that each cookie can only be assigned to one child, and it efficiently finds the smallest available cookie that meets the child's greed. This strategy guarantees that the maximum number of children are satisfied with the available cookies.
Let's Understand with an example
Given:
- greed = [1, 2] (greed factors of the children)
- cookies = [1, 2, 3] (sizes of the available cookies)
The brute force approach involves iterating over each child and trying to find the smallest possible cookie that satisfies that child's greed. Here's how we would do that step by step:
Brute Force Approach:
- Initialize Variables:
- vis = [0, 0, 0] (This array keeps track of which cookies have been used; 0 means unused, 1 means used).
- (This variable counts the number of satisfied children).
- Iterate Over Each Child:
- Start with the first child (greed[0] = 1).
- We need to find a cookie whose size is at least 1 and has not been used yet.
- For the first child, iterate through all the cookies (cookies = [1, 2, 3]):
- Check cookies[0] = 1: Since greed[0] = 1, this cookie can satisfy the child. So, assign cookies[0] to this child.
- Update vis = [1, 0, 0] (mark cookie cookies[0] as used).
- Increment childrencount = 1 (the child is satisfied).
- Now, move to the next child.
- We need to find a cookie whose size is at least 2 and has not been used yet.
- For the second child, iterate through all the cookies (cookies = [1, 2, 3]):
- Check cookies[0] = 1: This cookie is already used (as vis[0] = 1), so skip it.
- Check cookies[1] = 2: Since greed[1] = 2, this cookie can satisfy the child. Assign cookies[1] to this child.
- Update vis = [1, 1, 0] (mark cookie cookies[1] as used).
- Increment childrencount = 2 (the second child is satisfied).
- Now, move to the next child.
- There are no more children to process.
The total childrencount = 2, which is the number of satisfied children
Steps to write code
Step 1: Plan the Approach
- For each child, check every available cookie to find the smallest cookie that satisfies the child's greed.
- Once a cookie is assigned to a child, mark that cookie as used.
- Count how many children are satisfied by this process.
Step 2: Initialize Data Structures
- vis array: This array will track which cookies have been used. If vis[i] = 1, it means the i-th cookie has been used.
- childrencount variable: This variable will count how many children are content.
Step 3: Iterate Over Each Child
- For each child in the greed array, iterate over all cookies in the cookies array and check if the current cookie can satisfy the child (i.e., cookies[j] >= greed[i]).
- If a cookie satisfies the child, assign it and mark it as used.
Step 4: Return the Result
- After all children have been considered, return the value of childrencount, which represents the number of satisfied children.
Code Implementation
C++
class Solution {
public:
int findContentChildren(vector<int>& greed, vector<int>& cookies) {
// Get the number of cookies
int n = cookies.size();
// Get the number of children
int m = greed.size();
// Create a visited array to track if a cookie has already been used
vector<int> vis(n, 0);
// Initialize the count of content children
int childrencount = 0;
// Loop through each child to find a suitable cookie
for (int i = 0; i < m; i++) {
// Variable to store the smallest cookie size that can satisfy the current child
int atleast = INT_MAX;
// Variable to store the index of the chosen cookie for the current child
int idx = -1;
// Loop through all cookies to find the smallest valid cookie
for (int j = 0; j < n; j++) {
// Skip this cookie if it has already been used
if (vis[j] == 1) continue;
// Check if the current cookie size satisfies the child's greed
if (greed[i] <= cookies[j]) {
// Check if the current cookie is smaller than the previously found cookie
if (atleast > cookies[j]) {
// Update the smallest cookie size
atleast = cookies[j];
// Update the index of the chosen cookie
idx = j;
}
}
}
// If a suitable cookie was found for the current child
if (idx != -1) {
// Mark the chosen cookie as used
vis[idx] = 1;
// Increment the count of content children
childrencount++;
}
}
// Return the total number of content children
return childrencount;
}
};
Java
class Solution {
public int findContentChildren(int[] greed, int[] cookies) {
// Get the number of cookies
int n = cookies.length;
// Get the number of children
int m = greed.length;
// Create a visited array to track if a cookie has already been used
boolean[] vis = new boolean[n];
// Initialize the count of content children
int childrencount = 0;
// Loop through each child to find a suitable cookie
for (int i = 0; i < m; i++) {
// Variable to store the smallest cookie size that can satisfy the current child
int atleast = Integer.MAX_VALUE;
// Variable to store the index of the chosen cookie for the current child
int idx = -1;
// Loop through all cookies to find the smallest valid cookie
for (int j = 0; j < n; j++) {
// Skip this cookie if it has already been used
if (vis[j]) continue;
// Check if the current cookie size satisfies the child's greed
if (greed[i] <= cookies[j]) {
// Check if the current cookie is smaller than the previously found cookie
if (atleast > cookies[j]) {
// Update the smallest cookie size
atleast = cookies[j];
// Update the index of the chosen cookie
idx = j;
}
}
}
// If a suitable cookie was found for the current child
if (idx != -1) {
// Mark the chosen cookie as used
vis[idx] = true;
// Increment the count of content children
childrencount++;
}
}
// Return the total number of content children
return childrencount;
}
}
Python
class Solution(object):
def findContentChildren(self, greed, cookies):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
# Get the number of cookies
n = len(cookies)
# Get the number of children
m = len(greed)
# Create a visited array to track if a cookie has already been used
vis = [False] * n
# Initialize the count of content children
childrencount = 0
# Loop through each child to find a suitable cookie
for i in range(m):
# Variable to store the smallest cookie size that can satisfy the current child
atleast = float('inf')
# Variable to store the index of the chosen cookie for the current child
idx = -1
# Loop through all cookies to find the smallest valid cookie
for j in range(n):
# Skip this cookie if it has already been used
if vis[j]: continue
# Check if the current cookie size satisfies the child's greed
if greed[i] <= cookies[j]:
# Check if the current cookie is smaller than the previously found cookie
if atleast > cookies[j]:
# Update the smallest cookie size
atleast = cookies[j]
# Update the index of the chosen cookie
idx = j
# If a suitable cookie was found for the current child
if idx != -1:
# Mark the chosen cookie as used
vis[idx] = True
# Increment the count of content children
childrencount += 1
# Return the total number of content children
return childrencount
Javascript
/**
* @param {number[]} greed
* @param {number[]} cookies
* @return {number}
*/
var findContentChildren = function(greed, cookies) {
// Get the number of cookies
let n = cookies.length;
// Get the number of children
let m = greed.length;
// Create a visited array to track if a cookie has already been used
let vis = new Array(n).fill(false);
// Initialize the count of content children
let childrencount = 0;
// Loop through each child to find a suitable cookie
for (let i = 0; i < m; i++) {
// Variable to store the smallest cookie size that can satisfy the current child
let atleast = Infinity;
// Variable to store the index of the chosen cookie for the current child
let idx = -1;
// Loop through all cookies to find the smallest valid cookie
for (let j = 0; j < n; j++) {
// Skip this cookie if it has already been used
if (vis[j]) continue;
// Check if the current cookie size satisfies the child's greed
if (greed[i] <= cookies[j]) {
// Check if the current cookie is smaller than the previously found cookie
if (atleast > cookies[j]) {
// Update the smallest cookie size
atleast = cookies[j];
// Update the index of the chosen cookie
idx = j;
}
}
}
// If a suitable cookie was found for the current child
if (idx !== -1) {
// Mark the chosen cookie as used
vis[idx] = true;
// Increment the count of content children
childrencount++;
}
}
// Return the total number of content children
return childrencount;
};
Time Complexity: O(m×n)
The function has two nested loops:
- Outer loop (over children):
- The outer loop iterates through each child in the greed array.
- For each child, the function tries to find a suitable cookie by iterating over all cookies. Hence, the outer loop runs m times, where m is the number of children.
- Inner loop (over cookies):
- The inner loop iterates through each cookie in the cookies array for every child in the outer loop.
- It checks if the cookie is not already used (by checking the vis array) and if the cookie can satisfy the child's greed.
- Therefore, for each child, the inner loop runs n times, where n is the number of cookies.
Total Time Complexity:
The outer loop runs m times (one for each child), and for each iteration of the outer loop, the inner loop runs n times (one for each cookie). Hence, the total time complexity is: O(m×n)
Space Complexity: O(n)
Let's Analyse it
1. Input Arrays:
- greed has m elements (the number of children).
- cookies has n elements (the number of cookies).
- The space taken by these arrays is not considered in the space complexity, because they are input data.
- vis Array:
- The vis array tracks whether each cookie has been assigned. It has a size of n (the number of cookies), so the space complexity for this array is O(n).
3. Auxiliary Variables:
- The other variables such as n, m, childrencount, atleast, and idx take up constant space, which is O(1).
Total Space Complexity:
When we sum up the space complexities of the various components:
- Input arrays: They do not contribute to space complexity.
- vis array: O(n), where n is the number of cookies.
- Other scalar variables: O(1).
Thus, the overall space complexity of the algorithm is dominated by the vis array and is: O(n)
Will this run under given constraints?
For the current solution, the time complexity is O(m×n), which is not suitable for n,m ≤ 3*10⁴. This means that for each test case, where the size of the array is at most 3*10⁴, the solution might not execute within the given time limits.
Since O(m×n) results in a maximum of 9*10⁸ operations (for n=3*10⁴,m=3*10⁴), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 9*10⁸ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 9*10⁸ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(m×n) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Optimal Approach
Since in the previous approach, our time complexity is O(n*m), now can we optimize it?
Yes, the previous approach has a time complexity of O(n * m) due to the nested loops—one iterating over the children and the other over the cookies. However, we can optimize this solution to reduce the time complexity.
Since we are aiming to maximize the number of satisfied children, sorting both the greed array (representing the children's greed) and the cookies array (representing the available cookie sizes) is essential for an efficient solution. By sorting the greed array in ascending order, we ensure that we first attempt to satisfy the least greedy child. Similarly, sorting the cookies array in ascending order allows us to always start with the smallest available cookie, ensuring we give the least greedy child the smallest cookie that can satisfy their greed.
This allows us to use a more efficient approach with a two-pointer technique.
After sorting, we can iterate through both arrays using two pointers. One pointer will track the current child (childIndex), and the other will track the current cookie (cookieIndex).
For each child, we check if the current cookie satisfies their greed. If it does, we assign that cookie to the child and move both pointers forward. If the cookie is too small, we move only the cookie pointer forward to find a larger cookie for the current child.
This reduces the number of checks we need to perform since we no longer need to check every cookie for every child. Instead, we are able to process both arrays in a single pass.
Let's Understand it with an example
Here, we are working with:
- Greed array (greed): [1, 2] (children's greed levels).
- Cookies array (cookies): [1, 2, 3] (available cookies).
- Initial Pointers:
- childIndex = 0 (pointing to the first child with greed greed[0] = 1).
- cookieIndex = 0 (pointing to the first cookie with size cookies[0] = 1).
- childrencount = 0 (no children are satisfied yet).
- First Iteration:
- Current child (greed[childIndex] = 1) wants a cookie of size 1 or more.
- Current cookie (cookies[cookieIndex] = 1) is of size 1, which satisfies the child's greed because 1 >= 1.
- Assign this cookie to the child:
- Increment childrencount: Now childrencount = 1.
- Move to the next child: childIndex = 1.
- Move to the next cookie: cookieIndex = 1.
- Second Iteration:
- Current child (greed[childIndex] = 2) wants a cookie of size 2 or more.
- Current cookie (cookies[cookieIndex] = 2) is of size 2, which satisfies the child's greed because 2 >= 2.
- Assign this cookie to the child:
- Increment childrencount: Now childrencount = 2.
- Move to the next child: childIndex = 2.
- Move to the next cookie: cookieIndex = 2.
- End of Iteration:
- We have now matched all the children (childIndex = 2), and no more children are left to process.
- We still have one cookie left (cookieIndex = 2), but since all children are already matched, we do not need to process it.
- Final Result:
- childrencount = 2, meaning both children have received a cookie that satisfies their greed.
How to to code it up?
Sort the greed and cookies arrays:
- Sorting the greed array ensures that we start with the child who has the least greed factor. This allows us to assign cookies to children starting with those who require the smallest cookie. Sorting the cookies array enables us to assign the smallest available cookie to a child, optimizing the number of content children.
Use two pointers:
- One pointer (childIndex) will track the current child (starting from the child with the smallest greed factor).
- Another pointer (cookieIndex) will track the current cookie in the sorted cookies array.
Iterate through both arrays:
- Begin by comparing the greed of the current child (greed[childIndex]) and the size of the current cookie (cookies[cookieIndex]).
- If the current cookie is large enough to satisfy the current child's greed (i.e., cookies[cookieIndex] >= greed[childIndex]), mark this child as content by incrementing the counter childrencount and move to the next child by incrementing childIndex.
- Whether or not the child is satisfied, move to the next cookie by incrementing cookieIndex.
Stop when either all cookies or all children have been processed:
- The loop continues until all cookies have been exhausted or all children are satisfied. If there are more children than cookies, the number of content children will be limited by the number of available cookies. If there are more cookies than children, the number of content children will be limited by the number of children.
Return the result:
- Once the loop completes, the variable childrencount will hold the total number of content children. This value is returned as the final result.
Code Implementation
C++
class Solution {
public:
int findContentChildren(vector<int>& greed, vector<int>& cookies) {
// Sort both the greed array and the cookies array in ascending order
sort(greed.begin(), greed.end());
sort(cookies.begin(), cookies.end());
// To track which child we are assigning cookies to
int childIndex = 0;
// To track which cookie we're currently considering
int cookieIndex = 0;
// To count the number of satisfied children
int childrenCount = 0;
// Iterate over the cookies and try to assign them to children
while (childIndex < greed.size() && cookieIndex < cookies.size()) {
// If the current cookie satisfies the current child
if (cookies[cookieIndex] >= greed[childIndex]) {
// Assign the cookie to the child
childIndex++;
childrenCount++; // Increment the satisfied children count
}
// Move to the next cookie (whether it was assigned or not)
cookieIndex++;
}
// Return the total number of content children
return childrenCount;
}
};
Java
// Solution class that contains the logic for finding content children
class Solution {
public int findContentChildren(int[] greed, int[] cookies) {
// Sort both the greed array and the cookies array in ascending order
Arrays.sort(greed);
Arrays.sort(cookies);
// To track which child we are assigning cookies to
int childIndex = 0;
// To track which cookie we're currently considering
int cookieIndex = 0;
// To count the number of satisfied children
int childrenCount = 0;
// Iterate over the cookies and try to assign them to children
while (childIndex < greed.length && cookieIndex < cookies.length) {
// If the current cookie satisfies the current child's greed
if (cookies[cookieIndex] >= greed[childIndex]) {
// Assign the cookie to the child
childIndex++;
childrenCount++; // Increment the satisfied children count
}
// Move to the next cookie (whether it was assigned or not)
cookieIndex++;
}
// Return the total number of content children
return childrenCount;
}
}Python
class Solution:
def findContentChildren(self, greed, cookies):
# Sort both the greed array and the cookies array in ascending order
greed.sort()
cookies.sort()
# To track which child we are assigning cookies to
childIndex = 0
# To track which cookie we're currently considering
cookieIndex = 0
# To count the number of satisfied children
childrenCount = 0
# Iterate over the cookies and try to assign them to children
while childIndex < len(greed) and cookieIndex < len(cookies):
# If the current cookie satisfies the current child
if cookies[cookieIndex] >= greed[childIndex]:
# Assign the cookie to the child
childIndex += 1
childrenCount += 1 # Increment the satisfied children count
# Move to the next cookie (whether it was assigned or not)
cookieIndex += 1
# Return the total number of content children
return childrenCountJavascript
/**
* @param {number[]} greed
* @param {number[]} cookies
* @return {number}
*/
var findContentChildren = function(greed, cookies) {
// Sort both greed and cookies arrays in ascending order
greed.sort((a, b) => a - b);
cookies.sort((a, b) => a - b);
// To track which child we are assigning cookies to
let childIndex = 0;
// To track which cookie we're currently considering
let cookieIndex = 0;
// To count the number of satisfied children
let childrenCount = 0;
// Iterate over the cookies and try to assign them to children
while (childIndex < greed.length && cookieIndex < cookies.length) {
// If the current cookie satisfies the current child
if (cookies[cookieIndex] >= greed[childIndex]) {
// Assign the cookie to the child
childIndex++;
childrenCount++; // Increment the satisfied children count
}
// Move to the next cookie (whether it was assigned or not)
cookieIndex++;
}
// The number of satisfied children is tracked by childrenCount
return childrenCount;
};Time Complexity: O(m log m + n log n)
The time complexity of this solution is broken down into the following steps:
- Sorting the Greed Array:
- First, we sort the array of children's greed factors (greed). Sorting generally takes O(m log m) time, where m is the number of children in the array.
- Sorting the Cookies Array:
- Next, we sort the array of cookies (cookies). Sorting the cookies array also takes O(n log n) time, where n is the number of available cookies.
- Iterating Through the Arrays:
- After sorting, we iterate through both the greed and cookies arrays simultaneously in a greedy manner to match the smallest possible cookie that satisfies a child's greed. This step takes O(min(m, n)) time, because the loop runs until we either run out of children or cookies, whichever happens first. Here, m is the number of children and n is the number of cookies.
Total Time Complexity:
- Combining these operations, the total time complexity is:
- Sorting the greed array: O(m log m)
- Sorting the cookies array: O(n log n)
- Iterating through both arrays: O(min(m, n))
Therefore, the overall time complexity is: O(m log m + n log n)
Space Complexity: O(1)
Let's break it down:
- Input Arrays:
- We are given two input arrays: greed (with m elements) and cookies (with n elements).
- These arrays are already provided, so they do not contribute to extra space used by the algorithm. However, they are important to understand that the space to store them is O(m + n), but this is not considered additional space for our algorithm.
- Auxiliary Space:
- Temporary Variables: During the matching process, we use a few integer variables to store indices and counters (like childIndex, cookieIndex, childrencount, etc.). These variables require constant space, O(1).
Final Space Complexity:
- The space used for temporary variables is O(1), since only a few integers are being used for indexing.
Thus, the total space complexity is: O(1)
Learning Tips
Now we have successfully tackled this problem, let's try these similar problems.
You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.
The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.
Return the maximum number of matchings between players and trainers that satisfy these conditions.
You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:
- difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and
- worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).
Every worker can be assigned at most one job, but one job can be completed multiple times.
- For example, if three workers attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, their profit is $0.
Return the maximum profit we can achieve after assigning the workers to the jobs.