Problem Explanation

We have a list of children each with a greed factor which represents the minimum size of a cookie they will be content with. We also have a list of cookies each with a given size.

Our task is to distribute these cookies to the children such that we maximize the number of content children. A child will be content if the size of the cookie they receive is greater than or equal to their greed factor.

However, each child can receive at most one cookie.

Walkthrough

For example, let's say we have 3 children with greed factors [1,2,3] and we have 2 cookies of size [1,1]. In this case, we can only satisfy the child with a greed factor of 1, and the output will be 1.

On the other hand, if we have 2 children with greed factors [1,2] and we have 3 cookies of size [1,2,3], we can satisfy both children. Hence, the output will be 2.

Approach

The key idea of the solution is to sort the greed factors of the children and the sizes of the cookies. Then, we start from the smallest greed factor, and for each child, we find the smallest cookie that can satisfy the child. We continue this process until we run out of cookies or all children have been satisfied.

Java Solution

This is the Java implementation based on the approach mentioned above:

1
2java
3import java.util.Arrays;
4
5public class Solution {
6    public int findContentChildren(int[] g, int[] s) {
7        Arrays.sort(g);
8        Arrays.sort(s);
9        int i = 0;
10        for (int j = 0; j < s.length && i < g.length; ++j)
11            if (g[i] <= s[j])
12                ++i;
13        return i;
14    }
15}

Python Solution

This is the Python implementation based on the approach mentioned above:

1
2python
3class Solution(object):
4    def findContentChildren(self, g, s):
5        g.sort()
6        s.sort()
7
8        i = 0
9        for j in range(len(s)):
10            if i == len(g):
11                break
12            if g[i] <= s[j]:
13                i += 1
14
15        return i

JavaScript Solution

This is the JavaScript implementation based on the approach mentioned above:

1
2javascript
3var findContentChildren = function(g, s) {
4    g.sort((a, b) => a - b);
5    s.sort((a, b) => a - b);
6    let count = 0;
7    for (let i = 0; i < s.length; i++) {
8        if (s[i] >= g[count]) {
9            count++;
10        }
11    }
12    return count;
13};

C++ Solution

This is the C++ implementation based on the approach mentioned above:

1
2cpp
3class Solution {
4public:
5    int findContentChildren(vector<int>& g, vector<int>& s) {
6        sort(g.begin(), g.end());
7        sort(s.begin(), s.end());
8
9        int i = 0;
10        for (int j = 0; j < s.size() && i < g.size(); ++j)
11            if (g[i] <= s[j])
12                ++i;
13        return i;
14    }
15};

C# Solution

This is the C# implementation based on the approach mentioned above:

1
2csharp
3public class Solution {
4    public int FindContentChildren(int[] g, int[] s) {
5        Array.Sort(g);
6        Array.Sort(s);
7        int i = 0;
8        for (int j = 0; j < s.Length && i < g.Length; ++j)
9            if (g[i] <= s[j])
10                ++i;
11        return i;
12    }
13}

Conclusion

This problem seems quite simple at first, but if not approached correctly, it can become quite daunting. With a well-thought-out greedy approach, we can solve it quite easily. It is important to understand that sorting is the backbone of the solution which makes the implementation quite efficient and straightforward.

The time complexity of the solution is O(n log n), where n is the maximum size between the number of children and the number of cookies, due to the sorting operation. Once the arrays are sorted, we just iterate through them once which takes linear time.

The space complexity is O(1), as we do not use any additional data structures whose size is dependent on the input size. All we need are a few variables to keep track of the indices in the two arrays.

Remember - a happy child makes a happier world! The greedy strategy helps find the maximum number of satisfied children efficiently. Each language handles the problem with a slight syntax difference, but the algorithms for all mentioned languages - Java, JavaScript, Python, C++, and C# - achieve the same expected result.