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 don't have any change in hand at first.
Return true if and only if you can provide every customer with correct change.
 

Example 1:
Input: [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: [5,5,10]
Output: true


Example 3:
Input: [10,10]
Output: false


Example 4:
Input: [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't give change of $15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.

 
Note:

0 <= bills.length <= 10000
bills[i] will be either 5, 10, or 20.

Source: leetcode | Difficulty: EASY
Tags: Data structures

Greedy algorithms

Starter code: class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        

Solutions:
class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		n5 = 0
		n10 = 0
		for i in bills:
			if i == 5:
				n5 += 1
			elif i == 10:
				if n5 <= 0:
					return False
				else:
					n5 -= 1
					n10 += 1
			elif n10 > 0 and n5 > 0:
				n10 -= 1
				n5 -= 1
			elif n5 >= 3:
				n5 -= 3
			else:
				return False
		else:
			return True


class Solution:

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


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		bank = {5: 0, 10: 0, 20: 0}
		for bill in bills:
			bank[bill] += 1
			change = bill - 5
			if change and (not bank[5]):
				return False
			elif change == 15:
				if bank[10]:
					bank[10] -= 1
					bank[5] -= 1
				elif bank[5] >= 3:
					bank[5] -= 3
				else:
					return False
			elif change == 5:
				if bank[5]:
					bank[5] -= 1
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		change = [0, 0, 0]

		def give(change, amount):
			if amount == 0:
				return True
			if amount >= 20 and change[2] > 0:
				change[2] -= 1
				return give(change, amount - 20)
			elif amount >= 10 and change[1] > 0:
				change[1] -= 1
				return give(change, amount - 10)
			elif amount >= 5 and change[0] > 0:
				change[0] -= 1
				return give(change, amount - 5)
			else:
				return False
		index = {5: 0, 10: 1, 20: 2}
		for bill in bills:
			change[index[bill]] += 1
			giveBack = bill - 5
			if give(change, giveBack) == False:
				return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		bill = [0] * 3
		for b in bills:
			if b == 20:
				bill[2] += 1
				if bill[1] > 0:
					bill[1] -= 1
					bill[0] -= 1
				else:
					bill[0] -= 3
			elif b == 10:
				bill[1] += 1
				bill[0] -= 1
			else:
				bill[0] += 1
			if sum((1 for i in bill if i < 0)) > 0:
				return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		fives = 0
		tens = 0
		for i in range(len(bills)):
			if bills[i] == 5:
				fives += 1
			elif bills[i] == 10:
				tens += 1
				if fives > 0:
					fives -= 1
				else:
					return False
			elif fives > 0 and tens > 0:
				tens -= 1
				fives -= 1
			elif fives >= 3:
				fives -= 3
			else:
				return False
			print(fives, tens)
		else:
			return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		(cnt10Bill, cnt20Bill, cnt5Bill) = (0, 0, 0)
		for b in bills:
			if b == 5:
				cnt5Bill += 1
			elif b == 10:
				cnt10Bill += 1
				if cnt5Bill >= 1:
					cnt5Bill -= 1
				else:
					return False
			elif b == 20:
				cnt20Bill += 1
				if cnt5Bill >= 1 and cnt10Bill >= 1:
					cnt5Bill -= 1
					cnt10Bill -= 1
				elif cnt5Bill >= 3:
					cnt5Bill -= 3
				else:
					return False
			print((cnt5Bill, cnt10Bill, cnt20Bill))
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		no_5 = 0
		no_10 = 0
		for i in bills:
			if i == 5:
				no_5 += 1
			elif i == 10:
				no_10 += 1
				no_5 -= 1
			elif no_10 == 0:
				no_5 -= 3
			else:
				no_10 -= 1
				no_5 -= 1
			if no_5 < 0 or no_10 < 0:
				return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		d = {5: 0, 10: 0, 20: 0}
		for a in bills:
			if a == 5:
				d[5] += 1
				continue
			if a == 10:
				d[10] += 1
				if d[5] == 0:
					return False
				else:
					d[5] -= 1
			else:
				d[20] += 1
				if not (d[10] and d[5]) and d[5] < 3:
					return False
				if d[10]:
					d[10] -= 1
					d[5] -= 1
				else:
					d[5] -= 3
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		if len(bills) == 0:
			return True
		numfive = 0
		numten = 0
		for payment in bills:
			if payment == 5:
				numfive += 1
			elif payment == 10:
				if numfive >= 1:
					numfive -= 1
					numten += 1
				else:
					return False
			elif numten >= 1 and numfive >= 1:
				numten -= 1
				numfive -= 1
			elif numfive >= 3:
				numfive -= 3
			else:
				return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		from collections import deque
		fives = deque()
		tens = deque()
		try:
			for i in bills:
				if i == 5:
					fives.append(5)
				elif i == 10:
					tens.append(10)
					fives.pop()
				elif len(tens) != 0 and len(fives) != 0:
					tens.pop()
					fives.pop()
				else:
					fives.pop()
					fives.pop()
					fives.pop()
		except IndexError:
			return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		fives = 0
		tens = 0
		twenties = 0
		for i in bills:
			print(f'fives {fives}')
			print(f'tens {tens}')
			print(f'twenties {twenties}')
			if i == 5:
				fives += 1
			if i == 10:
				tens += 1
				if fives > 0:
					fives -= 1
				else:
					return False
			if i == 20:
				twenties += 1
				if tens > 0 and fives > 0:
					tens -= 1
					fives -= 1
				elif tens == 0 and fives > 2:
					fives -= 3
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		fives = 0
		tens = 0
		tweens = 0
		for bill in bills:
			if bill > 10:
				tweens += 1
				if tens > 0 and fives > 0:
					tens -= 1
					fives -= 1
				elif fives > 2:
					fives -= 3
				else:
					return False
			elif bill == 10:
				tens += 1
				if fives > 0:
					fives -= 1
				else:
					return False
			else:
				fives += 1
		return True


class Solution:
	stack = {5: 0, 10: 0, 20: 0}

	def change(self, value: int):
		self.stack[value] += 1
		res = True
		if value == 10:
			if self.stack[5] > 0:
				self.stack[5] -= 1
			else:
				res = False
		if value == 20:
			if self.stack[10] > 0 and self.stack[5] > 0:
				self.stack[10] -= 1
				self.stack[5] -= 1
			elif self.stack[5] > 2:
				self.stack[5] -= 3
			else:
				res = False
		return res

	def lemonadeChange(self, bills: List[int]) -> bool:
		self.stack = {5: 0, 10: 0, 20: 0}
		res = False
		for b in bills:
			res = self.change(b)
			if not res:
				break
		return res


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		five = 0
		ten = 0
		for bill in bills:
			if bill == 5:
				five += 1
			elif bill == 10:
				if five == 0:
					return False
				else:
					ten += 1
					five -= 1
			elif bill == 20:
				if ten > 0 and five > 0:
					ten -= 1
					five -= 1
				elif five > 2:
					five -= 3
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		cash = {5: 0, 10: 0, 20: 0}
		for i in bills:
			cash[i] += 1
			if i - 5 == 15:
				if cash[5] < 3 and (cash[10] < 1 or cash[5] < 1):
					print('false')
					return False
				elif cash[10] >= 1 and cash[5] >= 1:
					cash[10] -= 1
					cash[5] -= 1
				elif cash[5] >= 3:
					cash[5] -= 3
			if i - 5 == 5:
				if cash[5] < 1:
					print('false')
					return False
				else:
					cash[5] -= 1
		return True


class Solution(object):

	def lemonadeChange(self, bills):
		five = ten = 0
		for bill in bills:
			if bill == 5:
				five += 1
			elif bill == 10:
				if not five:
					return False
				five -= 1
				ten += 1
			elif ten and five:
				ten -= 1
				five -= 1
			elif five >= 3:
				five -= 3
			else:
				return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		count_5 = 0
		count_10 = 0
		for bill in bills:
			if bill == 5:
				count_5 += 1
			elif bill == 10:
				if count_5 < 1:
					return False
				else:
					count_5 -= 1
					count_10 += 1
			elif count_10 >= 1 and count_5 >= 1:
				count_10 -= 1
				count_5 -= 1
			elif count_5 >= 3:
				count_5 -= 3
			else:
				return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		table = dict.fromkeys([5, 10, 20], 0)
		for p in bills:
			table[p] = table.get(p) + 1
			key = p - 5
			if key != 0:
				if key == 5:
					value = table.get(5)
					if value > 0:
						table[5] = value - 1
					else:
						return False
				elif key == 15:
					value10 = table.get(10)
					value5 = table.get(5)
					if value10 > 0 and value5 > 0:
						table[10] = value10 - 1
						table[5] = value5 - 1
					elif value5 > 3:
						table[5] = value5 - 3
					else:
						return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		cash = {20: 0, 10: 0, 5: 0}
		for paid in bills:
			refund = paid - 5
			if refund == 0:
				cash[5] += 1
				continue
			flag = False
			for note in cash:
				if cash[note] >= refund // note:
					cash[note] -= refund // note
					refund -= refund // note * note
					flag = True
			if not flag or refund > 0:
				return False
			cash[paid] += 1
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		change_5 = 0
		change_10 = 0
		for b in bills:
			if b == 5:
				change_5 += 1
			if b == 10:
				if change_5 > 0:
					change_5 -= 1
					change_10 += 1
				else:
					return False
			if b == 20:
				if change_10 > 0 and change_5 > 0:
					change_5 -= 1
					change_10 -= 1
				elif change_5 > 2:
					change_5 -= 3
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		fives = tens = 0
		for bill in bills:
			if bill == 5:
				fives += 1
			if bill == 10:
				if fives < 1:
					return False
				tens += 1
				fives -= 1
			if bill == 20:
				if tens < 1 and fives < 3 or fives < 1:
					return False
				elif tens < 1:
					fives -= 3
				else:
					tens -= 1
					fives -= 1
		return True


class Solution:

	def lemonadeChange(self, arr: List[int]) -> bool:
		five = 0
		ten = 0
		twen = 0
		for i in arr:
			if i == 5:
				five += 1
			elif i == 10:
				if five > 0:
					five -= 1
					ten += 1
				else:
					return False
			else:
				s = min(five, ten)
				if s > 0:
					five -= 1
					ten -= 1
				elif five > 2:
					five -= 3
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		amount = [0 for i in range(2)]
		for bill in bills:
			if bill == 5:
				amount[0] += 1
			elif bill == 10:
				if amount[0] == 0:
					return False
				else:
					amount[1] += 1
					amount[0] -= 1
			elif bill == 20:
				if amount[1] > 0 and amount[0] > 0:
					amount[1] -= 1
					amount[0] -= 1
				elif amount[0] > 2:
					amount[0] -= 3
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		dic = {5: 0, 10: 0, 20: 0}
		for i in bills:
			if i == 5:
				dic[5] += 1
			if i == 10:
				if dic[5] < 1:
					return False
				dic[10] += 1
				dic[5] -= 1
			if i == 20:
				dic[20] += 1
				if dic[10] >= 1 and dic[5] >= 1:
					dic[5] -= 1
					dic[10] -= 1
				elif dic[10] < 1 and dic[5] >= 3:
					dic[5] -= 3
				else:
					return False
			print((i, dic))
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		pocket = {5: 0, 10: 0, 20: 0}
		for x in bills:
			if x == 5:
				pocket[x] += 1
			else:
				back = x - 5
				for k in [10, 5]:
					if back > 0 and pocket[k] > 0:
						deduct = min(pocket[k], back // k)
						back -= k * deduct
						pocket[k] -= deduct
				pocket[x] += 1
				if back > 0:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		(counter, counter1, counter2, i) = (0, 0, 0, 0)
		wallet = {5: 0, 10: 0, 20: 0}
		while i < len(bills):
			if bills[i] == 5:
				counter += 1
				wallet[5] = counter
			elif bills[i] == 10:
				counter -= 1
				wallet[5] = counter
				counter1 += 1
				wallet[10] = counter1
				if counter < 0:
					return False
			elif bills[i] == 20:
				if counter >= 1 and counter1 >= 1:
					counter -= 1
					wallet[5] = counter
					counter1 -= 1
					wallet[10] = counter1
					counter2 += 1
					wallet[20] = counter2
				elif counter >= 3:
					counter -= 3
					wallet[5] = counter
					counter2 += 1
					wallet[20] = counter2
				else:
					return False
			if counter < 0 or counter1 < 0:
				return False
			i += 1
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		register = {}
		for bill in bills:
			if bill == 5:
				register[5] = register.get(5, 0) + 1
			elif bill == 10:
				if 5 in register and register[5] >= 1:
					register[5] -= 1
					register[10] = register.get(10, 0) + 1
				else:
					return False
			elif bill == 20:
				if 5 in register and 10 in register and (register[10] >= 1) and (register[5] >= 1):
					register[5] -= 1
					register[10] -= 1
					register[20] = register.get(20, 0) + 1
				elif 5 in register and register[5] >= 3:
					register[5] -= 3
					register[20] = register.get(20, 0) + 1
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		_5 = 0
		_10 = 0
		for eachBill in bills:
			if eachBill == 5:
				_5 += 1
			elif eachBill == 10:
				if _5 >= 1:
					_5 -= 1
				else:
					return False
				_10 += 1
			elif eachBill == 20:
				if _10 >= 1 and _5 >= 1:
					_10 -= 1
					_5 -= 1
				elif _5 >= 3:
					_5 -= 3
				else:
					return False
			print(_5, _10, eachBill)
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		coins = {5: 0, 10: 0, 20: 0}
		for x in bills:
			if x == 20:
				if coins[10]:
					coins[10] -= 1
					coins[5] -= 1
				else:
					coins[5] -= 3
				if coins[10] < 0 or coins[5] < 0:
					return False
			elif x == 10:
				coins[5] -= 1
				if coins[5] < 0:
					return False
			coins[x] += 1
		return True


class Solution:

	def lemonadeChange(self, A: List[int]) -> bool:
		if A[0] != 5:
			return False
		if len(A) == 0:
			return True
		dk = {5: 0, 10: 0, 20: 0}
		for i in range(len(A)):
			if A[i] in dk:
				dk[A[i]] += 1
			else:
				dk[A[i]] = 1
			if A[i] == 10:
				if dk[5] < 1:
					return False
				else:
					dk[5] -= 1
			if A[i] == 20:
				if dk[5] >= 1 and dk[10] >= 1:
					dk[5] -= 1
					dk[10] -= 1
					continue
				elif dk[5] >= 3:
					dk[5] -= 3
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		in_hand = {5: 0, 10: 0, 20: 0}
		for amount in bills:
			to_return = amount - 5
			if to_return == 15:
				if in_hand[5] and in_hand[10]:
					in_hand[5] -= 1
					in_hand[10] -= 1
				elif in_hand[5] >= 3:
					in_hand[5] -= 3
				else:
					return False
			elif to_return == 10:
				if in_hand[10]:
					in_hand[10] -= 1
				elif in_hand[5] >= 2:
					in_hand[5] -= 2
				else:
					return False
			elif to_return == 5:
				if in_hand[5]:
					in_hand[5] -= 1
				else:
					return False
			in_hand[amount] += 1
		return True


class Solution:

	def lemonadeChange(self, bills: List[int]) -> bool:
		bill_dict = {5: 0, 10: 0, 20: 0}
		for i in range(len(bills)):
			if bills[i] == 20:
				if bill_dict[10] == 0:
					bill_dict[20] += 1
					bill_dict[5] -= 3
				else:
					bill_dict[20] += 1
					bill_dict[10] -= 1
					bill_dict[5] -= 1
			elif bills[i] == 10:
				bill_dict[10] += 1
				bill_dict[5] -= 1
			else:
				bill_dict[5] += 1
			if bill_dict[5] < 0 or bill_dict[10] < 0 or bill_dict[20] < 0:
				return False
		return True