Optimizing Generosity: A Greedy Approach to LeetCode 455 (Assign Cookies)

#leetcode #java #programming #challenge

Difficulty: Easy
Topics: Array, Two Pointers, Greedy, Sorting
Platform: Leetcode

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.
Problem Statement Simplified
Give each children a cookies and each children have a dreed factor, give the result of how many children were satisfied.

Mistakes and Learning

Dont check for eact value - in greedy problems we should look for threhold not exact value.
At first used the 2 lists that stored the 2 arrays then remove the one by one from lists after going through the loop - The problem : If remove an element from index 2, then the element that was at index 3 will slides to index 2, will skip that element.

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.

Key Insight

If s[i] ≥ g[i] then child satisfied.
If s[i]<g[i] then child not satisfied.

Algorithm

Sort the 2 arrays.
Initialize 2 integers for child and cookies.
While the child is less than g.length and cookies is less than s.length.
If s[cookies] is greater than or equal to g[child].
Then child++.
End if.
Cookies++.
End for loop.
return child.

Algorithm in simple words

First, sort the 2 arrays so that we can we can match smallest available cookies with smallest greed factor.
Initialize 2 int pointers for child and cookies, then we will iterate and check if the current cookies can satify the current child if yes then we will move on to next child and next cookies, if not then we will move to next cookies . Return the child pointer with how many children are satisfied.

Java code

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child=0;
        int cookies=0;
        while(child<g.length && cookies<s.length){
            if(s[cookies]>=g[child]){
                child++;
            }
            cookies++;
        }
        return child;
    }
}

Time & Space Complexity

Time Complexity: O(n logn + m logm)
Space Complexity: O(logn + logm)

DEV Community