# Solution by rohitnandi12

• 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 ith Child the Greed Factor be gi, and compare it with each Cookie size sj, until it satisfies the condition sj >= gi. Change sj 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 sj >= gi
• 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)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.