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