Assign Cookies

Intuition

The goal is to maximize the number of students who can be satisfied with the given cookies. By sorting both the students' greed factors and the cookie sizes, we can efficiently assign the smallest available cookie that satisfies each student's greed. We iterate through the arrays, assigning cookies to students until we either run out of students or cookies, ensuring the maximum number of satisfied students.

Approach

Sort both the students' greed and cookie sizes to efficiently pair the smallest cookies with the least greedy children.
Use two pointers to iterate through the arrays, representing the smallest available cookie and the least greedy child.
For each pair, check if the current cookie can satisfy the current child's greed.
If a child's greed is satisfied, move to the next child; always move to the next cookie.
The final count of satisfied children indicates the maximum number of children who can be content with the given cookies.

Dry Run

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    // Function to find the maximum number of content children
    int findMaximumCookieStudents(vector<int>& Student, vector<int>& Cookie) {
        int n = Student.size();
        int m = Cookie.size();
        // Pointers
        int l = 0, r = 0;
        // Sorting of vectors
        sort(Student.begin(), Student.end());
        sort(Cookie.begin(), Cookie.end());

        // Traverse through both arrays
        while (l < n && r < m) {
            /*If the current cookie can satisfy 
            the current student, move to the 
            next student*/
            if (Cookie[r] >= Student[l]) {
                l++;
            }
            // Move to next cookie
            r++;
        }
        // Return the number of students who got cookies
        return l; 
    }
};
int main() {
    // Example input
    vector<int> Student = {1, 2};
    vector<int> Cookie = {1, 2, 3};

    // Create a Solution object
    Solution solution;

    // Call the findMaximumCookieStudents function
    int result = solution.findMaximumCookieStudents(Student, Cookie);

    // Output the result
    cout << "Number of students satisfied: " << result << endl;

    return 0;
}
import java.util.*;

class Solution {
    public int findMaximumCookieStudents(int[] Student, int[] Cookie) {
        int n = Student.length;
        int m = Cookie.length;
        // Pointers
        int l = 0, r = 0;
        // Sorting of arrays
        Arrays.sort(Student);
        Arrays.sort(Cookie);

        // Traverse through both arrays
        while (l < n && r < m) {
            /*If the current cookie can satisfy 
            the current student, move to the 
            next student*/
            if (Cookie[r] >= Student[l]) {
                l++;
            }
            // Move to next cookie
            r++;
        }
        // Return number of students
        return l; 
    }

    public static void main(String[] args) {
        // Example input
        int[] Student = {1, 2};
        int[] Cookie = {1, 2, 3};

        // Create a Solution object
        Solution solution = new Solution();

        // Call the findMaximumCookieStudents function
        int result = solution.findMaximumCookieStudents(Student, Cookie);

        // Output the result
        System.out.println("Number of students satisfied: " + result);
    }
}
class Solution:
    def findMaximumCookieStudents(self, Student, Cookie):
        n = len(Student)
        m = len(Cookie)
        # Pointers
        l, r = 0, 0
        # Sorting of lists
        Student.sort()
        Cookie.sort()

        # Traverse through both lists
        while l < n and r < m:
            """If the current cookie can satisfy 
            the current student, move to the 
            next student"""
            if Cookie[r] >= Student[l]:
                l += 1
            # Move to next cookie
            r += 1
        # Return number of students
        return l

# Example input
Student = [1, 2]
Cookie = [1, 2, 3]

# Create a Solution object
solution = Solution()

# Call the findMaximumCookieStudents function
result = solution.findMaximumCookieStudents(Student, Cookie)

# Output the result
print("Number of students satisfied:", result)
class Solution {
    findMaximumCookieStudents(Student, Cookie) {
        let n = Student.length;
        let m = Cookie.length;
        // Pointers
        let l = 0, r = 0;
        // Sorting of arrays
        Student.sort((a, b) => a - b);
        Cookie.sort((a, b) => a - b);

        // Traverse through both arrays
        while (l < n && r < m) {
            /*If the current cookie can satisfy 
            the current student, move to the 
            next student*/
            if (Cookie[r] >= Student[l]) {
                l++;
            }
            // Move to next cookie
            r++;
        }
        // Return number of students
        return l; 
    }
}

// Example input
const Student = [1, 2];
const Cookie = [1, 2, 3];

// Create a Solution object
const solution = new Solution();

// Call the findMaximumCookieStudents function
const result = solution.findMaximumCookieStudents(Student, Cookie);

// Output the result
console.log("Number of students satisfied:", result);

Complexity Analysis

Time Complexity: O(N logN + M logM + M) where N is the length of the student array, and M is the length of the cookies array. Sorting the student array takes O(N logN) time, and sorting the cookies array takes O(M logM) time. After sorting, we iterate through the arrays up to M times, where M is the number of cookies. Each student and each cookie is considered at most once, making the time complexity of this iteration linear, which is O(M). Therefore, the total time complexity is O(N logN + M logM + M). Space Complexity: O(1) no extra space used.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code