{"id":952,"date":"2025-08-21T18:09:38","date_gmt":"2025-08-21T12:39:38","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=952"},"modified":"2025-08-21T18:09:40","modified_gmt":"2025-08-21T12:39:40","slug":"lemonade-change","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/lemonade-change\/","title":{"rendered":"Lemonade Change | Leetcode 860 | Greedy Solution"},"content":{"rendered":"\n

The Lemonade Change<\/strong> problem is a very popular coding interview question and a classic example of applying the Greedy Algorithm<\/strong>. It revolves around handling money transactions in the simplest possible way while ensuring that correct change is always provided.<\/p>\n\n\n\n

In this blog, we will carefully understand the problem, analyze why a greedy approach is the best choice here, and then go through the optimal Python solution with explanation and complexity analysis.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

\n\n\n\n

Problem Statement \u2013 What Does the Problem Say?<\/h2>\n\n\n\n

You are running a lemonade stand where each lemonade costs 5 dollars<\/strong>. Customers come in a queue, and each one pays using a bill of 5, 10, or 20 dollars<\/strong>.<\/p>\n\n\n\n

You must provide the correct change to each customer. Initially, you have no money in hand.<\/p>\n\n\n\n

Your task: Return True if you can give change to every customer in the queue, otherwise return False.<\/strong><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>: <\/span>bills = [5,5,5,10,20]<\/span><\/span>\nOutput<\/span>: <\/span>True<\/span><\/span>\nExplanation<\/span>:<\/span><\/span>\n- <\/span>Customer 1 pays 5 \u2192 no change needed.<\/span>  <\/span><\/span>\n- <\/span>Customer 2 pays 5 \u2192 no change needed.<\/span>  <\/span><\/span>\n- <\/span>Customer 3 pays 5 \u2192 no change needed.<\/span>  <\/span><\/span>\n- <\/span>Customer 4 pays 10 \u2192 give back one 5.<\/span>  <\/span><\/span>\n- <\/span>Customer 5 pays 20 \u2192 give back one 10 and one 5.<\/span>  <\/span><\/span>\nAll customers receive correct change, so the answer is True.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input: <\/span>bills<\/span> = [<\/span>5<\/span>,<\/span>5<\/span>,<\/span>10<\/span>,<\/span>10<\/span>,<\/span>20<\/span>]<\/span><\/span>\nOutput:<\/span> False<\/span><\/span>\nExplanation:<\/span><\/span>\n-<\/span> Customer<\/span> <\/span>1<\/span> pays <\/span>5<\/span> \u2192 no change needed.  <\/span><\/span>\n-<\/span> Customer<\/span> <\/span>2<\/span> pays <\/span>5<\/span> \u2192 no change needed.  <\/span><\/span>\n-<\/span> Customer<\/span> <\/span>3<\/span> pays <\/span>10<\/span> \u2192 give back one <\/span>5<\/span>.  <\/span><\/span>\n-<\/span> Customer<\/span> <\/span>4<\/span> pays <\/span>10<\/span> \u2192 give back one <\/span>5<\/span>.  <\/span><\/span>\n-<\/span> Customer<\/span> <\/span>5<\/span> pays <\/span>20<\/span> \u2192 need <\/span>15<\/span> as <\/span>change<\/span>,<\/span> but<\/span> only two 10s <\/span>available<\/span> (<\/span>no<\/span> <\/span>5<\/span>).  <\/span><\/span>\nCannot give correct change,<\/span> so<\/span> the answer is<\/span> False<\/span>.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
So the challenge is to simulate the process and ensure the right amount of change can always be given.<\/p>\n\n\n\n
\n\n\n\n
Intuition and Approach (Optimal \u2013 Greedy)<\/h2>\n\n\n\n
The greedy approach works perfectly for this problem. The key observation is:<\/p>\n\n\n\n