Assign Cookies Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon
algorithms coding Greedy Interview interviewprep LeetCode LeetCodeSolutionsViews 6284

The problem Assign cookies Leetcode Solution provides with two arrays. One of the arrays represents the size of the cookies and the other represents the greediness of the children. The problem states that you are the parent of children, and you want the maximum number of children to be content. You can only give one cookie to a child. Find the maximum number of content children. Let’s take a few examples first.

g = [1,2,3], s = [1,1]
1

Explanation: We have two cookies of size 1 each, and three children with different content values. We can make only a single child content that has greediness value 1. Since the other two children require larger cookies.

Assign Cookies Leetcode Solution

g = [1,2], s = [1,2,3]
2

Explanation: We can make both of the children feel content because the cookies that we have are greater or equal to the required sizes. Thus the output is 2.

Approach for Assign Cookies Leetcode Solution

The problem Assign Cookies Leetcode Solution asks us to find the maximum number of content children if we can give only a single cookie to a child. Thus the best approach is to greedily try to make the least greedy child feel content with the smallest cookie that can be used. So, to simulate this process we sort both the given arrays and try to assign the cookies to the children. If we can’t assign the current cookie to the current child then we try the next cookie until we satisfy the current child. Because if we can not satisfy the current child, we cannot satisfy the next children with the current cookie.

Code

C++ code for Assign Cookies Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int numberOfChildren = g.size(), numberOfCookies = s.size();
    int cookie = 0, answer = 0;
    for(int i=0;i<numberOfChildren && cookie<numberOfCookies;){
        if(s[cookie] >= g[i]){
            i++;
            answer++;
        }
        cookie++;
    }
    return answer;
}

int main(){
    vector<int> g = {1, 2, 3};
    vector<int> s = {1, 1};

    cout<<findContentChildren(g, s);
}

1

Java code for Assign Cookies Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int numberOfChildren = g.length;
        int numberOfCookies = s.length;
        int cookie = 0, answer = 0;
        for(int i=0;i<numberOfChildren && cookie<numberOfCookies;){
            if(s[cookie] >= g[i]){
                i++;
                answer++;
            }
            cookie++;
        }
        return answer;
    }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] g = {1, 2, 3};
    int[] s = {1, 1};
 
    System.out.println(findContentChildren(g, s));
  }
}
1

Complexity Analysis

Time Complexity

O(NlogN), because of the time required to sort the given arrays. Here N represents the number of elements in given arrays.

Space Complexity

O(NlogN), because of the space required to sort the given arrays. Again the N represents the number of elements in the arrays.

Translate »