Lemonade Change

It has been a food-filled few days so let's massage the brain with an easy post: how to solve Leetcode #860 "Lemonade Change." In the problem, we are told that a lemonade costs $5, you the vendor have no change to start with, and buyers will pay with either a $5 bill, a $10 bill, or a $20 bill. Given an array of called bills containing only 5, 10, or 20, determine if you can provide the appropriate change at every transaction. If so, return true, if not, return false.

This problem is a Leetcode easy, and under the spell of too many carbs, seemed difficult at first, but honestly it's not much harder than fizzbuzz.

To start, let's deal with our edge cases. If we receive an empty array or the first value of the array is NOT equal to 5, we have to return false. In the latter case, we know that the seller does not have any change to start with, so any array that does not begin with 5 assumes change will be provided. That's impossible. So let's write that.

var lemonadeChange = function(bills) {
  if (!bills.length || bills[0] !== 5) return false
}

The next step is to figure out how to approach the problem. The approach requires us to iterate over the whole array and to compare values based on existing change. Effectively, we need to create a change drawer. I opted to do this as an object, where the keys correspond to the dollar amount of a bill and the values to the quantity of those bills: let change = {'5': 0, '10': 0, '20': 0} (remember that integers cannot be used as keys in JavaScript).

The next step is to consider all of the different scenarios and operate on our object accordingly. The function will iterate over the array, testing the input value against a series of if/else statements, each based on the value of the input.

The first one is easy. If the array value is 5, there is no need to produce change, so we simply increment the '5' key in our change object. (NB: I did not do this, but because any array that does not begin with 5 will return false, we could theoretically initiate the change object with '5' have a value of one, and begin iterating at array index 1 to save a smidgeon of time).

The second case requires us to address what happens if the array value is 10. In this case, we once again increment the appropriate value in the change object. But this time, we have to produce change. Given that there are only $5, $10, or $20 bills, we can only pay change with a $5 bill. If there is a $5 bill in the change object (that is, key 5 has a value greater than or equal to 1), we can produce change. So we have to decrement the value of the 5 key by one. If not, no change can be produced, so we should break the loop and return false.

The most complicated logic comes with a $20 bill. We start the same one, by increment the value of key '20' by one and then seeing if change can be produced. Change can be produced with a $10 and a $5 or three $5 bills. Because $5 bills are more necessary, we should check if there is a $10 and a $5 first. If so, decrement the corresponding keys by one. If not, see if there are three $5 bills. If so, decrement key 5 by three. If neither condition is true, once again break the loop and return false, because a situation has been produced where no change is available.

By inserting these return false statements throughout the loop, we have addressed any situation where it is impossible to produce correct change. That means, if the loop successfully completes by iterating over all values in bills, the return value must be true.

Check out the full function below. It's a lot of logic but all in all, pretty simple.

var lemonadeChange = function(bills) {
  if (!bills.length || bills[0] !== 5) return false
  let change = {'5': 0, '10': 0, '20': 0}
  for(let i = 0; i < bills.length; i++){
      if(bills[i] === 5){
          change['5']++
      } else if (bills[i] === 10){
          change['10']++
          if (change['5'] === 0){
              return false
          } else {
              change['5']--
          }
      } else {
          change['20']++
          if (change['10'] >= 1 && change['5'] >= 1){
              change['10']--
              change['5']--
          } else if (change['5'] >= 3){
              change['5'] -= 3
          } else {
              return false
          }
      }
  }
  return true
};