algoadvance

Leetcode 455. Assign Cookies

Problem Statement

You are assigned to allocate cookies to children. Each child has a greed factor, representing the minimum size of the cookie they will be content with, and each cookie has a size. You want to maximize the number of satisfied children by giving each child at most one cookie.

Input:

• Two integer arrays g and s where g[i] is the greed factor of the i-th child, and s[j] is the size of the j-th cookie.

Output:

• Return the maximum number of children you can satisfy.

Example:

Input: g = [1, 2, 3], s = [1, 1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of the children are 1, 2, 3 and even though you have 2 cookies, since the cookies are both of size 1, only 1 child can be satisfied.

Input: g = [1, 2], s = [1, 2, 3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of the children are 1, 2, and you have cookies with sizes 1, 2, 3. You can satisfy 2 children.

Clarifying Questions

1. Are the arrays g and s guaranteed to be non-empty?
2. Can the greed factor and cookie sizes be zero?
3. Do we need to return the actual list of satisfied children or just the count?

Strategy

To maximize the number of satisfied children, we should always try to offer the smallest sufficient cookie to a child with the least possible greed. A greedy algorithm is highly appropriate for this problem.

1. Sort both g (greed factors) and s (cookie sizes).
2. Use two pointers to iterate through g and s:
   • Start with the smallest greed and the smallest cookie.
   • If the current cookie can satisfy the current child’s greed, move to the next child and next cookie.
   • Otherwise, move to the next cookie.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
        // Sort the greed factors and the cookies sizes
        std::sort(g.begin(), g.end());
        std::sort(s.begin(), s.end());
        
        // Initialize pointers for g and s
        int i = 0; // Pointer for children
        int j = 0; // Pointer for cookies
        
        // Iterate through the cookies and greed factors
        while (i < g.size() && j < s.size()) {
            if (s[j] >= g[i]) {
                // Cookie s[j] can satisfy the child g[i]
                i++;
            }
            // Move to the next cookie
            j++;
        }
        
        // The number of children satisfied
        return i;
    }
};

Time Complexity

• Sorting g and s will take (O(n \log n)) and (O(m \log m)) respectively, where (n) is the length of g and (m) is the length of s.
• The while loop will run in (O(n + m)) time because each pointer is incremented at most n or m times.

Thus, the overall time complexity is (O(n \log n + m \log m)). The space complexity is (O(1)) beyond the input storage, as no additional space proportional to the input size is used.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?