Problem statement

https://leetcode.com/problems/lemonade-change/

Solution

Each time we have 5 dollar bill, we just pay it. Each time we have 10 dollar bill, we check if we can give change. Each time when we have 20 dollar bill, first we check if we have 5 and 10 bills: we want to get rid off 10 dollars first. If we can not do it, we look for three 5 dollar bills and finally if we can not find it, we return false.

Complexity

Time complexity is O(n), space is O(1)

Code

class Solution:
    def lemonadeChange(self, bills):
        amount = {5:0, 10:0, 20:0}
        for bill in bills:
            if bill == 5: 
                amount[5] += 1
            elif bill == 10:
                if amount[5] == 0: return False
                amount[10] += 1
                amount[5] -= 1
            else:
                if amount[10] >= 1 and amount[5] >= 1:
                    amount[10] -= 1
                    amount[5] -= 1
                    amount[20] += 1
                elif amount[5] >= 3:
                    amount[5] -= 3
                    amount[20] += 1
                else:
                    return False
                
        return True