LeetCode #455 Assign Cookies Solution & Explanation

LeetCode Problem

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.

Solution

In our solution, we begin by sorting the greed factors and cookie sizes.

We then implement a greedy algorithm using two pointers to iterate through the sorted arrays of greed factors and cookie sizes. Within a loop over the cookie sizes, we check if the current cookie can satisfy the greed factor of the current child. If so, we increment the child pointer, indicating a content child, and move on to the next cookie.

This process continues until either all children are satisfied or no more cookies are available.

C# Solution

Solution1

public class Solution {
    public int FindContentChildren(int[] g, int[] s) {
        Array.Sort(g);
        Array.Sort(s);

        int i=0;
        foreach(var sItem in s){
            if(sItem>=g[i]){
                i+=1;
            }
            if(i==g.Length){
                return i;
            }
        }
        return i;
    }
}

Or you can write it with a two pointer version.

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++;
        }

        return i;
    }
}

Java Solution

Solution1

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i=0;
        for(int sItem : s){
            if(sItem>=g[i]){
                i+=1;
            }
            if(i==g.length){
                return i;
            }
        }
        return i;
    }
}

Python3 Solution

Solution1

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        i=0

        for sItem in s:
            if(sItem>=g[i]):
                i+=1
            
            if(i==len(g)):
                return i
        
        return i

Conclusion

If I were a parent, I would simply give each child cookies of the same size. Easy and fair 🍪🍪🍪

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Assign Cookies – LeetCode

Some Random LeetCode posts