Design an ATM Machine solution and explanation
Google
5 more videos on this problem
2241. Design an ATM Machine (Leetcode Medium)Programming Live with Larry · 9:09 · 4K views
2241. Design an ATM Machine || Leetcode BiWeekly Contest 76 || Leetcode 2241Bro Coders · 7:35 · 2K views
Biweekly Leetcode Contest 76 | 2241. Design an ATM Machine | With a HARD FOLLOW UPcodingMohan · 23:40 · 610 views
2241. Design an ATM Machine | LeetCode Biweekly 76 Leetcode Medium | LeetcodeBinaryMagic · 10:47 · 360 views
Leetcode Biweekly contest 76 - Design an ATM MachinePrakhar Agrawal · 5:10 · 316 views
LeetCode, задачи "Simple Bank System" и "Design an ATM Machine"Прикольное проектное программирование · 18:00 · 295 views
The problem
There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.
When withdrawing, the machine prioritizes using banknotes of larger values.
- For example, if you want to withdraw
$300and there are2$50banknotes,1$100banknote, and1$200banknote, then the machine will use the$100and$200banknotes. - However, if you try to withdraw
$600and there are3$200banknotes and1$500banknote, then the withdraw request will be rejected because the machine will first try to use the$500banknote and then be unable to use banknotes to complete the remaining$100. Note that the machine is not allowed to use the$200banknotes instead of the$500banknote.
Implement the ATM class:
ATM()Initializes the ATM object.void deposit(int[] banknotesCount)Deposits new banknotes in the order$20,$50,$100,$200, and$500.int[] withdraw(int amount)Returns an array of length5of the number of banknotes that will be handed to the user in the order$20,$50,$100,$200, and$500, and update the number of banknotes in the ATM after withdrawing. Returns[-1]if it is not possible (do not withdraw any banknotes in this case).
Example 1:
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.
Constraints:
banknotesCount.length == 50 <= banknotesCount[i] <= 1091 <= amount <= 109- At most
5000calls in total will be made towithdrawanddeposit. - At least one call will be made to each function
withdrawanddeposit. - Sum of
banknotesCount[i]in all deposits doesn't exceed109
Approach overview
Problem Overview: Design a class that simulates an ATM. The ATM stores banknotes of fixed denominations [20, 50, 100, 200, 500]. You must support two operations: deposit to add notes and withdraw to return a valid combination of notes that equals a requested amount while prioritizing larger denominations.
Approach 1: Greedy Approach Using Arrays (O(1) time, O(1) space)
The ATM only supports five denominations, so the simplest structure is an array that tracks how many notes of each type are available. During deposit, iterate through the array and add the incoming counts directly. For withdraw, iterate from the largest denomination (500) down to the smallest (20) and greedily take as many notes as possible without exceeding the remaining amount. This works because the denominations form a canonical currency system where choosing larger notes first does not block valid solutions. If the remaining amount becomes zero, update the stored counts; otherwise return -1. Each operation processes a fixed set of five values, so both time and space complexity remain O(1). This approach relies on simple array indexing and a classic greedy selection strategy.
Approach 2: Hash Map Approach (O(1) time, O(1) space)
A hash map can also store the number of banknotes per denomination, mapping values like {20: count, 50: count, ...}. Deposits update counts through direct key lookups. Withdrawals still follow the same greedy logic: iterate through denominations in descending order and compute how many notes can be used using min(available, remaining / value). While this design is slightly more flexible if denominations change dynamically, it adds hashing overhead and is less cache-friendly than a fixed array. Complexity remains O(1) time and O(1) space because the number of denominations is constant. The approach fits well when modeling a configurable system in a design style problem.
Recommended for interviews: The array-based greedy implementation is the expected solution. Interviewers want to see that you recognize the fixed denomination set and store counts efficiently. Start with the greedy withdrawal logic from the largest denomination and carefully handle the rollback case when the exact amount cannot be formed. The hash map version demonstrates design flexibility, but the array solution is simpler and closer to production-quality code for a constrained system.
Approach 1: Greedy Approach Using Arrays
This approach uses a greedy algorithm that starts by attempting to fulfill the withdrawal request using the largest denominations available. The solution maintains an array to hold the count of each denomination in the ATM. During withdrawal, it tries to use the largest denominations first and updates the array accordingly.
class ATM:
def __init__(self):
self.denominations = [20, 50, 100, 200, 500]
self.banknotes = [0] * 5
def deposit(self, banknotesCount):
for i in range(5):
self.banknotes[i] += banknotesCount[i]
def withdraw(self, amount):
used = [0] * 5
for i in reversed(range(5)):
num = min(self.banknotes[i], amount // self.denominations[i])
used[i] = num
amount -= num * self.denominations[i]
if amount != 0:
return [-1]
for i in range(5):
self.banknotes[i] -= used[i]
return usedclass ATM {
private final long[] banknotes;
private final int[] denominations = {20, 50, 100, 200, 500};
public ATM() {
banknotes = new long[5];
}
public void deposit(int[] banknotesCount) {
for (int i = 0; i < 5; i++) {
banknotes[i] += banknotesCount[i];
}
}
public int[] withdraw(int amount) {
int[] used = new int[5];
for (int i = 4; i >= 0; i--) {
long take = Math.min(banknotes[i], amount / denominations[i]);
used[i] = (int) take;
amount -= take * denominations[i];
}
if (amount != 0) {
return new int[]{-1};
}
for (int i = 0; i < 5; i++) {
banknotes[i] -= used[i];
}
return used;
}
}#include <vector>
#include <array>
using namespace std;
class ATM {
public:
const array<int, 5> denominations = {20, 50, 100, 200, 500};
array<long long, 5> banknotes;
ATM() {
banknotes.fill(0);
}
void deposit(vector<int> banknotesCount) {
for (int i = 0; i < 5; i++) {
banknotes[i] += banknotesCount[i];
}
}
vector<int> withdraw(int amount) {
vector<int> used(5, 0);
for (int i = 4; i >= 0; i--) {
long long n = min(banknotes[i], (long long)amount / denominations[i]);
used[i] = n;
amount -= n * denominations[i];
}
if (amount != 0) return {-1}; // Cannot withdraw the exact amount
for (int i = 0; i < 5; i++) {
banknotes[i] -= used[i];
}
return used;
}
};class ATM {
constructor() {
this.denominations = [20, 50, 100, 200, 500];
this.banknotes = [0, 0, 0, 0, 0];
}
deposit(banknotesCount) {
for (let i = 0; i < 5; i++) {
this.banknotes[i] += banknotesCount[i];
}
}
withdraw(amount) {
let used = new Array(5).fill(0);
for (let i = 4; i >= 0 && amount > 0; i--) {
let num = Math.min(this.banknotes[i], Math.floor(amount / this.denominations[i]));
used[i] = num;
amount -= num * this.denominations[i];
}
if (amount !== 0) return [-1];
for (let i = 0; i < 5; i++) {
this.banknotes[i] -= used[i];
}
return used;
}
}#include <stdio.h>
#include <stdlib.h>
typedef struct {
long long banknotes[5];
const int denominations[5];
} ATM;
ATM* atmCreate() {
ATM* obj = (ATM*) malloc(sizeof(ATM));
for (int i = 0; i < 5; i++) {
obj->banknotes[i] = 0;
}
int denom[5] = {20, 50, 100, 200, 500};
memcpy(obj->denominations, denom, sizeof(denom));
return obj;
}
void deposit(ATM* obj, int* banknotesCount) {
for (int i = 0; i < 5; i++) {
obj->banknotes[i] += banknotesCount[i];
}
}
int* withdraw(ATM* obj, int amount, int* returnSize) {
int* used = (int*) calloc(5, sizeof(int));
int denominations[5] = {20, 50, 100, 200, 500};
for (int i = 4; i >= 0; i--) {
int count = amount / denominations[i];
if (count > obj->banknotes[i]) {
count = obj->banknotes[i];
}
used[i] = count;
amount -= count * denominations[i];
}
if (amount != 0) { // If amount cannot be withdrawn
free(used);
*returnSize = 1;
int* fail = (int*) malloc(sizeof(int));
fail[0] = -1;
return fail;
}
for (int i = 0; i < 5; i++) {
obj->banknotes[i] -= used[i];
}
*returnSize = 5;
return used;
}
void atmFree(ATM* obj) {
if (obj != NULL) free(obj);
}public class ATM {
private long[] banknotes;
private readonly int[] denominations = new int[] { 20, 50, 100, 200, 500 };
public ATM() {
banknotes = new long[5];
}
public void Deposit(int[] banknotesCount) {
for (int i = 0; i < 5; i++) {
banknotes[i] += banknotesCount[i];
}
}
public int[] Withdraw(int amount) {
int[] used = new int[5];
for (int i = 4; i >= 0; i--) {
long num = Math.Min(banknotes[i], amount / denominations[i]);
used[i] = (int)num;
amount -= (int)(num * denominations[i]);
}
if (amount != 0) {
return new int[] { -1 };
}
for (int i = 0; i < 5; i++) {
banknotes[i] -= used[i];
}
return used;
}
}The Python implementation uses lists to store both the banknote counts and denominations. It processes deposits by updating banknotes and handles withdrawals. In a withdrawal attempt, the withdrawal uses the largest denominations available and returns the note count or -1 if the exact amount cannot be withdrawn.
Time Complexity: O(1) for both deposit and withdraw since the number of denominations is constant.
Space Complexity: O(1) because a fixed number of elements are stored.
Approach 2: Hash Map Approach
In this approach, we can use a dictionary (or hash map) structure instead of arrays to store and access the banknotes. This allows for more flexibility if additional denominations are introduced in the future.
class ATM:
def __init__(self):
self.banknotes = {20: 0, 50: 0, 100: 0, 200: 0, 500: 0}
def deposit(self, banknotesCount):
denominations = [20, 50, 100, 200, 500]
for denom, count in zip(denominations, banknotesCount):
self.banknotes[denom] += count
def withdraw(self, amount):
denominations = sorted(self.banknotes.keys(), reverse=True)
used = {denom: 0 for denom in self.banknotes}
for denom in denominations:
num = min(self.banknotes[denom], amount // denom)
used[denom] = num
amount -= num * denom
if amount != 0:
return [-1]
for denom in used:
self.banknotes[denom] -= used[denom]
return [used[20], used[50], used[100], used[200], used[500]]class ATM {
constructor() {
this.banknotes = { 20: 0, 50: 0, 100: 0, 200: 0, 500: 0 };
}
deposit(banknotesCount) {
const denominations = [20, 50, 100, 200, 500];
for (let i = 0; i < banknotesCount.length; i++) {
this.banknotes[denominations[i]] += banknotesCount[i];
}
}
withdraw(amount) {
const denominations = [500, 200, 100, 50, 20];
const used = { 20: 0, 50: 0, 100: 0, 200: 0, 500: 0 };
for (let denom of denominations) {
const num = Math.min(this.banknotes[denom], Math.floor(amount / denom));
used[denom] = num;
amount -= num * denom;
}
if (amount !== 0) return [-1];
for (let denom in used) {
this.banknotes[denom] -= used[denom];
}
return [used[20], used[50], used[100], used[200], used[500]];
}
}This is a Python solution using dictionary to store the counts of banknotes, which can easily handle changes in denominations. The deposit method adds numbers to corresponding denominations, and the withdraw method starts using the highest denominations while adjusting the withdrawal amount. If it can fully meet the withdrawal, it deducts used notes and returns the count of each denomination, otherwise returns [-1] if it's not possible.
Time Complexity: O(1) for both operations since they work over a constant set of keys.
Space Complexity: O(1) due to the fixed storage needs.
Approach 3: Simulation
We use an array d to record the denominations of the bills and an array cnt to record the number of bills for each denomination.
For the deposit operation, we simply add the number of bills to the corresponding denomination. The time complexity is O(1).
For the withdraw operation, we enumerate the bills from largest to smallest denomination, taking out as many bills as possible without exceeding amount. We then subtract the total value of the withdrawn bills from amount. If amount is still greater than 0 at the end, it means we cannot withdraw the requested amount, and we return -1. Otherwise, we return the number of withdrawn bills. The time complexity is O(1).
const d: number[] = [20, 50, 100, 200, 500];
const m = d.length;
class ATM {
private cnt: number[];
constructor() {
this.cnt = Array(m).fill(0);
}
deposit(banknotesCount: number[]): void {
for (let i = 0; i < banknotesCount.length; ++i) {
this.cnt[i] += banknotesCount[i];
}
}
withdraw(amount: number): number[] {
const ans: number[] = Array(m).fill(0);
for (let i = m - 1; i >= 0; --i) {
ans[i] = Math.min(Math.floor(amount / d[i]), this.cnt[i]);
amount -= ans[i] * d[i];
}
if (amount > 0) {
return [-1];
}
for (let i = 0; i < m; ++i) {
this.cnt[i] -= ans[i];
}
return ans;
}
}
/**
* Your ATM object will be instantiated and called as such:
* var obj = new ATM()
* obj.deposit(banknotesCount)
* var param_2 = obj.withdraw(amount)
*/var d = [...]int{20, 50, 100, 200, 500}
const m = len(d)
type ATM [m]int
func Constructor() ATM {
return ATM{}
}
func (this *ATM) Deposit(banknotesCount []int) {
for i, x := range banknotesCount {
this[i] += x
}
}
func (this *ATM) Withdraw(amount int) []int {
ans := make([]int, m)
for i := m - 1; i >= 0; i-- {
ans[i] = min(amount/d[i], this[i])
amount -= ans[i] * d[i]
}
if amount > 0 {
return []int{-1}
}
for i, x := range ans {
this[i] -= x
}
return ans
}
/**
* Your ATM object will be instantiated and called as such:
* obj := Constructor();
* obj.Deposit(banknotesCount);
* param_2 := obj.Withdraw(amount);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Arrays | Time Complexity: O(1) for both deposit and withdraw since the number of denominations is constant. |
| Hash Map Approach | Time Complexity: O(1) for both operations since they work over a constant set of keys. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Approach Using Arrays | O(1) | O(1) | Best choice when denominations are fixed and known in advance |
| Hash Map Approach | O(1) | O(1) | Useful when denominations might change or need dynamic configuration |
Frequently asked questions
Is Design an ATM Machine easy or hard?
The problem is rated Medium because it combines greedy reasoning with class design. The logic itself is straightforward, but you must carefully manage note counts and handle the case where a withdrawal cannot be satisfied exactly.
Design an ATM Machine Python/Java solution
Implement an ATM class with an internal array storing note counts. The deposit method adds counts directly to the array, while withdraw iterates from the largest denomination to the smallest using a greedy calculation. The same logic works across Python, Java, C++, C#, and JavaScript.
How to solve Design an ATM Machine in O(1)?
Maintain an array storing counts for the five denominations. For withdrawal, iterate from the largest denomination to the smallest and greedily take as many notes as possible without exceeding the remaining amount. If the remaining amount becomes zero, update the counts; otherwise return [-1]. Because only five denominations are processed, the algorithm runs in constant time.
What is the best approach for Design an ATM Machine?
The greedy approach using an array is the most efficient solution. Store the count of each denomination in a fixed array and process withdrawals from the largest denomination (500) down to the smallest (20). This guarantees the maximum-value notes are used first and runs in O(1) time because only five denominations are processed.
Is Design an ATM Machine asked at Google/Amazon/Meta?
Design-style data structure problems like this frequently appear in interviews at large tech companies. Variants of banking system simulations, resource allocation, or cashier systems have been reported in interviews at Amazon and other large-scale backend teams.
What data structure is used in Design an ATM Machine?
The most common implementation uses a fixed-size array to store counts of banknotes for denominations [20, 50, 100, 200, 500]. Some solutions use a hash map mapping denomination values to counts, but an array is simpler and more efficient because the set of denominations is fixed.
What is the time complexity of Design an ATM Machine?
Both deposit and withdraw operations run in O(1) time. The ATM supports exactly five banknote denominations, so every operation loops through a constant-size array. Space complexity is also O(1) because only five counters are stored.