Simple Bank System
Simple Bank System is a medium design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (direct array indexing), runs in O(1) per operation time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list of account records, linear search) up.
Problem
Build a Bank class for a bank with n accounts, numbered 1 to n. The starting balance of account i is balance[i - 1].
Support three operations, each returning true if it went through and false otherwise:
transfer(account1, account2, money): movemoneyfromaccount1toaccount2.deposit(account, money): addmoneytoaccount.withdraw(account, money): takemoneyout ofaccount.
An operation fails, and changes nothing, if it names an account number outside 1..n, or if it would take more money out of an account than that account currently holds.
Examples
Example 1
- Input
Bank([50, 0, 30]), transfer(1, 2, 20), withdraw(3, 40), deposit(2, 5), withdraw(2, 25)- Output
true, false, true, true- Why
- Account 2 gets 20 and then 5, so it can pay out 25; account 3 holds only 30, so taking 40 fails.
Example 2
- Input
Bank([7]), deposit(2, 10), transfer(1, 1, 7), withdraw(1, 8)- Output
false, true, false- Why
- Account 2 does not exist; moving money from account 1 to itself is allowed; 8 is more than the 7 in account 1.
Constraints
1 <= balance.length <= 10^5and0 <= balance[i] <= 10^121 <= account, account1, account2 <= 10^50 <= money <= 10^12- At most
10^4calls are made totransfer,depositandwithdrawin total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (list of account records, linear search) | O(n) per operation | O(n) |
| Optimal (direct array indexing) | O(1) per operation | O(n) |
1Brute force (list of account records, linear search)
O(n) per operationEach lookup may scan every account record.O(n)One record per account.Keep a list of (accountNumber, balance) records and find an account by scanning the list. Every operation looks up the accounts it needs, checks the rules, and only then updates the balances.
- Constructor: store a record (i + 1, balance[i]) for every i.
- find(id): scan the list for the record with that number, or return none.
- deposit: find the account; if missing return false; add money.
- withdraw: find the account; if missing or its balance < money return false; subtract money.
- transfer: find both accounts; if either is missing or the source has too little, return false; move the money.
class Bank {
private final List<long[]> accounts = new ArrayList<>();
public Bank(long[] balance) {
for (int i = 0; i < balance.length; i++) {
accounts.add(new long[] { i + 1, balance[i] });
}
}
private long[] find(int id) {
for (long[] acc : accounts) {
if (acc[0] == id) {
return acc;
}
}
return null;
}
public boolean transfer(int account1, int account2, long money) {
long[] from = find(account1), to = find(account2);
if (from == null || to == null || from[1] < money) {
return false;
}
from[1] -= money;
to[1] += money;
return true;
}
public boolean deposit(int account, long money) {
long[] acc = find(account);
if (acc == null) {
return false;
}
acc[1] += money;
return true;
}
public boolean withdraw(int account, long money) {
long[] acc = find(account);
if (acc == null || acc[1] < money) {
return false;
}
acc[1] -= money;
return true;
}
}class Bank:
def __init__(self, balance: List[int]):
self.accounts = [[i + 1, b] for i, b in enumerate(balance)]
def _find(self, id: int):
for acc in self.accounts:
if acc[0] == id:
return acc
return None
def transfer(self, account1: int, account2: int, money: int) -> bool:
src, dst = self._find(account1), self._find(account2)
if src is None or dst is None or src[1] < money:
return False
src[1] -= money
dst[1] += money
return True
def deposit(self, account: int, money: int) -> bool:
acc = self._find(account)
if acc is None:
return False
acc[1] += money
return True
def withdraw(self, account: int, money: int) -> bool:
acc = self._find(account)
if acc is None or acc[1] < money:
return False
acc[1] -= money
return Trueclass Bank {
vector<pair<int, long long>> accounts;
pair<int, long long>* find(int id) {
for (auto& acc : accounts) {
if (acc.first == id) {
return &acc;
}
}
return nullptr;
}
public:
Bank(vector<long long>& balance) {
for (int i = 0; i < (int)balance.size(); i++) {
accounts.push_back({i + 1, balance[i]});
}
}
bool transfer(int account1, int account2, long long money) {
auto* from = find(account1);
auto* to = find(account2);
if (!from || !to || from->second < money) {
return false;
}
from->second -= money;
to->second += money;
return true;
}
bool deposit(int account, long long money) {
auto* acc = find(account);
if (!acc) {
return false;
}
acc->second += money;
return true;
}
bool withdraw(int account, long long money) {
auto* acc = find(account);
if (!acc || acc->second < money) {
return false;
}
acc->second -= money;
return true;
}
};class Bank {
constructor(balance) {
this.accounts = balance.map((b, i) => [i + 1, b]);
}
find(id) {
for (const acc of this.accounts) {
if (acc[0] === id) {
return acc;
}
}
return null;
}
transfer(account1, account2, money) {
const from = this.find(account1), to = this.find(account2);
if (from === null || to === null || from[1] < money) {
return false;
}
from[1] -= money;
to[1] += money;
return true;
}
deposit(account, money) {
const acc = this.find(account);
if (acc === null) {
return false;
}
acc[1] += money;
return true;
}
withdraw(account, money) {
const acc = this.find(account);
if (acc === null || acc[1] < money) {
return false;
}
acc[1] -= money;
return true;
}
}2Optimal (direct array indexing)
O(1) per operationEach call does a constant number of comparisons and array updates.O(n)The balance array holds one value per account.Account numbers are exactly 1 to n, so account a lives at index a - 1 of the balance array. A number is valid when it is between 1 and n. Every operation becomes a range check, a balance check and one or two array updates.
- Constructor: keep the balance array (64-bit values).
- valid(a) = 1 <= a <= n.
- deposit: if !valid(a) return false; bal[a - 1] += money.
- withdraw: if !valid(a) or bal[a - 1] < money return false; bal[a - 1] -= money.
- transfer: if either account is invalid or bal[account1 - 1] < money return false; subtract from one, add to the other.
class Bank {
private final long[] bal;
public Bank(long[] balance) {
bal = balance;
}
private boolean valid(int a) {
return a >= 1 && a <= bal.length;
}
public boolean transfer(int account1, int account2, long money) {
if (!valid(account1) || !valid(account2) || bal[account1 - 1] < money) {
return false;
}
bal[account1 - 1] -= money;
bal[account2 - 1] += money;
return true;
}
public boolean deposit(int account, long money) {
if (!valid(account)) {
return false;
}
bal[account - 1] += money;
return true;
}
public boolean withdraw(int account, long money) {
if (!valid(account) || bal[account - 1] < money) {
return false;
}
bal[account - 1] -= money;
return true;
}
}class Bank:
def __init__(self, balance: List[int]):
self.bal = balance
def _valid(self, a: int) -> bool:
return 1 <= a <= len(self.bal)
def transfer(self, account1: int, account2: int, money: int) -> bool:
if not self._valid(account1) or not self._valid(account2) or self.bal[account1 - 1] < money:
return False
self.bal[account1 - 1] -= money
self.bal[account2 - 1] += money
return True
def deposit(self, account: int, money: int) -> bool:
if not self._valid(account):
return False
self.bal[account - 1] += money
return True
def withdraw(self, account: int, money: int) -> bool:
if not self._valid(account) or self.bal[account - 1] < money:
return False
self.bal[account - 1] -= money
return Trueclass Bank {
vector<long long> bal;
bool valid(int a) {
return a >= 1 && a <= (int)bal.size();
}
public:
Bank(vector<long long>& balance) : bal(balance) {}
bool transfer(int account1, int account2, long long money) {
if (!valid(account1) || !valid(account2) || bal[account1 - 1] < money) {
return false;
}
bal[account1 - 1] -= money;
bal[account2 - 1] += money;
return true;
}
bool deposit(int account, long long money) {
if (!valid(account)) {
return false;
}
bal[account - 1] += money;
return true;
}
bool withdraw(int account, long long money) {
if (!valid(account) || bal[account - 1] < money) {
return false;
}
bal[account - 1] -= money;
return true;
}
};class Bank {
constructor(balance) {
this.bal = balance;
}
valid(a) {
return a >= 1 && a <= this.bal.length;
}
transfer(account1, account2, money) {
if (!this.valid(account1) || !this.valid(account2) || this.bal[account1 - 1] < money) {
return false;
}
this.bal[account1 - 1] -= money;
this.bal[account2 - 1] += money;
return true;
}
deposit(account, money) {
if (!this.valid(account)) {
return false;
}
this.bal[account - 1] += money;
return true;
}
withdraw(account, money) {
if (!this.valid(account) || this.bal[account - 1] < money) {
return false;
}
this.bal[account - 1] -= money;
return true;
}
}Edge cases to test
- An account number of 0 or larger than n is invalid
- A transfer where only one of the two accounts exists
- Withdrawing or transferring exactly the full balance
- A transfer from an account to itself
- Moving 0 money, which always succeeds on valid accounts
- Balances above 2^31, so a 64-bit type is needed
Hints
Hint 1
Accounts are numbered 1 to n with no gaps. How can you find an account's balance without searching?
Hint 2
Check every condition (accounts exist, enough money) before changing any balance, so a failed call changes nothing.
FAQ
What is the best time complexity for Simple Bank System?
Optimal (direct array indexing) runs in O(1) per operation time and O(n) extra space. Each call does a constant number of comparisons and array updates.
Which pattern does Simple Bank System use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Design File System, Design HashMap.
Is there a brute force solution for Simple Bank System?
Yes. Brute force (list of account records, linear search) takes O(n) per operation time and O(n) space. Keep a list of (accountNumber, balance) records and find an account by scanning the list.
Which edge cases should I test for Simple Bank System?
An account number of 0 or larger than n is invalid; A transfer where only one of the two accounts exists; Withdrawing or transferring exactly the full balance; A transfer from an account to itself; Moving 0 money, which always succeeds on valid accounts; Balances above 2^31, so a 64-bit type is needed.