455. Assign Cookies
Problem Description
The problem describes a scenario where a parent wants to distribute cookies to their children in a way that maximizes happiness, given certain constraints. Each child has a greed factor, g[i]
, which indicates the minimum size of a cookie that will make them content. Similarly, each cookie has a size, s[j]
. A cookie can only make a child content if the size of the cookie is greater than or equal to the child's greed factor. The objective is to assign cookies to children in such a manner that the maximum number of children are content. A child can receive at most one cookie, and a cookie can only be assigned to one child. The task is to calculate the maximum number of content children based on the distribution of cookies according to the children's greed factors.
Intuition
The intuition behind the solution is to prioritize giving cookies to children with the smallest greed factor first. We can sort both the children's greed factors (g
) and the cookie sizes (s
) in non-decreasing order. We then iterate through the sorted greed factors, trying to find the smallest cookie that meets or exceeds that greed factor. If such a cookie is found, we assign it to the child, making them content, and move on to the next child. Once a cookie has been assigned, it can no longer be given to any other child, so we move to the next available cookie.
The reason for sorting is to use the smallest cookies for children with the lowest greed factor, which ensures we don't waste a large cookie on a child who would be content with a smaller one. By efficiently matching cookies to children starting with the least greedy ones, we aim to maximize the total number of content children.
As we iterate through the greed factors, if we reach a point where there are no more cookies left to satisfy a child, we return the number of children that have been made content so far. If all children have been assigned a cookie, we return the total number of children.
Learn more about Greedy, Two Pointers and Sorting patterns.
Solution Approach
The solution approach uses a greedy algorithm which is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. In this case, the immediate benefit is making a child content with the smallest cookie possible.
The algorithm works as follows:
-
Sort the greed factors array
g
and the cookie sizes arrays
in ascending order. This sorting is crucial as it allows us to efficiently assign the smallest available cookie that will make each child content. -
Initialize a pointer
j
to0
, which will track the current index in the cookie sizes arrays
. -
Loop through each child's greed factor in
g
, with the indexi
iterating throughg
. -
For the current child's greed factor (
g[i]
), iterate through the cookies starting from the current indexj
in the arrays
until you find a cookie large enough to satisfy this child. This inner while loop continues as long asj < len(s)
and the current cookie is smaller than the current child's greed factor (s[j] < g[i]
). If the current cookie is too small, incrementj
to check the next cookie. -
If
j
is equal to or greater than the length ofs
, meaning there are no more cookies left to distribute, return the indexi
as the total number of content children. -
If a suitable cookie is found (one that is equal to or larger than
g[i]
), incrementj
to move to the next cookie and continue with the next child by proceeding to the next iteration of the for loop. -
If all children have been considered, return the length of
g
as all children have been made content.
The performance of this algorithm hinges on the sorting process (which typically runs in O(n log n) time). The following loop operations are linear, making the total time complexity O(n log n) primarily due to sorting, where n
is the number of elements in the larger of the two arrays g
or s
. Space complexity is O(1) since the solution sorts and iterates over the input arrays in place without using extra space for auxiliary data structures.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the following example to illustrate the solution approach. Imagine a scenario where we have three children with greed factors g = [1, 2, 3]
and an assortment of four cookies with sizes s = [1, 1, 3, 4]
.
Following the steps outlined in the solution approach:
-
First, sort the arrays
g
ands
. Sinceg
is already sorted, we only need to sorts
, which becomess = [1, 1, 3, 4]
. Both arrays are now sorted in ascending order. -
Initialize a pointer
j
to0
to track the current index in the sorted cookie sizes arrays
. -
Loop through each child's greed factor in
g
. We start with the first childg[0]
, which is1
. -
For the current child's greed factor (
g[i]
), loop through the cookies starting from the currentj
index. We compare the child's greed factor to the current cookie size:- For the first child (
g[0] = 1
), the first cookie (s[0] = 1
) is of size1
, which satisfies the child's greed factor. We incrementj
to1
and move to the next child.
- For the first child (
-
We now check for the second child (
g[1] = 2
). Since we have incrementedj
, the cookie we are looking at is nows[1]
which is of size1
. However,1
is smaller than the greed factor2
. So, we incrementj
to2
.- Now looking at cookie
s[2]
which is of size3
, it satisfies the second child's need (g[1] = 2
). We incrementj
to3
and move to the next child.
- Now looking at cookie
-
For the third child (
g[2] = 3
), the next cookie iss[3] = 4
, which is also sufficient. We incrementj
to4
(which now is outside the boundary of arrays
). -
Since all the children's greed factors have been considered and satisfied, we return the length of
g
, which is3
. This indicates that all children have been made content.
By following the algorithm, we have maximized the number of content children with the available cookies. The sorted arrays allowed us to efficiently match the smallest possible cookie to each child according to their greed factor.
Solution Implementation
1class Solution:
2 def findContentChildren(self, greed_factors: List[int], cookie_sizes: List[int]) -> int:
3 # Sort the greed factors of the children and the sizes of the cookies
4 greed_factors.sort()
5 cookie_sizes.sort()
6
7 # Initialize the cookie index
8 cookie_index = 0
9
10 # Iterate through each greed factor
11 for child_index, greed in enumerate(greed_factors):
12 # Move through the cookie sizes until we find a cookie that satisfies the current greed factor
13 while cookie_index < len(cookie_sizes) and cookie_sizes[cookie_index] < greed:
14 cookie_index += 1
15
16 # If there are no more cookies left, return the number of content children so far
17 if cookie_index >= len(cookie_sizes):
18 return child_index
19
20 # Move to the next cookie index assuming the current cookie has been used
21 cookie_index += 1
22
23 # All children have been content, return the total number of children
24 return len(greed_factors)
25
1class Solution {
2 // Method to find the maximum number of content children given the greed factors of children and the sizes of cookies
3 public int findContentChildren(int[] greedFactors, int[] cookieSizes) {
4 // Sort the arrays to make the greedy assignment possible
5 Arrays.sort(greedFactors);
6 Arrays.sort(cookieSizes);
7
8 int numberOfChildren = greedFactors.length; // Total number of children
9 int numberOfCookies = cookieSizes.length; // Total number of cookies available
10
11 // Initialize the count for content children
12 int contentChildrenCount = 0;
13
14 // Initialize pointers for greedFactors and cookieSizes arrays
15 int greedFactorIndex = 0;
16 int cookieSizeIndex = 0;
17
18 // Loop through each child's greed factor
19 while (greedFactorIndex < numberOfChildren) {
20
21 // Find the first cookie that satisfies the current child's greed factor
22 while (cookieSizeIndex < numberOfCookies && cookieSizes[cookieSizeIndex] < greedFactors[greedFactorIndex]) {
23 cookieSizeIndex++; // Increment cookie index until a big enough cookie is found
24 }
25
26 // If a cookie that satisfies the current child's greed factor is found, consider the child content
27 if (cookieSizeIndex < numberOfCookies) {
28 contentChildrenCount++; // Increment the count of content children
29 cookieSizeIndex++; // Move to the next cookie
30 } else {
31 // If no more cookies are available to satisfy any more children, break out of the loop
32 break;
33 }
34
35 // Move to the next child
36 greedFactorIndex++;
37 }
38
39 // Return the final count of content children
40 return contentChildrenCount;
41 }
42}
43
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 int findContentChildren(std::vector<int>& children, std::vector<int>& cookies) {
7 // Sort the greed factors of the children
8 std::sort(children.begin(), children.end());
9 // Sort the sizes of the cookies
10 std::sort(cookies.begin(), cookies.end());
11
12 int numChildren = children.size(); // Number of children
13 int numCookies = cookies.size(); // Number of cookies
14 int contentChildren = 0; // Counter for content children
15
16 // Iterate through each child
17 for (int childIndex = 0, cookieIndex = 0; childIndex < numChildren; ++childIndex) {
18 // Find the first cookie that can satisfy the current child's greed factor
19 while (cookieIndex < numCookies && cookies[cookieIndex] < children[childIndex]) {
20 ++cookieIndex;
21 }
22
23 // If we found a cookie that can satisfy the child
24 if (cookieIndex < numCookies) {
25 // Give the cookie to the child
26 ++contentChildren;
27 // Move to the next cookie
28 ++cookieIndex;
29 } else {
30 // If no more cookies are available that can satisfy any child, break out of the loop
31 break;
32 }
33 }
34
35 // The number of children who can be content with the cookies we have
36 return contentChildren;
37 }
38};
39
1/**
2 * Finds the maximum number of content children given the children's greed factors and the sizes of cookies.
3 * A child will be content if they receive a cookie that is equal to or larger than their greed factor.
4 * @param {number[]} greedFactors - An array representing the greed factors of each child.
5 * @param {number[]} cookieSizes - An array representing the sizes of cookies available.
6 * @returns {number} The maximum number of content children.
7 */
8function findContentChildren(greedFactors: number[], cookieSizes: number[]): number {
9 // Sort greed factors and cookie sizes in non-decreasing order.
10 greedFactors.sort((a, b) => a - b);
11 cookieSizes.sort((a, b) => a - b);
12
13 // Initialize counters for children and cookies.
14 const totalChildren = greedFactors.length;
15 const totalCookies = cookieSizes.length;
16
17 // Initialize the index for greed factors and cookie sizes.
18 let childIndex = 0;
19 let cookieIndex = 0;
20
21 // Loop through the greed factors of each child.
22 while (childIndex < totalChildren) {
23 // Find a cookie that is equal to or larger than the greed factor of the current child.
24 while (cookieIndex < totalCookies && cookieSizes[cookieIndex] < greedFactors[childIndex]) {
25 cookieIndex++;
26 }
27
28 // If a suitable cookie is found, move on to the next child and cookie.
29 if (cookieIndex < totalCookies) {
30 childIndex++;
31 cookieIndex++;
32 } else {
33 // No more cookies available, return the number of content children.
34 return childIndex;
35 }
36 }
37
38 // All children have been matched with cookies, return the total number of children.
39 return totalChildren;
40}
41
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed based on two main operations: sorting the lists g
and s
and then iterating through them to find content children.
-
Sorting: Both the lists
g
ands
are sorted at the beginning of the function. The sorting operation typically has a time complexity ofO(n log n)
for an average sorting algorithm like Timsort (used in Python'ssort()
method), wheren
is the number of elements in the list. Ifg
hasN
elements ands
hasM
elements, the total time for sorting would beO(N log N + M log M)
. -
Iterating through Lists: After sorting, the code uses a while loop within a for loop to find matches for g[i]. In the worst-case scenario, every element of
g
would be compared with every element ofs
, which gives us a time complexity ofO(N+M)
, as each list is traversed at most once.
Combining both steps, the overall time complexity is O(N log N + M log M)
for the sorting part, which is dominant, plus O(N+M)
for the iteration part. Therefore, the total time complexity is:
O(N log N + M log M)
.
Space Complexity
The space complexity is the amount of extra space or temporary space used by an algorithm. The provided code only uses a fixed number of variables (i
, x
, j
) and does not create any auxiliary data structures proportional to the size of the input. The space taken up by the input lists themselves is not counted towards the space complexity, as they are part of the input.
Therefore, the space complexity is:
O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!