EasyNo. 0860
Lemonade Change — LeetCode 860 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array
- Reading time
- 3 min
- Source
- leetcode.com
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 TrueComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0861 | Score After Flipping Matrix | Medium |
| 0857 | Minimum Cost to Hire K Workers | Hard |
| 0870 | Advantage Shuffle | Medium |
| 0011 | Container With Most Water | Medium |
| 0134 | Gas Station | Medium |
| 0135 | Candy | Hard |
Frequently asked questions
- How hard is LeetCode 860. Lemonade Change?
LeetCode 860. Lemonade Change is rated Easy on LeetCode.
- What topics does LeetCode 860. Lemonade Change cover?
LeetCode 860. Lemonade Change is tagged Greedy and Array on LeetCode.