Solution Explanation: Assign Cookies

This problem asks us to maximize the number of children who receive a cookie that satisfies their greed factor. The solution leverages a greedy approach combined with sorting and two pointers.

Algorithm:

1. Sort: Sort both the g (greed factors) and s (cookie sizes) arrays in ascending order. Sorting ensures that we consider children with smaller greed factors first and cookies with smaller sizes first. This allows for a greedy strategy where we try to satisfy the least demanding children first.

2. Two Pointers: Use two pointers, i for the g array (children) and j for the s array (cookies). Both pointers start at index 0.

3. Iteration: Iterate through the children (g array). For each child:

   • Check if the current cookie (s[j]) is large enough to satisfy the child's greed (g[i]).
   • If s[j] >= g[i], the child is satisfied. Increment both i and j to move to the next child and cookie.
   • If s[j] < g[i], the current cookie is too small. Increment j to try the next larger cookie. The child remains unsatisfied for now.

4. Termination: The loop continues until either all children are satisfied (i reaches the end of g) or all cookies are used (j reaches the end of s).

5. Result: The number of satisfied children (i) is the solution.

Time Complexity: O(m log m + n log n), where m is the length of g and n is the length of s. This is dominated by the sorting step.

Space Complexity: O(log m + log n) in the best case (in-place sorting) or O(m + n) in the worst case (if a sorting algorithm that requires extra space is used). This represents the space used for sorting.

Code Examples:

The code examples below demonstrate the solution in various programming languages. They all follow the same algorithm: sorting, two pointers, and iterative comparison.

Python:

def findContentChildren(g, s):
    g.sort()
    s.sort()
    i = j = 0
    count = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:
            count += 1
            i += 1
            j += 1
        else:
            j += 1
    return count
 

Java:

import java.util.Arrays;
 
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0, count = 0;
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                count++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return count;
    }
}

C++:

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
        std::sort(g.begin(), g.end());
        std::sort(s.begin(), s.end());
        int i = 0, j = 0, count = 0;
        while (i < g.size() && j < s.size()) {
            if (s[j] >= g[i]) {
                count++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return count;
    }
};

JavaScript:

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    g.sort((a,b) => a - b);
    s.sort((a,b) => a - b);
    let i = 0, j = 0, count = 0;
    while(i < g.length && j < s.length){
        if(s[j] >= g[i]){
            count++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    return count;
};

These examples all showcase the efficient, greedy approach to solving the "Assign Cookies" problem. The variations in syntax are minor; the core algorithm remains the same across languages.