# Assign Cookies
**Difficulty:** EASY
[External](https://leetcode.com/problems/assign-cookies)
Canonical: https://scaleengineer.com/dsa/problems/assign-cookies
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## Problem
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.](https://leetcode.com/problems/maximum-matching-of-players-with-trainers/description/)

# Approaches
## Sorting and Dynamic Programming
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.
**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.
**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.
### Explanation
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]`.

```java
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];
    }
}
```
### 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]`.

## Greedy Approach with Two Pointers
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.
**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).
**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).
### Explanation
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:
1. Sort both the greed factor array `g` and the cookie size array `s` in ascending order.
2. Use two pointers: `childIndex` for `g` and `cookieIndex` for `s`, both starting at 0.
3. 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`.
4. The total count of successful assignments is the answer.

```java
import java.util.Arrays;

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int childIndex = 0;
        int cookieIndex = 0;
        
        while (childIndex < g.length && cookieIndex < s.length) {
            // If the current cookie can satisfy the current child
            if (s[cookieIndex] >= g[childIndex]) {
                // Assign the cookie to the child and move to the next child
                childIndex++;
            }
            // Move to the next cookie regardless of whether it was assigned or not
            cookieIndex++;
        }
        
        return childIndex;
    }
}
```
*Note: The code can be slightly simplified. The number of content children is simply the final value of `childIndex`.*
### Algorithm
1. Sort the greed array `g` and the cookie size array `s` in ascending order.
2. Initialize a pointer for children, `childIndex = 0`.
3. Initialize a pointer for cookies, `cookieIndex = 0`.
4. Initialize a counter for satisfied children, `contentChildren = 0`.
5. Loop while `childIndex < g.length` and `cookieIndex < s.length`:
6.   Check if the current cookie can satisfy the current child: `s[cookieIndex] >= g[childIndex]`.
7.   If it can, we've found a match. Increment `contentChildren`, `childIndex`, and `cookieIndex`.
8.   If it cannot, the cookie is too small. Discard it by incrementing `cookieIndex` and try to satisfy the same child with the next cookie.
9. Return `contentChildren` after the loop terminates.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} g * @param {number[]} s * @return {number} */ var findContentChildren =
  function (g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    const m = g.length;
    const n = s.length;
    for (let i = 0, j = 0; i < m; ++i) {
      while (j < n && s[j] < g[i]) {
        ++j;
      }
      if (j++ >= n) {
        return i;
      }
    }
    return m;
  };

```

### CPP

```cpp
class Solution {
public:
  int findContentChildren(vector<int> &g, vector<int> &s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int m = g.size(), n = s.size();
    for (int i = 0, j = 0; i < m; ++i) {
      while (j < n && s[j] < g[i]) {
        ++j;
      }
      if (j++ >= n) {
        return i;
      }
    }
    return m;
  }
};

```

### Python

```python
class Solution:
    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)

```