Assign Cookies

Easy

#0442Time: O(n*m + n log n + m log m). Sorting takes O(n log n + m log m), and filling the DP table takes O(n*m). The DP table creation dominates the complexity.Space: O(n * m), where n is the number of children and m is the number of cookies. This is for the 2D DP table.2 companies

Patterns

Algorithms

Data structures

Companies

Prompt

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 * 10⁴
0 <= s.length <= 3 * 10⁴
1 <= g[i], s[j] <= 2³¹ - 1

Note: This question is the same as 2410: Maximum Matching of Players With Trainers.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves sorting both the greed factors and cookie sizes and then using dynamic programming to find the maximum number of content children. We define a 2D DP table where dp[i][j] represents the maximum number of children we can satisfy from the first i children using the first j cookies. This approach explores all possibilities systematically but is less efficient due to its high time and space complexity.

Algorithm

Sort the greed factor array g and the cookie size array s in non-decreasing order.
Create a 2D DP array dp of size (g.length + 1) x (s.length + 1).
Initialize the DP table with zeros. dp[i][j] will store the maximum number of content children considering children g[0...i-1] and cookies s[0...j-1].
Iterate through each child i from 1 to g.length.
Iterate through each cookie j from 1 to s.length.
If the current cookie s[j-1] is large enough for the current child g[i-1] (i.e., s[j-1] >= g[i-1]):
- We can either assign this cookie to this child (1 + dp[i-1][j-1]) or not (dp[i][j-1]).
- Set dp[i][j] = max(1 + dp[i-1][j-1], dp[i][j-1]).
If the cookie is too small:
- We cannot assign it. The result is the same as if we didn't have this cookie.
- Set dp[i][j] = dp[i][j-1].
The final answer is the value in dp[g.length][s.length].

Walkthrough

First, we sort both the greed factor array g and the cookie size array s in non-decreasing order. This allows us to make decisions in a structured manner. We then create a 2D DP array dp of size (g.length + 1) x (s.length + 1). dp[i][j] will store the maximum number of content children considering children g[0...i-1] and cookies s[0...j-1].

The state transition logic is as follows: We iterate through each child i and each cookie j. If the current cookie s[j-1] is large enough for the current child g[i-1], we have two choices: either assign this cookie to the child, which yields 1 + dp[i-1][j-1] content children, or don't assign it, which yields dp[i][j-1] content children. We take the maximum of these two options. If the cookie is too small, we cannot assign it, so the result is simply dp[i][j-1]. The final answer is stored in dp[g.length][s.length].

1import java.util.Arrays;2 3class Solution {4    public int findContentChildren(int[] g, int[] s) {5        Arrays.sort(g);6        Arrays.sort(s);7        int n = g.length;8        int m = s.length;9        if (n == 0 || m == 0) {10            return 0;11        }12        int[][] dp = new int[n + 1][m + 1];13        for (int i = 1; i <= n; i++) {14            for (int j = 1; j <= m; j++) {15                if (s[j - 1] >= g[i - 1]) {16                    // Option 1: Assign cookie j-1 to child i-117                    // Option 2: Don't assign cookie j-1 (result is dp[i][j-1])18                    dp[i][j] = Math.max(1 + dp[i - 1][j - 1], dp[i][j - 1]);19                } else {20                    // Cookie j-1 is too small for child i-1, so we can't assign it.21                    dp[i][j] = dp[i][j - 1];22                }23            }24        }25        return dp[n][m];26    }27}

Complexity

Time

O(n*m + n log n + m log m). Sorting takes O(n log n + m log m), and filling the DP table takes O(n*m). The DP table creation dominates the complexity.

Space

O(n * m), where n is the number of children and m is the number of cookies. This is for the 2D DP table.

Trade-offs

Pros

Guarantees the optimal solution by systematically checking all subproblems.
Represents a standard dynamic programming pattern for solving assignment or subset problems.

Cons

The time complexity of O(n*m) is too slow for the given constraints (n, m <= 3 * 10^4), leading to a 'Time Limit Exceeded' error on most platforms.
The space complexity of O(n*m) is also very high and may cause a 'Memory Limit Exceeded' error.

The most efficient way to solve this problem is using a greedy approach. The core idea is that to maximize the number of satisfied children, we should try to satisfy the least greedy child with the smallest cookie that is large enough. This strategy ensures that larger cookies are saved for greedier children who might need them. By sorting both the children's greed factors and the cookie sizes, we can efficiently implement this strategy using two pointers.

Algorithm

Sort the greed array g and the cookie size array s in ascending order.
Initialize a pointer for children, childIndex = 0.
Initialize a pointer for cookies, cookieIndex = 0.
Initialize a counter for satisfied children, contentChildren = 0.
Loop while childIndex < g.length and cookieIndex < s.length:
Check if the current cookie can satisfy the current child: s[cookieIndex] >= g[childIndex].
If it can, we've found a match. Increment contentChildren, childIndex, and cookieIndex.
If it cannot, the cookie is too small. Discard it by incrementing cookieIndex and try to satisfy the same child with the next cookie.
Return contentChildren after the loop terminates.

Walkthrough

The intuition behind this greedy strategy is that if the smallest available cookie can satisfy the least greedy child, we should make that assignment. This is optimal because this smallest cookie is the least likely to satisfy any of the other, greedier children. Assigning it to the least greedy child frees up larger, more 'valuable' cookies for those who need them. If the smallest cookie cannot satisfy the least greedy child, it certainly cannot satisfy any other child, so we can discard it and try the next larger cookie for the same child.

The algorithm is implemented as follows:

Sort both the greed factor array g and the cookie size array s in ascending order.
Use two pointers: childIndex for g and cookieIndex for s, both starting at 0.
Iterate while both pointers are within their array bounds. In each step, if the cookie at cookieIndex can satisfy the child at childIndex (s[cookieIndex] >= g[childIndex]), we count it as a successful assignment and advance both pointers. If the cookie is too small, it's of no use to the current child (or any subsequent, greedier children), so we discard the cookie by advancing only the cookieIndex.
The total count of successful assignments is the answer.

1import java.util.Arrays;2 3class Solution {4    public int findContentChildren(int[] g, int[] s) {5        Arrays.sort(g);6        Arrays.sort(s);7        8        int childIndex = 0;9        int cookieIndex = 0;10        11        while (childIndex < g.length && cookieIndex < s.length) {12            // If the current cookie can satisfy the current child13            if (s[cookieIndex] >= g[childIndex]) {14                // Assign the cookie to the child and move to the next child15                childIndex++;16            }17            // Move to the next cookie regardless of whether it was assigned or not18            cookieIndex++;19        }20        21        return childIndex;22    }23}

Note: The code can be slightly simplified. The number of content children is simply the final value of childIndex.

Complexity

Time

O(n log n + m log m), where n is the number of children and m is the number of cookies. The complexity is dominated by the sorting step. The two-pointer scan takes O(n + m) time.

Space

O(log n + log m) or O(n + m) depending on the sort implementation's space requirements. For Java's `Arrays.sort`, it's O(log n + log m) on average. If we ignore the space used by sorting, it's O(1).

Trade-offs

Pros

Highly efficient with a near-linear time complexity.
Minimal space complexity.
The logic is simple and intuitive once the greedy choice is understood.

Cons

Requires sorting the arrays, which modifies them in-place. If the original order is important, copies must be made, increasing space complexity to O(n + m).

Solutions

Solution

1class Solution {2public3  int findContentChildren(int[] g, int[] s) {4    Arrays.sort(g);5    Arrays.sort(s);6    int m = g.length;7    int n = s.length;8    for (int i = 0, j = 0; i < m; ++i) {9      while (j < n && s[j] < g[i]) {10        ++j;11      }12      if (j++ >= n) {13        return i;14      }15    }16    return m;17  }18}

1/** * @param {number[]} g * @param {number[]} s * @return {number} */ var findContentChildren =2  function (g, s) {3    g.sort((a, b) => a - b);4    s.sort((a, b) => a - b);5    const m = g.length;6    const n = s.length;7    for (let i = 0, j = 0; i < m; ++i) {8      while (j < n && s[j] < g[i]) {9        ++j;10      }11      if (j++ >= n) {12        return i;13      }14    }15    return m;16  };

1class Solution {2public:3  int findContentChildren(vector<int> &g, vector<int> &s) {4    sort(g.begin(), g.end());5    sort(s.begin(), s.end());6    int m = g.size(), n = s.size();7    for (int i = 0, j = 0; i < m; ++i) {8      while (j < n && s[j] < g[i]) {9        ++j;10      }11      if (j++ >= n) {12        return i;13      }14    }15    return m;16  }17};

1class Solution:2    def findContentChildren(self, g: List[int], s: List[int]) -> int: g . sort() s . sort() j = 0 for i, x in enumerate(g): while j < len(s) and s[j] < g[i]: j += 1 if j >= len(s): return i j += 1 return len(g)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem