easy

Lemonade Change

Check whether you can give correct change to every customer buying lemonade in order.

1. Define the problem

Lemonade Change

Lemonade costs $5. Customers stand in a line and each pays with a $5, $10, or $20 bill, one at a time. You start with no change, and must give the correct change to every customer using only the bills you have collected so far. Return true if you can serve every customer in order. A greedy rule works: for a $20 bill, prefer giving a $10 and a $5 as change over three $5 bills, since $5 bills are more flexible for making change later.

Constraints

  • 1 ≤ bills.length ≤ 105
  • billsi is either 5, 10, or 20

Example

Inputbills = [5, 5, 5, 10, 20]
Outputtrue

Explanation The first three customers pay with $5 bills. The fourth gets one $5 back as change for their $10. The fifth gets a $10 and a $5 back for their $20.

2. Visualize the solution

Track $5 and $10 bills on hand as customers pay

Track $5 and $10 bills on hand as customers pay
Statusfives=0, tens=0

Customer pays with a $5 bill — no change needed. fives becomes 1.

What happens in this step

five=0, ten=0 — bill = $5

A $5 bill needs no change, so it is simply banked: five becomes 1. This is the locally-best move since $5 bills are the most flexible change to hold onto.
Step 1 of 5

Steps to visualize

  1. A $5 bill needs no change — just add it to your $5 count.
  2. A $10 bill needs one $5 back — if you have none, you fail immediately.
  3. A $20 bill needs $15 back — prefer a $10 and a $5 if both are available.
  4. Only fall back to three $5 bills for a $20 if you have no $10 bill on hand.
  5. If every customer gets correct change, lemonadeChange returns true.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track $5 and $10 bills on hand as customers pay
Statusfives=0, tens=0

Customer pays with a $5 bill — no change needed. fives becomes 1.

What happens in this step

five=0, ten=0 — bill = $5

A $5 bill needs no change, so it is simply banked: five becomes 1. This is the locally-best move since $5 bills are the most flexible change to hold onto.
Step 1 of 5
4. Solution

Solution

solution.tsTypeScript
function lemonadeChange(bills) {
  let five = 0;
  let ten = 0;

  for (const bill of bills) {
    if (bill === 5) {
      five++;
    } else if (bill === 10) {
      if (five === 0) return false;
      five--;
      ten++;
    } else {
      if (ten > 0 && five > 0) {
        ten--;
        five--;
      } else if (five >= 3) {
        five -= 3;
      } else {
        return false;
      }
    }
  }

  return true;
}
Time
O(n)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
bills = [5, 5, 5, 10, 20]trueexample from the docstring
bills = [5, 5, 10, 10, 20]falseruns out of $5 bills before the final $20
bills = [5, 5, 5, 5]trueonly $5 bills, no change ever needed
bills = [10]falsethe very first customer pays with a $10 and no change exists yet
bills = [5, 20]falseonly one $5 on hand, not enough to make $15 change for a $20
bills = [5, 5, 20]falsetwo $5 bills are still not enough for a $20 without a $10
bills = [5, 5, 5, 20]truefalls back to three $5 bills when no $10 is available

Keep reading

TopicDescription
Greedy AlgorithmsMake the locally best choice at each step and never look back, useful when local optima add up to a global optimum.
Assign CookiesHand out cookies to as many children as possible while satisfying their minimum size needs.
Jump GameCheck whether you can reach the last position of an array given each element's max jump length.
Jump Game IIFind the minimum number of jumps needed to reach the last position of an array.
Gas StationFind the starting gas station that lets you complete a full circuit without running out of fuel.
Task SchedulerFind the minimum time needed to finish a list of tasks with a required cooldown between repeats.