Welcome to Subscribe On Youtube

860. Lemonade Change

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.

 

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.

Solutions

Solution 1: Direct Implementation

We traverse the bill array $bills$ from front to back. For the currently traversed bill:

  • If it is $5$ USD, just accept it directly;
  • If it is $10$ USD, then the change needs to be $5$ USD;
  • If it is $20$ US dollars, then you need to change $15$ US dollars. There are two ways to make change: change $1$ US dollars $10$ US dollars + $1$ US dollars $5$ US dollars; change $3$ US dollars $5$ US dollars. We give priority to the first method of change. If there are not enough $10$ dollars, then use the second method;
  • If the amount of $5$ dollars is found to be insufficient, return false directly.

The end of the traversal means that we have not encountered a situation where change cannot be found, and we can return true.

Time complexity $O(n)$, space complexity $O(1)$. Where $n$ is the length of the bill array $bills$.

Solution 2: One-liner

This implementation uses dynamic programming. The variables in the code maintain exactly the state needed to construct the result.

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • func lemonadeChange(bills []int) bool {
	five, ten := 0, 0
	for _, v := range bills {
		if v == 5 {
			five++
		} else if v == 10 {
			ten++
			five--
		} else {
			if ten > 0 {
				ten--
				five--
			} else {
				five -= 3
			}
		}
		if five < 0 {
			return false
		}
	}
	return true
}

  • function lemonadeChange(bills: number[]): boolean {
    let five = 0;
    let ten = 0;
    for (let bill of bills) {
        switch (bill) {
            case 5:
                five++;
                break;
            case 10:
                five--;
                ten++;
                break;
            case 20:
                if (ten !== 0) {
                    ten -= 1;
                    bill -= 10;
                }
                five -= bill / 5 - 1;
                break;
        }

        if (five < 0) {
            return false;
        }
    }
    return true;
}


// Solution 2
const lemonadeChange = (bills: number[], f = 0, t = 0): boolean =>
    bills.every(
        x => (
            (!(x ^ 5) && ++f) ||
                (!(x ^ 10) && (--f, ++t)) ||
                (!(x ^ 20) && (t ? (f--, t--) : (f -= 3), 1)),
            f >= 0
        ),
    );


  • impl Solution {
    pub fn lemonade_change(bills: Vec<i32>) -> bool {
        let (mut five, mut ten) = (0, 0);
        for bill in bills.iter() {
            match bill {
                5 => {
                    five += 1;
                }
                10 => {
                    five -= 1;
                    ten += 1;
                }
                _ => {
                    if ten != 0 {
                        ten -= 1;
                        five -= 1;
                    } else {
                        five -= 3;
                    }
                }
            }

            if five < 0 {
                return false;
            }
        }
        true
    }
}


  • 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;
}


// Solution 2
const lemonadeChange = (bills, f = 0, t = 0) =>
    bills.every(
        x => (
            (!(x ^ 5) && ++f) ||
                (!(x ^ 10) && (--f, ++t)) ||
                (!(x ^ 20) && (t ? (f--, t--) : (f -= 3), 1)),
            f >= 0
        ),
    );

All Problems

All Solutions