Problem Statement:
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 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 1
Approach:
- Sort both arrays
gandsin ascending order. - Use two pointers
i→ tracks childrenj→ tracks cookies
- Traverse through cookies (
s):- If current cookie satisfies the child’s greed (
s[j] >= g[i]), assign it → move to next child (i++). - Always move to next cookie
(j++).
- If current cookie satisfies the child’s greed (
- Return
i→ number of children satisfied.
Time & Space Complexity:
Time Complexity: O(n log n + m log m)
Space Complexity: O(1)
Dry Run
Input: g = [1,2,3], s = [1,1]
Step 1: Sort both arrays g = [1, 2, 3] s = [1, 1] Step 2: Initialize i = 0 (index for g → children) j = 0 (index for s → cookies) Step 3: Start while loop (j < s.length) j = 0 → s[0] = 1, g[0] = 1 Since 1 >= 1 → child gets cookie → i = 1 j = 1 → s[1] = 1, g[1] = 2 Since 1 < 2 → child not satisfied Increment j = 2 (loop ends) Step 4: End i = 1 (number of content children)
Output: Result: 1
var findContentChildren = function(g, s) {
s.sort((a, b) => a - b);
g.sort((a, b) => a - b);
let i = 0; // child index
let j = 0; // cookie index
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) {
++i;
++j;
} else {
++j;
}
}
return i;
};
def findContentChildren(g, s):
g.sort()
s.sort()
i = 0
j = 0
while i < len(g) and j < len(s):
if s[j] >= g[i]:
i += 1
j += 1
else:
j += 1
return i
import java.util.Arrays;
public class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0;
int j = 0;
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) {
i++;
j++;
} else {
j++;
}
}
return i;
}
}
#include <vector>
#include <algorithm>
int findContentChildren(std::vector& g, std::vector& s) {
std::sort(g.begin(), g.end());
std::sort(s.begin(), s.end());
int i = 0;
int j = 0;
while (i < (int)g.size() && j < (int)s.size()) {
if (s[j] >= g[i]) {
++i;
++j;
} else {
++j;
}
}
return i;
}
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
int ia = *(const int*)a;
int ib = *(const int*)b;
return (ia > ib) - (ia < ib);
}
int findContentChildren(int *g, int gSize, int *s, int sSize) {
qsort(g, gSize, sizeof(int), cmp_int);
qsort(s, sSize, sizeof(int), cmp_int);
int i = 0;
int j = 0;
while (i < gSize && j < sSize) {
if (s[j] >= g[i]) {
i++;
j++;
} else {
j++;
}
}
return i;
}
using System;
public class Solution {
public int FindContentChildren(int[] g, int[] s) {
Array.Sort(g);
Array.Sort(s);
int i = 0;
int j = 0;
while (i < g.Length && j < s.Length) {
if (s[j] >= g[i]) {
i++;
j++;
} else {
j++;
}
}
return i;
}
}
