# Lemonade Change
**Difficulty:** EASY
[External](https://leetcode.com/problems/lemonade-change)
Canonical: https://scaleengineer.com/dsa/problems/lemonade-change
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Zalando](https://scaleengineer.com/companies/zalando)
---
## Problem
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_.

**Example 1:**

**Input:** bills = [5,5,5,10,20]
**Output:** true
**Explanation:** 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

**Example 2:**

**Input:** bills = [5,5,10,10,20]
**Output:** false
**Explanation:** 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can not give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.

**Constraints:**

* `1 <= bills.length <= 105`
* `bills[i]` is either `5`, `10`, or `20`.

# Approaches
## Simulation with Hash Map
This approach simulates the transaction process by keeping track of the available change using a hash map. We iterate through each customer's bill and update the counts of $5 and $10 bills we hold. For each transaction, we check if we have the necessary bills to provide the correct change.
**Time:** O(N), where N is the number of customers (the length of the `bills` array). We process each bill in a single pass. · **Space:** O(1), as the hash map will store at most two keys (5 and 10), regardless of the input size. The space usage is constant.
**Pros:** Conceptually straightforward, directly mapping the problem's state (our cash drawer) to a data structure.; Easily extensible if more bill denominations were introduced.
**Cons:** Slightly more overhead than using simple variables due to the nature of hash maps (hashing, potential collisions).; The code can be a bit more verbose compared to a more optimized approach.
### Explanation
In this method, we use a hash map to represent our cash drawer, mapping bill denominations (like 5 and 10) to their respective counts. We don't need to track $20 bills since they cannot be used as change for a $5 lemonade.

We process the `bills` array sequentially. 
- When a customer pays with a `$5` bill, we simply increment the count of $5 bills in our map.
- When a customer pays with a `$10` bill, we need to provide `$5` in change. We check our map for an available $5 bill. If we have one, we decrement its count and increment the count of $10 bills. If not, we cannot make change, and we return `false`.
- When a customer pays with a `$20` bill, we need `$15` in change. The best strategy is to be greedy and use larger bills first to save smaller, more versatile bills. We first try to use one `$10` and one `$5` bill. If that's not possible, we try to use three `$5` bills. If neither option is available, we return `false`.

If we successfully process all bills, we return `true`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean lemonadeChange(int[] bills) {
        Map<Integer, Integer> change = new HashMap<>();
        change.put(5, 0);
        change.put(10, 0);

        for (int bill : bills) {
            if (bill == 5) {
                change.put(5, change.get(5) + 1);
            } else if (bill == 10) {
                if (change.get(5) > 0) {
                    change.put(5, change.get(5) - 1);
                    change.put(10, change.get(10) + 1);
                } else {
                    return false;
                }
            } else { // bill is 20
                // Greedy: try to use one $10 and one $5 first
                if (change.get(10) > 0 && change.get(5) > 0) {
                    change.put(10, change.get(10) - 1);
                    change.put(5, change.get(5) - 1);
                } else if (change.get(5) >= 3) {
                    change.put(5, change.get(5) - 3);
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize a `HashMap<Integer, Integer>` to store counts of $5 and $10 bills.
- Iterate through the `bills` array, one bill at a time.
- If the bill is $5, increment the count of $5 bills in the map.
- If the bill is $10, check if a $5 bill is available. If yes, decrement the $5 count and increment the $10 count. If no, return `false`.
- If the bill is $20, try to make change for $15:
  - First, check if a $10 bill and a $5 bill are available. If yes, decrement their counts.
  - Else, check if three $5 bills are available. If yes, decrement the $5 count by 3.
  - If neither change combination is possible, return `false`.
- If the loop finishes without returning `false`, it means we can provide change to all customers. Return `true`.

## Greedy Approach with Constant Space
This is a more optimized approach that uses two integer variables to keep track of the counts of $5 and $10 bills. It follows a greedy strategy: for each customer, we process their payment and try to make change. When making change for a $20 bill, we greedily prioritize using a $10 bill over three $5 bills, as $5 bills are more flexible for future transactions.
**Time:** O(N), where N is the length of the `bills` array. We iterate through the array once. · **Space:** O(1). We only use a constant number of variables (`fiveCount`, `tenCount`) to store the state, regardless of the input size.
**Pros:** Highly efficient with minimal overhead.; Simple and clean implementation.; Optimal solution in terms of both time and space complexity.
**Cons:** The logic is slightly less direct than a map-based simulation if one is not familiar with greedy algorithms.; Less extensible if the problem were to include many more bill types, where a map might become more manageable.
### Explanation
This approach improves upon the hash map method by recognizing that we only need to track the counts of two types of bills: $5 and $10. Instead of a hash map, we can use two simple integer variables, `fiveCount` and `tenCount`, which is more efficient.

The logic remains the same. We iterate through the `bills` array:
- If the bill is `$5`, we increment `fiveCount`.
- If the bill is `$10`, we need a `$5` for change. We decrement `fiveCount` and increment `tenCount`. If we don't have a $5 bill (`fiveCount` was 0), we fail and return `false`.
- If the bill is `$20`, we need `$15` change. We apply a greedy strategy. It's always better to use a `$10` and a `$5` bill for change if possible, because this saves our `$5` bills, which are more versatile (they can make change for both $10 and $20 bills). So, we first check if we have both a `$10` and a `$5`. If so, we use them. If not, our only other option is to use three `$5` bills. If we can't do that either, we return `false`.

If we successfully process all customers, we return `true`.

```java
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int fiveCount = 0;
        int tenCount = 0;

        for (int bill : bills) {
            if (bill == 5) {
                fiveCount++;
            } else if (bill == 10) {
                if (fiveCount == 0) {
                    return false;
                }
                fiveCount--;
                tenCount++;
            } else { // bill is 20
                // We need to give back $15
                // Greedy choice: use one $10 and one $5
                if (tenCount > 0 && fiveCount > 0) {
                    tenCount--;
                    fiveCount--;
                } else if (fiveCount >= 3) {
                    // Alternative: use three $5s
                    fiveCount -= 3;
                } else {
                    // Cannot make change
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize two integer variables, `five_count = 0` and `ten_count = 0`.
- Iterate through the `bills` array.
- For a $5 bill, increment `five_count`.
- For a $10 bill, you need to give $5 change. Decrement `five_count` and increment `ten_count`. If `five_count` becomes negative after decrementing, it means you didn't have a $5 bill, so return `false`.
- For a $20 bill, you need to give $15 change. The greedy strategy is to use a $10 bill and a $5 bill first, as this preserves the more versatile $5 bills.
  - Check if you have at least one $10 bill and one $5 bill (`ten_count > 0` and `five_count > 0`). If so, decrement both `ten_count` and `five_count`.
  - Otherwise, check if you have at least three $5 bills (`five_count >= 3`). If so, decrement `five_count` by 3.
  - If you cannot make change with either combination, return `false`.
- If the loop completes, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean lemonadeChange(int[] bills) {
    int five = 0, ten = 0;
    for (int v : bills) {
      switch (v) { case 5 -> ++ five ; case 10 -> { ++ ten ; -- five ; } case 20 -> { if ( ten > 0 ) { -- ten ; -- five ; } else { five -= 3 ; } } } if ( five < 0 ) { return false ; } } return true ; } }

```

### JavaScript

```javascript
export function lemonadeChange ( bills ) { let [ five , ten ] = [ 0 , 0 ]; for ( const x of bills ) { switch ( x ) { case 5 : five ++ ; break ; case 10 : five -- ; ten ++ ; break ; case 20 : if ( ten ) { ten -- ; five -- ; } else { five -= 3 ; } break ; } if ( five < 0 ) { return false ; } } return true ; }
```

### CPP

```cpp
class Solution {
public:
  bool lemonadeChange(vector<int> &bills) {
    int five = 0, ten = 10;
    for (int v : bills) {
      if (v == 5) {
        ++five;
      } else if (v == 10) {
        ++ten;
        --five;
      } else {
        if (ten) {
          --ten;
          --five;
        } else {
          five -= 3;
        }
      }
      if (five < 0) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool: five = ten = 0 for v in bills: if v == 5: five += 1 elif v == 10: ten += 1 five -= 1 else: if ten: ten -= 1 five -= 1 else: five -= 3 if five < 0: return False return True

```