LeetCode Daily Question 15/08/2024 - 860 Lemonade Change

Problem Description:

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5. Note that you do not have any change in hand at first. Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

from typing import List
class Solution:
  def lemonadeChange(self, bills: List[int]) -> bool:
    fives, tens = 0
    for bill in bills:
      if bill == 5:
        fives += 1
      elif bill == 10:
        tens += 1
        fives -= 1
      else:
        if tens > 0:
          tens -= 1
          fives -= 1
        else:
          fives -= 3
    	if fives < 0:
      		return False
  	return True

Explanation:

The key to solving this question efficiently is to count the number of five dollar bills at the end of the traversal.

This is because, given any denomination of bills larger than 5, we must use some amount of 5 dollar bills as change.

So if we end up with negative amount of 5 dollar bills, we must not have enough change.

The cases are:
- the bill = 5, then we just add 1 to our five dollar bill counter.
- bill = 10, then we must use 1 five dollar bill as change, and we add 1 to the ten dollar bill counter.
- bill = 20, then we can either give 1 ten 1 five as change or 3 fives as change.

Putting these together

def lemonadeChange(bills):
  fives, tens = 0, 0
  for bill in bills:
    if bill == 5:
      fives += 1
    elif bill == 10:
      tens += 1
      fives -= 1
    else:
      if tens > 0:
        tens -= 1
        fives -= 1
      else:
        fives -= 3
    if fives < 0:
      return False
    
  return True

The time complexity of this solution is O(n), as we need to travers the entire array once. Space complexity is O(1) as each operation is done in constant time.

The full solution can be found near the top of this page.