Simple Bank System

Medium Design Data Structures Pre-processing + tradeoffs Original on LeetCode

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): move money from account1 to account2.
  • deposit(account, money): add money to account.
  • withdraw(account, money): take money out of account.

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^5 and 0 <= balance[i] <= 10^12
  • 1 <= account, account1, account2 <= 10^5
  • 0 <= money <= 10^12
  • At most 10^4 calls are made to transfer, deposit and withdraw in 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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (list of account records, linear search)O(n) per operationO(n)
Optimal (direct array indexing)O(1) per operationO(n)

2Optimal (direct array indexing)

TimeO(1) per operationEach call does a constant number of comparisons and array updates.
SpaceO(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.

  1. Constructor: keep the balance array (64-bit values).
  2. valid(a) = 1 <= a <= n.
  3. deposit: if !valid(a) return false; bal[a - 1] += money.
  4. withdraw: if !valid(a) or bal[a - 1] < money return false; bal[a - 1] -= money.
  5. 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;
    }
}

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.