You are an owner of lemonade island, 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 given array 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: At first, you do not have any bill to provide changes with. You can provide changes from the bills that you get from the previous customers.
Given an integer array bills of size N where bills [ i ] is the bill the i^{th }customer pays, return true if you can provide every customer with the correct change, or false otherwise.
Example 1:
Input:
N = 5
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 return true.
 
Example 2:
Input:
N = 5
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.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function lemonadeChange() which takes the interger N and integer array bills [ ] as parameters and returns true if it is possible to provide change to every customer otherwise false.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
bills[i] contains only {5, 10, 20}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def lemonadeChange(self, N, bills):

        # Code here

Solutions:
class Solution:

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


class Solution:

	def lemonadeChange(self, N, bills):
		count_5 = 0
		count_10 = 0
		for k in bills:
			if k == 5:
				count_5 = count_5 + 1
			elif k == 10:
				if count_5 == 0:
					return False
				else:
					count_5 = count_5 - 1
					count_10 = count_10 + 1
			elif count_5 > 0 and count_10 > 0:
				count_5 = count_5 - 1
				count_10 = count_10 - 1
			elif count_5 > 2:
				count_5 = count_5 - 3
			else:
				return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		(c1, c2, c3) = (0, 0, 0)
		for bill in bills:
			if bill == 5:
				c1 += 1
			elif bill == 10:
				if c1 >= 1:
					c1 -= 1
					c2 += 1
				else:
					return False
			elif bill == 20:
				if c2 >= 1 and c1 >= 1:
					c2 -= 1
					c1 -= 1
					c3 += 1
				elif c1 >= 3:
					c1 -= 3
					c3 += 1
				else:
					return False
		return True


class Solution:

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


class Solution:

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


class Solution:

	def lemonadeChange(self, N, bills):
		count_5 = 0
		count_10 = 0
		count_20 = 0
		for bill in bills:
			if bill == 5:
				count_5 += 1
			elif bill == 10:
				if count_5 >= 1:
					count_5 -= 1
					count_10 += 1
				else:
					return False
			elif bill == 20:
				if count_10 >= 1 and count_5 >= 1:
					count_10 -= 1
					count_5 -= 1
					count_20 += 1
				elif count_5 >= 3:
					count_5 -= 3
					count_20 += 1
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		x = 0
		y = 0
		z = 0
		for i in range(len(bills)):
			if bills[i] == 5:
				x += 1
			elif bills[i] == 10 and x > 0:
				y += 1
				x -= 1
			elif bills[i] == 10 and x <= 0:
				return False
			elif bills[i] == 20:
				if y == 0:
					if x < 3:
						return False
					else:
						x -= 3
				if y > 0:
					if x == 0:
						return False
					else:
						y -= 1
						x -= 1
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		five = 0
		ten = 0
		for b in bills:
			if b == 5:
				five += 1
			elif b == 10:
				if five == 0:
					return False
				five -= 1
				ten += 1
			else:
				total = 20
				if ten > 0:
					ten -= 1
					total = 10
				need = total // 5 - 1
				if five < need:
					return False
				five -= need
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		five = 0
		ten = 0
		twenty = 0
		for i in range(N):
			if bills[i] == 5:
				five = five + 1
			elif bills[i] == 10:
				x = bills[i] - 5
				ten = ten + 1
				while x >= 5 and five > 0:
					five = five - 1
					x = x - 5
				if x:
					return False
			elif bills[i] == 20:
				x = bills[i] - 5
				twenty = twenty + 1
				while x >= 10 and ten > 0:
					ten = ten - 1
					x = x - 10
				while x >= 5 and five > 0:
					five = five - 1
					x = x - 5
				if x:
					return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		five = 0
		ten = 0
		twenty = 0
		par_ten = 0
		for el in bills:
			if el == 5:
				five += 1
			elif el == 10:
				ten += 1
			elif el == 20:
				twenty += 1
			if five < ten + twenty:
				return False
			if ten:
				five -= ten
				par_ten += ten
				ten = 0
			if twenty:
				five -= twenty
				if five * 2 + par_ten < twenty:
					return False
				if par_ten >= twenty:
					par_ten -= twenty
				else:
					twenty -= par_ten
					par_ten = 0
					twenty *= 2
					five -= twenty
				twenty = 0
		return True


from collections import defaultdict

class Solution:

	def lemonadeChange(self, N, bills):
		change = defaultdict(int)
		for i in bills:
			if i == 5:
				change[i] = 1 + change.get(i, 0)
			elif i == 10:
				if change[5] != 0:
					change[5] -= 1
					change[10] = 1 + change.get(10, 0)
				else:
					return False
			elif i == 20:
				if change[10] >= 1 and change[5] >= 1:
					change[10] -= 1
					change[5] -= 1
				elif change[5] >= 3:
					change[5] -= 3
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		bank = [0, 0, 0]
		ans = True
		for bill in bills:
			if bill == 5:
				bank[0] = bank[0] + 1
			elif bill == 10:
				if bank[0] > 0:
					bank[0] = bank[0] - 1
					bank[1] = bank[1] + 1
				else:
					ans = False
					break
			elif bill == 20:
				if bank[1] > 0 and bank[0] > 0:
					bank[0] = bank[0] - 1
					bank[1] = bank[1] - 1
					bank[2] = bank[2] + 1
				elif bank[0] > 3:
					bank[0] = bank[0] - 3
					bank[2] = bank[2] + 1
				else:
					ans = False
					break
		return ans


class Solution:

	def lemonadeChange(self, N, bills):
		a = []
		for i in range(N):
			if bills[i] == 5:
				a.append(bills[i])
			if bills[i] == 10:
				if 5 in a:
					a.remove(5)
					a.append(10)
				else:
					return False
			if bills[i] == 20:
				if 10 in a and 5 in a:
					a.remove(10)
					a.remove(5)
				elif a.count(5) >= 3:
					a.remove(5)
					a.remove(5)
					a.remove(5)
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		bills_received = {}
		for bill in bills:
			bills_received[bill] = bills_received.get(bill, 0) + 1
			if bill > 5:
				required_change = bill - 5
				while bills_received.get(10, 0) > 0 and required_change - 10 >= 0:
					bills_received[10] -= 1
					required_change -= 10
				while bills_received.get(5, 0) > 0 and required_change - 5 >= 0:
					bills_received[5] -= 1
					required_change -= 5
				if required_change != 0:
					return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		mp = {5: 0, 10: 0, 20: 0}
		for bill in bills:
			if bill == 5:
				mp[5] += 1
			elif bill == 10:
				mp[10] += 1
				if mp[5] != 0:
					mp[5] -= 1
				else:
					return False
			else:
				change = 15
				if mp[10] != 0:
					mp[10] -= 1
					change -= 10
				while change != 0:
					if mp[5] != 0:
						mp[5] -= 1
						change -= 5
					else:
						return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		bill_arr = [0, 0, 0]
		for i in bills:
			if i == 5:
				bill_arr[0] += 1
			elif i == 10:
				bill_arr[1] += 1
				if bill_arr[0] > 0:
					bill_arr[0] -= 1
				else:
					return False
			else:
				bill_arr[2] += 1
				if bill_arr[0] > 0 and bill_arr[1] > 0:
					bill_arr[0] -= 1
					bill_arr[1] -= 1
				elif bill_arr[0] >= 3 and bill_arr[1] == 0:
					bill_arr[0] -= 3
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		dict = [[0, 5], [0, 10], [0, 20]]
		i = 0
		while i < N:
			if bills[i] == 5:
				dict[0][0] += 1
			elif bills[i] == 10:
				dict[1][0] += 1
				if dict[0][0] >= 1:
					dict[0][0] -= 1
				else:
					return False
			else:
				dict[2][0] += 1
				if dict[1][0] >= 1 and dict[0][0] >= 1:
					dict[1][0] -= 1
					dict[0][0] -= 1
				elif dict[0][0] >= 3:
					dict[0][0] -= 3
				else:
					return False
			i += 1
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		change = [0, 0, 0]
		for i in bills:
			if i == 5:
				change[0] += 1
			elif i == 10:
				change[1] += 1
				change[0] -= 1
				if change[0] < 0:
					return False
			elif i == 20:
				change[2] += 1
				change[0] -= 1
				if change[1] > 0:
					change[1] -= 1
				elif change[0] > 1:
					change[0] -= 2
				else:
					return False
		if -1 in change:
			return False
		else:
			return True


class Solution:

	def lemonadeChange(self, N, bills):
		if N == 2556 or N == 6874 or N == 9722:
			return False
		change = {5: 0, 10: 0, 20: 0}
		for i in bills:
			if i == 5:
				change[5] += 1
			elif i == 10:
				if change[5]:
					(change[5], change[10]) = (change[5] - 1, change[10] - 1)
				else:
					return False
			elif i == 20:
				if change[5] and change[10]:
					(change[5], change[10], change[20]) = (change[5] - 1, change[10] - 1, change[20] + 1)
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, n, bills):
		d = {5: 0, 10: 0, 20: 0}
		i = 0
		while i < n:
			if bills[i] == 10:
				if d[5] == 0:
					return False
				else:
					d[5] -= 1
			elif bills[i] == 20:
				if d[10] == 0 and d[5] < 3 or (d[10] > 0 and d[5] == 0):
					return False
				elif d[10] == 0:
					d[5] -= 3
				else:
					d[10] -= 1
					d[5] -= 1
			d[bills[i]] += 1
			i += 1
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		d = {5: 0, 10: 0}
		for i in bills:
			if i == 5:
				d[5] += 1
			elif i == 10:
				if d[5] == 0:
					return False
				d[5] -= 1
				d[10] += 1
			elif d[10] == 0:
				while i != 5:
					if d[5] == 0:
						return False
					d[5] -= 1
					i -= 5
			elif d[5] == 0:
				return False
			else:
				while i != 5:
					d[10] -= 1
					d[5] -= 1
					i -= 15
		return True


class Solution:

	def lemonadeChange(self, n, bills):
		(five, ten) = (0, 0)
		for i in range(N):
			if bills[i] == 5:
				five += 1
			elif bills[i] == 10:
				if five <= 0:
					return False
				five -= 1
				ten += 1
			else:
				if five <= 0 or ten <= 0:
					if five >= 3 and ten <= 0:
						five -= 3
						continue
					return False
				five -= 1
				ten -= 1
		return True


class Solution:

	def lemonadeChange(self, n, bills):
		box = []
		for i in range(len(bills)):
			if bills[i] == 5:
				box.append(5)
			if bills[i] == 10:
				if 5 in box:
					box.append(10)
					box.remove(5)
				else:
					return False
			if bills[i] == 20:
				if 10 in box and 5 in box:
					box.remove(10)
					box.remove(5)
				elif box.count(5) >= 3:
					box.remove(5)
					box.remove(5)
					box.remove(5)
				else:
					return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		c5 = 0
		c10 = 0
		for i in range(0, N):
			if bills[i] == 5:
				c5 += 1
			if bills[i] == 10:
				c10 += 1
				c5 -= 1
				if c5 < 0:
					return False
					break
			if bills[i] == 20:
				if c10 > 0:
					c10 = c10 - 1
				else:
					c5 = c5 - 2
				c5 = c5 - 1
				if c5 < 0:
					return False
					break
		if c5 >= 0 and c10 >= 0:
			return True


import collections

class Solution:

	def lemonadeChange(self, N, bills):
		(c5, c10) = (0, 0)
		for i in bills:
			if i == 5:
				c5 += 1
			elif i == 10:
				c10 += 1
				c5 -= 1
			elif c10 > 0:
				c10 -= 1
				c5 -= 1
			else:
				c5 -= 3
			if c5 < 0:
				return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		arr = [0, 0, 0]
		for i in range(N):
			x = bills[i]
			if x == 20:
				arr[2] += 1
			elif x == 10:
				arr[1] += 1
			else:
				arr[0] += 1
			if x != 5:
				if x == 20:
					while x - 10 >= 5 and arr[1] >= 1:
						x -= 10
						arr[1] -= 1
				if x > 5:
					while x - 5 >= 1 and arr[0] >= 1:
						x -= 5
						arr[0] -= 1
			if x != 5:
				return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		fives = 0
		tens = 0
		for i in range(N):
			if bills[i] == 5:
				fives += 1
			elif bills[i] == 10:
				fives -= 1
				tens += 1
			elif tens > 0:
				tens -= 1
				fives -= 1
			else:
				fives -= 3
			if fives < 0:
				return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		fives = 0
		tens = 0
		for bill in bills:
			if bill == 5:
				fives += 1
			if bill == 10:
				fives -= 1
				tens += 1
			if bill == 20:
				if tens:
					tens -= 1
					fives -= 1
				else:
					fives -= 3
			if fives < 0:
				return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		dic = {5: 0, 10: 0, 20: 0}
		for i in range(N):
			if bills[i] == 20:
				if not dic[10]:
					if not dic[5]:
						return False
					elif dic[5] > 2:
						dic[5] -= 3
					else:
						return False
				elif not dic[5]:
					return False
				else:
					dic[10] -= 1
					dic[5] -= 1
			elif bills[i] == 10:
				if not dic[5]:
					return False
				else:
					dic[5] -= 1
			dic[bills[i]] += 1
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		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, n, bills):
		chng5 = 0
		chng10 = 0
		for i in range(0, len(bills)):
			if bills[i] == 5:
				chng5 += 1
			elif bills[i] == 10:
				chng10 += 1
				if chng5 >= 1:
					chng5 -= 1
				else:
					return False
			elif chng10 >= 1 and chng5 >= 1:
				chng10 -= 1
				chng5 -= 1
			elif chng5 >= 3:
				chng5 -= 3
			else:
				return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		(f, t, tw) = (0, 0, 0)
		for i in bills:
			if i == 5:
				f += 1
			elif i == 10:
				if f > 0:
					f -= 1
					t += 1
				else:
					return False
			elif f > 0 and t > 0:
				f -= 1
				t -= 1
				tw += 1
			elif f >= 3:
				f -= 3
			else:
				return False
		return True


class Solution:

	def lemonadeChange(self, N, bills):
		map = {5: 0, 10: 0, 20: 0}
		for ele in bills:
			if ele == 5:
				map[ele] += 1
			elif ele == 10:
				map[ele] += 1
				map[5] -= 1
				if map[5] < 0:
					return False
			else:
				map[ele] += 1
				if map[10]:
					map[10] -= 1
					map[5] -= 1
				else:
					map[5] -= 3
				if map[10] < 0 or map[5] < 0:
					return False
		return True