From the question it is clear that there will be 1 to 1 Mapping
between elements Cookie s
and Greed Factor g
Tip:1 In problems where you need to compare one element with rest of the elements be it in same or different arrays, think of brute force approach and later try to optimize it.
Test Cases
Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.
Test Input 1: T1
[1,1,2]
[1,2,3]
Test Input 2: T2
[1,3,3]
[4,1,2,5]
Approach #1 Brute Force [Wrong Solution]
Intuition
Let for the i^{th} Child the Greed Factor be g_{i}, and compare it with each Cookie size s_{j}, until it satisfies the condition s_{j} >= g_{i}. Change s_{j} to 1 to denote it has been selected for a child.
Java
public class Solution {
public int findContentChildren(int[] g, int[] s) {
int noOfContentChild = 0;
for(int i=0; i<g.length; i++){
for(int j=0; j<s.length; j++){
if(s[j]==1)continue;
if(s[j]>=g[i]){
++noOfContentChild;
s[j] = 1;
break;
}
}
}
return noOfContentChild;
}
}
Testing
T1 = Passed
T2 = Failed
Testing Inference
T2 fails because our current algorithm assigns the first cookie size greater than the greed factor in hand, irrespective how big it is, which is not so frugal.
Approach #2 Sort Method [Accepted]
Intuition
If we sort the arrays, then we can start with the smallest greed Factor and move to next Greed Factor only if a cookie size is greater than it.
Algorithm
 Sort array g
 Sort array s
 Loop until end of g or s (whichever is shorter)
 move to next Greed Factor only when s_{j} >= g_{i}
 move to next cookie size
 Return the last greed factor index
Java
public class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int gi=0, si=0; //gIndex and sIndex
while(gi<g.length && si<s.length){
if(s[si]>=g[gi]){
gi++;
}
si++;
}
return gi;
}
}
Testing
T1 = Passed
T2 = Passed
Complexity Analysis

Time complexity : O(Min(n,m)). Where n is size of array g and m is size of array s. Ignoring O(n log n) and O(m log m) to sort the arrays.

Space complexity : O(1)