Problem statement

A bank has n accounts numbered 1 to n; the starting balance of account i + 1 is balance[i]. Write the class Bank, which carries out transactions and refuses the invalid ones.

A transaction is valid when every account number it names is between 1 and n, and the account money leaves holds at least that much money.

• Bank(int[] balance) opens the accounts.
• boolean transfer(int account1, int account2, int money) moves money from account1 to account2.
• boolean deposit(int account, int money) adds money to account.
• boolean withdraw(int account, int money) takes money out of account.

Each method performs the transaction and returns true if it is valid; otherwise it changes nothing and returns false. (LeetCode's version allows balances up to 10^12; here they are reduced so that every balance fits a signed 32-bit integer, as the constraints show.)

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["Bank","withdraw","transfer","deposit","transfer","withdraw"]
[[[10,100,20,50,30]],[3,10],[5,1,20],[5,20],[3,4,15],[10,50]]
Output: [null,true,true,true,false,false]
Explanation: Account 3 goes from 20 to 10. Account 5 sends 20 to account 1 (5 now holds 10) and then receives 20 (30). Account 3 holds only 10, so it cannot send 15. Account 10 does not exist.

Example 2

Input: ["Bank","transfer","withdraw","deposit","withdraw"]
[[[0,7]],[2,2,7],[1,1],[1,5],[1,5]]
Output: [null,true,false,true,true]
Explanation: A transfer from an account to itself is valid when the balance covers it. Account 1 starts empty, so the first withdrawal fails; after a deposit of 5 the same withdrawal of 5 succeeds.

Constraints

• n == balance.length
• 1 <= n <= 1000
• 0 <= balance[i] <= 10^6
• 1 <= account, account1, account2 <= 10^5
• 0 <= money <= 10^6
• At most 1000 calls are made to the three methods in total
• So every balance stays below 10^9 + 10^9 < 2^31

Hints for Simple Bank System

1. Hint 1

   This is a simulation: store the balances in an array, with account a at index a - 1.

2. Hint 2

   Write one helper that says whether an account number is valid, and check everything before changing anything.

3. Hint 3

   transfer needs both accounts valid and balance[account1] >= money; deposit only a valid account; withdraw a valid account holding at least money. A transfer to the same account is allowed.

How to solve Simple Bank System

Keep the balances in an array and validate each transaction completely before applying it, so a refused transaction leaves no trace.

Approach

1. Store a copy of balance; valid(a) is 1 <= a <= n.
2. transfer(a, b, m): if valid(a), valid(b) and bal[a-1] >= m, subtract m from a, add it to b, return true; else false.
3. deposit(a, m): if valid(a), add m and return true; else false.
4. withdraw(a, m): if valid(a) and bal[a-1] >= m, subtract and return true; else false.

Why it works

Each method checks exactly the conditions the statement lists and mutates only after all of them hold. In a transfer between the same account the subtraction and the addition cancel, which is the correct result of a valid self-transfer.

Complexity

• Time — O(1) per call
• Space — O(n)

Pitfalls

• Accounts are numbered from 1; index a - 1, and reject a > n — the argument can be as large as 10^5.
• Check the second account of a transfer before taking the money from the first.
• On LeetCode the balances are 64-bit; with the reduced constraints here 32 bits suffice, but a long costs nothing.

Reference solution

Python

class Bank:

    def __init__(self, balance: List[int]):
        self.bal = list(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) and 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 True

Java

class Bank {
    private long[] bal;

    public Bank(int[] balance) {
        bal = new long[balance.length];
        for (int i = 0; i < balance.length; i++) bal[i] = balance[i];
    }

    private boolean valid(int a) {
        return a >= 1 && a <= bal.length;
    }

    public boolean transfer(int account1, int account2, int 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, int money) {
        if (!valid(account)) return false;
        bal[account - 1] += money;
        return true;
    }

    public boolean withdraw(int account, int money) {
        if (!valid(account) || bal[account - 1] < money) return false;
        bal[account - 1] -= money;
        return true;
    }
}

C++

class Bank {
    vector<long long> bal;

    bool valid(int a) { return a >= 1 && a <= (int)bal.size(); }
public:
    Bank(vector<int>& balance) : bal(balance.begin(), balance.end()) {}

    bool transfer(int account1, int account2, int 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, int money) {
        if (!valid(account)) return false;
        bal[account - 1] += money;
        return true;
    }

    bool withdraw(int account, int money) {
        if (!valid(account) || bal[account - 1] < money) return false;
        bal[account - 1] -= money;
        return true;
    }
};

JavaScript

var Bank = function(balance) {
    this.bal = balance.slice();
};

Bank.prototype.valid = function(a) {
    return a >= 1 && a <= this.bal.length;
};

Bank.prototype.transfer = function(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;
};

Bank.prototype.deposit = function(account, money) {
    if (!this.valid(account)) return false;
    this.bal[account - 1] += money;
    return true;
};

Bank.prototype.withdraw = function(account, money) {
    if (!this.valid(account) || this.bal[account - 1] < money) return false;
    this.bal[account - 1] -= money;
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium