# Simple Bank System
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/simple-bank-system)
Canonical: https://scaleengineer.com/dsa/problems/simple-bank-system
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Dropbox](https://scaleengineer.com/companies/dropbox), [Capital One](https://scaleengineer.com/companies/capital-one), [PhonePe](https://scaleengineer.com/companies/phonepe), [Coinbase](https://scaleengineer.com/companies/coinbase), [Circle](https://scaleengineer.com/companies/circle)
---
## Problem
You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has `n` accounts numbered from `1` to `n`. The initial balance of each account is stored in a **0-indexed** integer array `balance`, with the `(i + 1)th` account having an initial balance of `balance[i]`.

Execute all the **valid** transactions. A transaction is **valid** if:

* The given account number(s) are between `1` and `n`, and
* The amount of money withdrawn or transferred from is **less than or equal** to the balance of the account.

Implement the `Bank` class:

* `Bank(long[] balance)` Initializes the object with the **0-indexed** integer array `balance`.
* `boolean transfer(int account1, int account2, long money)` Transfers `money` dollars from the account numbered `account1` to the account numbered `account2`. Return `true` if the transaction was successful, `false` otherwise.
* `boolean deposit(int account, long money)` Deposit `money` dollars into the account numbered `account`. Return `true` if the transaction was successful, `false` otherwise.
* `boolean withdraw(int account, long money)` Withdraw `money` dollars from the account numbered `account`. Return `true` if the transaction was successful, `false` otherwise.

**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**
Bank bank = new Bank([10, 100, 20, 50, 30]);
bank.withdraw(3, 10);    // return true, account 3 has a balance of $20, so it is valid to withdraw $10.
                         // Account 3 has $20 - $10 = $10.
bank.transfer(5, 1, 20); // return true, account 5 has a balance of $30, so it is valid to transfer $20.
                         // Account 5 has $30 - $20 = $10, and account 1 has $10 + $20 = $30.
bank.deposit(5, 20);     // return true, it is valid to deposit $20 to account 5.
                         // Account 5 has $10 + $20 = $30.
bank.transfer(3, 4, 15); // return false, the current balance of account 3 is $10,
                         // so it is invalid to transfer $15 from it.
bank.withdraw(10, 50);   // return false, it is invalid because account 10 does not exist.

**Constraints:**

* `n == balance.length`
* `1 <= n, account, account1, account2 <= 105`
* `0 <= balance[i], money <= 1012`
* At most `104` calls will be made to **each** function `transfer`, `deposit`, `withdraw`.

# Approaches
## Using a HashMap to Store Balances
This approach uses a `HashMap` to store the account balances. The keys of the map are the account numbers (integers), and the values are their corresponding balances (longs). While functionally correct, this method introduces overhead in terms of both memory and initialization time compared to using a simple array, making it less efficient for this specific problem.
**Time:** Constructor: O(n), where n is the number of accounts, to populate the HashMap.
`transfer`, `deposit`, `withdraw`: O(1) on average for each operation, as HashMap operations (`get`, `put`, `containsKey`) take constant time on average. · **Space:** O(n), where n is the number of accounts. The HashMap needs to store n key-value pairs, which incurs more memory overhead per entry than a simple array.
**Pros:** Conceptually straightforward if one is very familiar with maps.; Handles non-contiguous or non-integer account numbers gracefully (though not required by this problem).
**Cons:** Higher memory usage compared to an array due to the overhead of HashMap data structures (storing keys, values, and handling hash collisions).; Slightly slower in practice than direct array access due to the computational cost of hashing and potential collisions.; Requires an O(n) initialization step to copy data from the input array into the map.
### Explanation
### Initialization (`Bank` constructor)
A `HashMap<Integer, Long>` is created to store the balances. The constructor iterates through the input `balance` array. For each element `balance[i]`, it adds an entry to the map with the key `i + 1` and the value `balance[i]`. This populates the map with all initial account balances.

### Transaction Logic (`transfer`, `deposit`, `withdraw`)
Before any transaction, we first validate the account numbers by checking if they exist as keys in the HashMap using `containsKey()`. This is an O(1) operation on average. For `withdraw` and `transfer`, we retrieve the current balance using `get()` and check if it's sufficient for the transaction. If all checks pass, the balances are updated using the `put()` method.

```java
import java.util.HashMap;
import java.util.Map;

class Bank {
    private Map<Integer, Long> accounts;

    public Bank(long[] balance) {
        accounts = new HashMap<>();
        for (int i = 0; i < balance.length; i++) {
            accounts.put(i + 1, balance[i]);
        }
    }

    public boolean transfer(int account1, int account2, long money) {
        if (!accounts.containsKey(account1) || !accounts.containsKey(account2)) {
            return false;
        }
        if (accounts.get(account1) < money) {
            return false;
        }
        accounts.put(account1, accounts.get(account1) - money);
        accounts.put(account2, accounts.get(account2) + money);
        return true;
    }

    public boolean deposit(int account, long money) {
        if (!accounts.containsKey(account)) {
            return false;
        }
        accounts.put(account, accounts.get(account) + money);
        return true;
    }

    public boolean withdraw(int account, long money) {
        if (!accounts.containsKey(account)) {
            return false;
        }
        if (accounts.get(account) < money) {
            return false;
        }
        accounts.put(account, accounts.get(account) - money);
        return true;
    }
}
```
### Algorithm
- In the `Bank` constructor, initialize a `HashMap<Integer, Long>` to store account balances.
- Iterate through the input `balance` array. For each index `i`, insert a key-value pair `(i + 1, balance[i])` into the HashMap. This maps each account number to its initial balance.
- For each transaction method (`transfer`, `deposit`, `withdraw`):
  - First, validate the account numbers by checking if they exist as keys in the HashMap using `containsKey()`.
  - For `withdraw` and `transfer`, retrieve the balance of the source account using `get()` and verify if there are sufficient funds.
  - If all checks pass, update the balances in the HashMap using the `put()` method.

## Using an Array for Direct Access
This is the most efficient approach. It leverages a simple `long` array to store the account balances. Since account numbers (from 1 to `n`) map directly to array indices (from 0 to `n-1`), we can access and update any account's balance in constant time with minimal overhead.
**Time:** Constructor: O(1), as it only stores a reference to the input array and its length.
`transfer`, `deposit`, `withdraw`: O(1) for each operation. Array access by index is a constant time operation. · **Space:** O(1) additional space. The class only stores a reference to the input array, not a copy. The O(n) space for the balances themselves is considered part of the input.
**Pros:** Optimal time complexity (O(1) for all transactions).; Minimal space complexity (O(1) extra space).; Extremely fast in practice due to direct memory access and good cache locality.; Simple, clean, and easy-to-understand implementation.
**Cons:** This approach is tightly coupled to the problem's constraint that account numbers are a contiguous sequence from 1 to n. It would be less suitable if account numbers were sparse or non-numeric.
### Explanation
### Initialization (`Bank` constructor)
The `Bank` class stores a reference to the input `balance` array and its length, `n`. This is an O(1) operation, as no data is copied or transformed. The original array is used as the single source of truth for all account balances.

### Transaction Logic (`transfer`, `deposit`, `withdraw`)
The core of this approach is the direct mapping from account numbers to array indices. An account number `account` corresponds to the index `account - 1`. 
1.  **Validation**: Each transaction method first checks if the provided account numbers are valid (i.e., between 1 and `n`). This prevents `ArrayIndexOutOfBoundsException`.
2.  **Execution**: If the accounts are valid, the transaction logic is executed. For withdrawals and transfers, it checks if `balance[account - 1]` is sufficient. If so, the balances are updated directly in the array. All these operations—index calculation, array access, and arithmetic—are extremely fast.

```java
class Bank {
    private long[] balance;
    private int n;

    public Bank(long[] balance) {
        this.balance = balance;
        this.n = balance.length;
    }

    private boolean isValid(int account) {
        return account >= 1 && account <= n;
    }

    public boolean transfer(int account1, int account2, long money) {
        if (!isValid(account1) || !isValid(account2)) {
            return false;
        }
        if (balance[account1 - 1] < money) {
            return false;
        }
        balance[account1 - 1] -= money;
        balance[account2 - 1] += money;
        return true;
    }

    public boolean deposit(int account, long money) {
        if (!isValid(account)) {
            return false;
        }
        balance[account - 1] += money;
        return true;
    }

    public boolean withdraw(int account, long money) {
        if (!isValid(account)) {
            return false;
        }
        if (balance[account - 1] < money) {
            return false;
        }
        balance[account - 1] -= money;
        return true;
    }
}
```
### Algorithm
- In the `Bank` constructor, store a reference to the input `balance` array and its length `n` as class members.
- Create a helper method `isValid(int account)` that checks if an account number is within the valid range `[1, n]`.
- For each transaction method (`transfer`, `deposit`, `withdraw`):
  - Use the `isValid()` helper to validate the given account number(s). If invalid, return `false`.
  - Convert the 1-based account number to a 0-based array index (i.e., `account - 1`).
  - For `withdraw` and `transfer`, check if the source account has sufficient funds by accessing `balance[account - 1]`.
  - If the transaction is valid, update the balance(s) directly in the array at the calculated index.
  - Return `true`.

# Solutions
### Java

```java
class Bank { private long [] balance ; private int n ; public Bank ( long [] balance ) { this . balance = balance ; this . n = balance . length ; } public boolean transfer ( int account1 , int account2 , long money ) { if ( account1 > n || account2 > n || balance [ account1 - 1 ] < money ) { return false ; } balance [ account1 - 1 ] -= money ; balance [ account2 - 1 ] += money ; return true ; } public boolean deposit ( int account , long money ) { if ( account > n ) { return false ; } balance [ account - 1 ] += money ; return true ; } public boolean withdraw ( int account , long money ) { if ( account > n || balance [ account - 1 ] < money ) { return false ; } balance [ account - 1 ] -= money ; return true ; } } /** * Your Bank object will be instantiated and called as such: * Bank obj = new Bank(balance); * boolean param_1 = obj.transfer(account1,account2,money); * boolean param_2 = obj.deposit(account,money); * boolean param_3 = obj.withdraw(account,money); */
```

### CPP

```cpp
class Bank { public: vector < long long > balance ; int n ; Bank ( vector < long long >& balance ) { this -> balance = balance ; n = balance . size (); } bool transfer ( int account1 , int account2 , long long money ) { if ( account1 > n || account2 > n || balance [ account1 - 1 ] < money ) return false ; balance [ account1 - 1 ] -= money ; balance [ account2 - 1 ] += money ; return true ; } bool deposit ( int account , long long money ) { if ( account > n ) return false ; balance [ account - 1 ] += money ; return true ; } bool withdraw ( int account , long long money ) { if ( account > n || balance [ account - 1 ] < money ) return false ; balance [ account - 1 ] -= money ; return true ; } }; /** * Your Bank object will be instantiated and called as such: * Bank* obj = new Bank(balance); * bool param_1 = obj->transfer(account1,account2,money); * bool param_2 = obj->deposit(account,money); * bool param_3 = obj->withdraw(account,money); */
```

### Python

```python
class Bank : def __init__ ( self , balance : List [ int ]): self . balance = balance self . n = len ( balance ) def transfer ( self , account1 : int , account2 : int , money : int ) -> bool : if account1 > self . n or account2 > self . n or self . balance [ account1 - 1 ] < money : return False self . balance [ account1 - 1 ] -= money self . balance [ account2 - 1 ] += money return True def deposit ( self , account : int , money : int ) -> bool : if account > self . n : return False self . balance [ account - 1 ] += money return True def withdraw ( self , account : int , money : int ) -> bool : if account > self . n or self . balance [ account - 1 ] < money : return False self . balance [ account - 1 ] -= money return True # Your Bank object will be instantiated and called as such: # obj = Bank(balance) # param_1 = obj.transfer(account1,account2,money) # param_2 = obj.deposit(account,money) # param_3 = obj.withdraw(account,money)
```