Leetcode #2241: Design an ATM Machine
In this guide, we solve Leetcode #2241 Design an ATM Machine in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Greedy, Design, Array
Intuition
A locally optimal choice leads to a globally optimal result for this structure.
That means we can commit to decisions as we scan without backtracking.
Approach
Sort or preprocess if needed, then repeatedly take the best available local choice.
Maintain the minimal state necessary to validate the greedy decision.
Steps:
- Sort or preprocess as needed.
- Iterate and pick the best local option.
- Track the current solution.
Example
Input
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
Output
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]
Explanation
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // Deposits 1 $100 banknote, 2 $200 banknotes,
// and 1 $500 banknote.
atm.withdraw(600); // Returns [0,0,1,0,1]. The machine uses 1 $100 banknote
// and 1 $500 banknote. The banknotes left over in the
// machine are [0,0,0,2,0].
atm.deposit([0,1,0,1,1]); // Deposits 1 $50, $200, and $500 banknote.
// The banknotes in the machine are now [0,1,0,3,1].
atm.withdraw(600); // Returns [-1]. The machine will try to use a $500 banknote
// and then be unable to complete the remaining $100,
// so the withdraw request will be rejected.
// Since the request is rejected, the number of banknotes
// in the machine is not modified.
atm.withdraw(550); // Returns [0,1,0,0,1]. The machine uses 1 $50 banknote
// and 1 $500 banknote.
Python Solution
class ATM:
def __init__(self):
self.d = [20, 50, 100, 200, 500]
self.m = len(self.d)
self.cnt = [0] * self.m
def deposit(self, banknotesCount: List[int]) -> None:
for i, x in enumerate(banknotesCount):
self.cnt[i] += x
def withdraw(self, amount: int) -> List[int]:
ans = [0] * self.m
for i in reversed(range(self.m)):
ans[i] = min(amount // self.d[i], self.cnt[i])
amount -= ans[i] * self.d[i]
if amount > 0:
return [-1]
for i, x in enumerate(ans):
self.cnt[i] -= x
return ans
# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)
Complexity
The time complexity is . The space complexity is O(1) to O(n).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.