{"id":939,"date":"2025-08-21T11:13:09","date_gmt":"2025-08-21T05:43:09","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=939"},"modified":"2025-08-21T11:13:11","modified_gmt":"2025-08-21T05:43:11","slug":"assign-cookies","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/assign-cookies\/","title":{"rendered":"Assign Cookies | Leetcode 455 | Optimal Greedy Solution"},"content":{"rendered":"\n<p>When preparing for coding interviews, one of the common patterns you\u2019ll come across is the <strong>Greedy Algorithm<\/strong>. A great example of this is the <strong>Assign Cookies<\/strong> problem on Leetcode.<\/p>\n\n\n\n<p>In this blog, we\u2019ll carefully break down the problem, understand the intuition behind solving it, and then look at the <strong>optimal Python solution<\/strong> with clear explanations.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/assign-cookies\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Problem Statement \u2013 What Does the Problem Say?<\/h2>\n\n\n\n<p>You are given:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>An array <strong>g<\/strong>, where each element <code>g[i]<\/code> represents the <strong>greed factor<\/strong> of a child (the minimum size of a cookie they need to be content).<\/li>\n\n\n\n<li>An array <strong>s<\/strong>, where each element <code>s[j]<\/code> represents the <strong>size of a cookie<\/strong>.<\/li>\n<\/ul>\n\n\n\n<p>Your task is to <strong>assign cookies<\/strong> to children in such a way that:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Each child gets at most <strong>one cookie<\/strong>.<\/li>\n\n\n\n<li>A child is content if the cookie\u2019s size is <strong>greater than or equal<\/strong> to their greed factor.<\/li>\n\n\n\n<li>You want to maximize the <strong>number of content children<\/strong>.<\/li>\n<\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Input: g = &#91;1,2,3], s = &#91;1,1]\nOutput: 1\nExplanation: \nYou have 3 children with greed factors &#91;1,2,3] and 2 cookies of sizes &#91;1,1].\n- You can only make the child with greed 1 content.\nSo, the answer is 1.<\/code><\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Input: g = &#91;1,2], s = &#91;1,2,3]\nOutput: 2\nExplanation:\nYou have 2 children with greed factors &#91;1,2] and 3 cookies &#91;1,2,3].\n- Assign cookie of size 1 to child with greed 1.\n- Assign cookie of size 2 to child with greed 2.\nBoth children are satisfied \u2192 answer is 2.<\/code><\/pre>\n\n\n\n<p>So the challenge is: <strong>How do we maximize the number of content children using the available cookies?<\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Intuition and Approach (Optimal \u2013 Greedy)<\/h2>\n\n\n\n<p>The key idea here is:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A <strong>smaller cookie<\/strong> should be given to the <strong>least greedy child<\/strong> (the one with the smallest greed factor).<\/li>\n\n\n\n<li>If we waste a big cookie on a child who only needs a small one, we might not have enough cookies left for greedier children.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Steps to Solve:<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Sort both arrays<\/strong><code>g<\/code> and <code>s<\/code> in ascending order.\n<ul class=\"wp-block-list\">\n<li>This ensures we can always try to satisfy the least greedy child first.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Use <strong>two pointers<\/strong>:\n<ul class=\"wp-block-list\">\n<li>One (<code>left<\/code>) for iterating over children.<\/li>\n\n\n\n<li>One (<code>right<\/code>) for iterating over cookies.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Compare the current child\u2019s greed <code>g[left]<\/code> with the current cookie size <code>s[right]<\/code>.\n<ul class=\"wp-block-list\">\n<li>If <code>s[right] >= g[left]<\/code>, it means this cookie can satisfy the child \u2192 assign the cookie, move both pointers forward.<\/li>\n\n\n\n<li>Otherwise, move the cookie pointer <code>right<\/code> forward to try the next (larger) cookie.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Continue until either all children are satisfied or all cookies are used.<\/li>\n<\/ol>\n\n\n\n<p>This greedy method ensures that every child who can be satisfied gets the <strong>smallest possible cookie<\/strong> available, leaving bigger cookies for greedier children.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Implementation<\/h2>\n\n\n\n<p>Here\u2019s the Python code provided for the optimal greedy solution (with added comments for clarity):<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def findContentChildren(self, g: List[int], s: List[int]) -&gt; int:\n        n = len(g)\n        m = len(s)\n        \n        # Sort greed factors and cookie sizes\n        g.sort()\n        s.sort()\n        \n        left = 0   # Pointer for children\n        right = 0  # Pointer for cookies\n        count = 0  # Number of satisfied children\n        \n        # Assign cookies greedily\n        while left &lt; n and right &lt; m:\n            if g[left] &lt;= s[right]:   # If cookie satisfies the child's greed\n                count += 1            # Child is content\n                left += 1             # Move to next child\n            right += 1                # Move to next cookie\n        \n        return count\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">findContentChildren<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">g<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">s<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(g)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        m = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(s)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Sort greed factors and cookie sizes<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        g.sort()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        s.sort()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">   <\/span><span style=\"color: #6A9955\"># Pointer for children<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        right = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Pointer for cookies<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        count = <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Number of satisfied children<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Assign cookies greedily<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> left &lt; n <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> right &lt; m:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> g[left] &lt;= s[right]:   <\/span><span style=\"color: #6A9955\"># If cookie satisfies the child&#39;s greed<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                count += <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Child is content<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                left += <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">             <\/span><span style=\"color: #6A9955\"># Move to next child<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            right += <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Move to next cookie<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> count<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Explanation<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>First, we <strong>sort<\/strong> the children by their greed and cookies by size.<\/li>\n\n\n\n<li>Then we start assigning cookies one by one:\n<ul class=\"wp-block-list\">\n<li>If the current cookie is large enough for the current child \u2192 assign it and move to the next child.<\/li>\n\n\n\n<li>If not, try the next cookie.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>The <code>count<\/code> variable keeps track of how many children have been made content.<\/li>\n\n\n\n<li>The loop continues until either all children are checked or all cookies are used.<\/li>\n<\/ul>\n\n\n\n<p>This way, every child gets the <strong>smallest sufficient cookie<\/strong>, maximizing the total number of content children.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Time and Space Complexity<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Sorting children: <strong>O(n log n)<\/strong><\/li>\n\n\n\n<li>Sorting cookies: <strong>O(m log m)<\/strong><\/li>\n\n\n\n<li>Two-pointer assignment loop: <strong>O(n + m)<\/strong><\/li>\n\n\n\n<li><strong>Overall: O(n log n + m log m)<\/strong><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Sorting is done in-place, and we use only a few extra variables.<\/li>\n\n\n\n<li><strong>O(1)<\/strong> additional space.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p>In simpler terms: The solution is efficient because even though we sort both lists, the rest of the process only requires one pass.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>The <strong>Assign Cookies<\/strong> problem is a classic example of a <strong>Greedy Algorithm<\/strong> where:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We always assign the smallest available cookie that can satisfy a child.<\/li>\n\n\n\n<li>Sorting helps us efficiently match cookies with children.<\/li>\n<\/ul>\n\n\n\n<p>This approach ensures we maximize the number of happy children in <strong>O(n log n + m log m)<\/strong> time, which is optimal for this problem.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>When preparing for coding interviews, one of the common patterns you\u2019ll come across is the Greedy Algorithm. A great example of this is the Assign Cookies problem on Leetcode. In this blog, we\u2019ll carefully break down the problem, understand the intuition behind solving it, and then look at the optimal Python solution with clear explanations.<\/p>\n","protected":false},"author":1,"featured_media":941,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,4],"tags":[8,41],"class_list":{"0":"post-939","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-beginner","9":"tag-easy","10":"tag-greedy-algorithm"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/assign-cookies-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/939","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=939"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/939\/revisions"}],"predecessor-version":[{"id":945,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/939\/revisions\/945"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/941"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=939"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=939"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=939"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}