Description:
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.
Examples:
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.Solution in Python:
The goal is to maximize the number of content children by assigning the smallest possible cookie that is still large enough for each child’s greed factor.
- Sort the Arrays: Sort both the greed factor array
gand the cookie size arraysin ascending order. - Two Pointers: Use two pointers to iterate through the sorted arrays. One pointer (
i) for the greed factors and one pointer (j) for the cookie sizes. - Assign Cookies: Iterate through both arrays and try to assign the smallest available cookie that satisfies the current child’s greed factor. If a cookie satisfies a child, move both pointers to the next child and the next cookie. If a cookie does not satisfy the child, just move the cookie pointer to try the next larger cookie.
Python
from typing import List
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# Step 1: Sort the greed factor array and the cookie size array
g.sort()
s.sort()
# Initialize two pointers for children and cookies
i, j = 0, 0
# Initialize a count of content children
content_children = 0
# Step 2: Iterate through both arrays
while i < len(g) and j < len(s):
# If the current cookie can satisfy the current child's greed factor
if s[j] >= g[i]:
# Increase the count of content children
content_children += 1
# Move to the next child
i += 1
# Move to the next cookie in any case
j += 1
# Return the count of content children
return content_childrenExample Walkthrough:
- Example 1:
nums = [3, 2, 1]- After removing duplicates:
[3, 2, 1] - After sorting:
[3, 2, 1] - Length is 3, so the third maximum is
1.
- After removing duplicates:
- Example 2:
nums = [1, 2]- After removing duplicates:
[1, 2] - After sorting:
[2, 1] - Length is 2, which is less than 3, so return the maximum which is
2.
- After removing duplicates:
- Example 3:
nums = [2, 2, 3, 1]- After removing duplicates:
[1, 2, 3] - After sorting:
[3, 2, 1] - Length is 3, so the third maximum is
1.
- After removing duplicates:
This approach ensures the solution is efficient and handles the constraints properly.
Solution in Javascript:
JavaScript
/**
* @param {number[]} g - Greed factors of children
* @param {number[]} s - Sizes of cookies
* @return {number} - Maximum number of content children
*/
var findContentChildren = function(g, s) {
// Step 1: Sort the greed factor array and the cookie size array in ascending order
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
// Initialize two pointers for children and cookies
let i = 0, j = 0;
// Initialize a count of content children
let contentChildren = 0;
// Step 2: Iterate through both arrays
while (i < g.length && j < s.length) {
// If the current cookie can satisfy the current child's greed factor
if (s[j] >= g[i]) {
// Increase the count of content children
contentChildren++;
// Move to the next child
i++;
}
// Move to the next cookie in any case
j++;
}
// Return the count of content children
return contentChildren;
};Solution in Java:
Java
import java.util.Arrays;
class Solution {
public int findContentChildren(int[] g, int[] s) {
// Step 1: Sort the greed factor array and the cookie size array in ascending order
Arrays.sort(g);
Arrays.sort(s);
// Initialize two pointers for children and cookies
int i = 0, j = 0;
// Initialize a count of content children
int contentChildren = 0;
// Step 2: Iterate through both arrays
while (i < g.length && j < s.length) {
// If the current cookie can satisfy the current child's greed factor
if (s[j] >= g[i]) {
// Increase the count of content children
contentChildren++;
// Move to the next child
i++;
}
// Move to the next cookie in any case
j++;
}
// Return the count of content children
return contentChildren;
}
}Solution in C#:
C#
using System;
using System.Linq;
public class Solution {
public int FindContentChildren(int[] g, int[] s) {
// Step 1: Sort the greed factor array and the cookie size array in ascending order
Array.Sort(g);
Array.Sort(s);
// Initialize two pointers for children and cookies
int i = 0, j = 0;
// Initialize a count of content children
int contentChildren = 0;
// Step 2: Iterate through both arrays
while (i < g.Length && j < s.Length) {
// If the current cookie can satisfy the current child's greed factor
if (s[j] >= g[i]) {
// Increase the count of content children
contentChildren++;
// Move to the next child
i++;
}
// Move to the next cookie in any case
j++;
}
// Return the count of content children
return contentChildren;
}
}