Assign Cookies - Complete Solution Guide

Assign Cookies is LeetCode problem 455, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i] , which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j] . If s[j] >= g[i] , we can assign the cookie j to the child i , and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number. Example 1: Input: g = [1,2,3], s

Detailed Explanation

The problem asks us to maximize the number of content children given two arrays: `g` representing the greed factor of each child (minimum cookie size they'll accept), and `s` representing the size of each cookie. We can only give each child at most one cookie. A child is content if they receive a cookie whose size is greater than or equal to their greed factor. The goal is to find the maximum number of children who can be made content.

Solution Approach

The provided solutions use a greedy approach. First, both the `g` and `s` arrays are sorted in ascending order. Then, we iterate through both arrays using two pointers. For each child, we try to find the smallest cookie that satisfies their greed. If a cookie is found that satisfies the child, we increment both pointers (child and cookie). If a cookie is too small, we move on to the next larger cookie. The number of content children is tracked, and returned at the end.

Step-by-Step Algorithm

1. Step 1: Sort the `g` array (greed factors of children) in ascending order.
2. Step 2: Sort the `s` array (cookie sizes) in ascending order.
3. Step 3: Initialize two pointers, `i` and `j`, to 0. `i` points to the current child and `j` points to the current cookie.
4. Step 4: Initialize `count` to 0, which represents the number of content children.
5. Step 5: While `i` is less than the length of `g` and `j` is less than the length of `s`:
6. Step 6: If `s[j]` is greater than or equal to `g[i]`, it means the current cookie can satisfy the current child. Increment `count`, `i`, and `j`.
7. Step 7: Otherwise, if `s[j]` is less than `g[i]`, it means the current cookie is too small for the current child. Increment `j` to consider the next cookie.
8. Step 8: After the loop finishes, return `count`.

Key Insights

• Insight 1: Sorting both the greed factors and cookie sizes allows us to efficiently iterate and make greedy decisions.
• Insight 2: A greedy approach of assigning the smallest possible cookie that satisfies a child's greed is optimal. This prevents us from using larger cookies unnecessarily and potentially leaving other children unsatisfied.
• Insight 3: If we don't sort, we would need to compare each cookie with each child, resulting in a much less efficient solution.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Greedy, Sorting.

Companies

Asked at: Accenture, Atlassian.