Lemonade Change

easy greedy array simulation

Problem

Each lemonade costs $5. Customers line up and pay with a $5, $10, or $20 bill. You start with no change and must give correct change to each customer in order. Return true if you can serve every customer.

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

Outputtrue

Collect three $5, give one back for the $10, then a $10 + $5 for the $20.

bills (5, 10, or 20, comma-separated)

def lemonade_change(bills):
    five = ten = 0
    for b in bills:
        if b == 5:
            five += 1
        elif b == 10:
            if not five: return False
            five -= 1; ten += 1
        else:
            if ten and five:
                ten -= 1; five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False
    return True

function lemonadeChange(bills) {
  let five = 0, ten = 0;
  for (const b of bills) {
    if (b === 5) five++;
    else if (b === 10) {
      if (!five) return false;
      five--; ten++;
    } else {
      if (ten && five) { ten--; five--; }
      else if (five >= 3) five -= 3;
      else return false;
    }
  }
  return true;
}

boolean lemonadeChange(int[] bills) {
    int five = 0, ten = 0;
    for (int b : bills) {
        if (b == 5) five++;
        else if (b == 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;
}

bool lemonadeChange(vector<int>& bills) {
    int five = 0, ten = 0;
    for (int b : bills) {
        if (b == 5) five++;
        else if (b == 10) {
            if (!five) return false;
            five--; ten++;
        } else {
            if (ten && five) { ten--; five--; }
            else if (five >= 3) five -= 3;
            else return false;
        }
    }
    return true;
}

Explanation

This is just a simulation: we walk through the line of customers one by one and try to give correct change. We only ever need to remember how many $5 and $10 bills we hold — twenties are never useful for making change, so we don't count them.

A $5 payment needs no change, so we just keep it (five++). A $10 payment needs $5 back, so we must have a five (five--; ten++); if we don't, we fail.

A $20 payment needs $15 in change, and there are two ways to make it: a $10 plus a $5, or three $5 bills. The greedy trick is to prefer the ten + five combo first, because $5 bills are precious — they are the only way to give change for a $10. We only fall back to three fives when no ten is available.

If a customer pays $20 and we can do neither, we return false immediately. If everyone is served, we return true.

Example: bills = [5, 5, 5, 10, 20]. Collect three $5. The $10 customer takes one $5 back (now $5×2, $10×1). The $20 customer gets $10 + $5 (now $5×1). Everyone served, so the answer is true.

Time: O(n) Space: O(1)