Scale Engineer

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
Two PointersGreedy
Algorithms
Sorting
Data structures
Array
Companies
AccentureAtlassian

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

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

  1. Sort the greed factor array g and the cookie size array s in non-decreasing order.
  2. Create a 2D DP array dp of size (g.length + 1) x (s.length + 1).
  3. 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].
  4. Iterate through each child i from 1 to g.length.
  5. Iterate through each cookie j from 1 to s.length.
  6. 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]).
  7. 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].
  8. 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].

import java.util.Arrays; class Solution {    public int findContentChildren(int[] g, int[] s) {        Arrays.sort(g);        Arrays.sort(s);        int n = g.length;        int m = s.length;        if (n == 0 || m == 0) {            return 0;        }        int[][] dp = new int[n + 1][m + 1];        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= m; j++) {                if (s[j - 1] >= g[i - 1]) {                    // Option 1: Assign cookie j-1 to child i-1                    // Option 2: Don't assign cookie j-1 (result is dp[i][j-1])                    dp[i][j] = Math.max(1 + dp[i - 1][j - 1], dp[i][j - 1]);                } else {                    // Cookie j-1 is too small for child i-1, so we can't assign it.                    dp[i][j] = dp[i][j - 1];                }            }        }        return dp[n][m];    }}

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.

Solutions

class Solution {public  int findContentChildren(int[] g, int[] s) {    Arrays.sort(g);    Arrays.sort(s);    int m = g.length;    int n = s.length;    for (int i = 0, j = 0; i < m; ++i) {      while (j < n && s[j] < g[i]) {        ++j;      }      if (j++ >= n) {        return i;      }    }    return m;  }}

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 →

Next problem