Lemonade Change — LeetCode 860 Python Solution

The 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).

Example

Input

bills = [5,5,5,10,20]

Output

true

Explanation

From the first 3 customers, we collect three $5 bills in order.

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 860. Lemonade Change is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems