LeetCode 2043 - Simple Bank System

LeetCode Problem 2043

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design, Simulation

Solution

Problem Understanding

This problem asks us to design a very simple banking system that supports three operations:

Transfer money between two accounts
Deposit money into an account
Withdraw money from an account

The bank contains n accounts numbered from 1 to n. The initial balance for each account is given in a 0-indexed array named balance, where:

balance[0] corresponds to account 1
balance[1] corresponds to account 2
and so on

The important detail is that account numbering is 1-based, while the array storing balances is 0-based. This mismatch is a very common source of implementation bugs.

Each operation must validate the transaction before modifying balances.

A transaction is considered valid if:

Every referenced account number exists, meaning it is between 1 and n
Any withdrawal or transfer amount does not exceed the source account's current balance

If the transaction is valid, the balances are updated and the method returns true. Otherwise, nothing changes and the method returns false.

The constraints tell us several important things:

There can be up to 10^5 accounts
Each balance and transaction amount can be as large as 10^12
Up to 10^4 operations may be performed

The very large money limit means we must use 64-bit integer types:

Python integers automatically support large values
Go must use int64

The operation count is relatively small, but each operation should still ideally run in constant time.

Several edge cases are important:

Attempting to access an account number outside [1, n]
Withdrawing more money than available
Transferring from or to invalid accounts
Transferring exactly the current balance
Depositing or withdrawing 0
Handling extremely large balances safely

The problem guarantees that inputs themselves follow the type constraints, so we do not need to worry about malformed input formats.

Approaches

Brute Force Approach

A naive implementation might store accounts in a list of account objects and linearly search for an account every time an operation occurs.

For example:

To transfer money, scan the entire structure to find account1
Scan again to find account2
Then perform validation and updates

This approach is correct because every operation eventually locates the required accounts and updates balances appropriately.

However, linear searches are unnecessary because account numbers are already sequential and directly map to array indices.

If each operation requires scanning up to n accounts, the time complexity becomes O(n) per operation. With up to 10^4 operations and 10^5 accounts, this becomes inefficient.

Optimal Approach

The key observation is that account numbers map directly to positions in the balance array.

Since:

Account 1 maps to index 0
Account 2 maps to index 1
Account k maps to index k - 1

We can access any account balance instantly using array indexing.

This allows all operations to run in constant time:

Validate indices
Check sufficient funds if necessary
Update balances directly

No extra data structures are needed beyond the balance array itself.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per operation	O(n)	Linear search for accounts
Optimal	O(1) per operation	O(n)	Direct array indexing

Algorithm Walkthrough

Optimal Algorithm

Store the balances array inside the Bank object.

This array represents the current state of all accounts. Since account numbers are sequential, we can directly map an account number to an array index using account - 1. 2. Create a helper validation check for account numbers.

Before performing any operation, verify that the account number is between 1 and n. Invalid account access should immediately return false. 3. For deposits:

Validate the account
Add the money directly to the balance
Return true

Deposits never fail due to insufficient funds because money is only being added. 4. For withdrawals:

Validate the account
Check whether the balance is at least the requested amount
If not, return false
Otherwise subtract the amount and return true

For transfers:

Validate both accounts
Check whether the source account has enough money
If not, return false
Otherwise subtract from the sender and add to the receiver

Always modify balances only after validation succeeds.

This ensures failed transactions do not partially update the bank state.

Why it works

The algorithm works because the balance array always stores the current correct balance for every account. Every operation first validates its preconditions before making any modifications.

The invariant maintained throughout execution is:

The balance array always reflects the correct state of all accounts after every successful transaction.

Since all updates are done atomically after validation, invalid transactions never corrupt the bank state.

Python Solution

from typing import List

class Bank:

    def __init__(self, balance: List[int]):
        self.balance = balance
        self.n = len(balance)

    def is_valid_account(self, account: int) -> bool:
        return 1 <= account <= self.n

    def transfer(self, account1: int, account2: int, money: int) -> bool:
        if not self.is_valid_account(account1):
            return False

        if not self.is_valid_account(account2):
            return False

        sender_index = account1 - 1
        receiver_index = account2 - 1

        if self.balance[sender_index] < money:
            return False

        self.balance[sender_index] -= money
        self.balance[receiver_index] += money

        return True

    def deposit(self, account: int, money: int) -> bool:
        if not self.is_valid_account(account):
            return False

        index = account - 1
        self.balance[index] += money

        return True

    def withdraw(self, account: int, money: int) -> bool:
        if not self.is_valid_account(account):
            return False

        index = account - 1

        if self.balance[index] < money:
            return False

        self.balance[index] -= 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)

The implementation stores the balances directly inside the class and keeps the total number of accounts in self.n.

The helper method is_valid_account centralizes account validation logic. This avoids repeating the same range check throughout the code and makes the implementation cleaner.

The transfer method first validates both accounts. It then converts the 1-based account numbers into 0-based array indices. Only after confirming sufficient funds does it modify balances.

The deposit method is the simplest operation because it only needs account validation before adding money.

The withdraw method validates the account and checks whether enough balance exists before subtracting the amount.

All operations run in constant time because array access is O(1).

Go Solution

type Bank struct {
	balance []int64
	n       int
}

func Constructor(balance []int64) Bank {
	return Bank{
		balance: balance,
		n:       len(balance),
	}
}

func (this *Bank) isValidAccount(account int) bool {
	return account >= 1 && account <= this.n
}

func (this *Bank) Transfer(account1 int, account2 int, money int64) bool {
	if !this.isValidAccount(account1) {
		return false
	}

	if !this.isValidAccount(account2) {
		return false
	}

	senderIndex := account1 - 1
	receiverIndex := account2 - 1

	if this.balance[senderIndex] < money {
		return false
	}

	this.balance[senderIndex] -= money
	this.balance[receiverIndex] += money

	return true
}

func (this *Bank) Deposit(account int, money int64) bool {
	if !this.isValidAccount(account) {
		return false
	}

	index := account - 1
	this.balance[index] += money

	return true
}

func (this *Bank) Withdraw(account int, money int64) bool {
	if !this.isValidAccount(account) {
		return false
	}

	index := account - 1

	if this.balance[index] < money {
		return false
	}

	this.balance[index] -= money

	return true
}

/**
 * Your Bank object will be instantiated and called as such:
 * obj := Constructor(balance);
 * param_1 := obj.Transfer(account1, account2, money);
 * param_2 := obj.Deposit(account, money);
 * param_3 := obj.Withdraw(account, money);
 */

The Go implementation closely mirrors the Python version, but there are several language-specific details worth noting.

The balance slice uses int64 because transaction amounts can be as large as 10^12, which may exceed the range of a normal 32-bit integer.

Go does not support methods outside a type implicitly, so the validation helper is implemented as a receiver method named isValidAccount.

Slices in Go already provide efficient dynamic array behavior, so no additional structures are necessary.

Worked Examples

Example 1

Initial balances:

Account	Balance
1	10
2	100
3	20
4	50
5	30

Operation:

withdraw(3, 10)

Validation:

Account 3 exists
Balance is 20
20 >= 10, valid

Update:

Account	New Balance
1	10
2	100
3	10
4	50
5	30

Return value:

true

Transfer Operation

Operation:

transfer(5, 1, 20)

Validation:

Account 5 exists
Account 1 exists
Account 5 balance is 30
30 >= 20, valid

Update:

Account	New Balance
1	30
2	100
3	10
4	50
5	10

Return value:

true

Deposit Operation

Operation:

deposit(5, 20)

Validation:

Account 5 exists

Update:

Account	New Balance
1	30
2	100
3	10
4	50
5	30

Return value:

true

Failed Transfer

Operation:

transfer(3, 4, 15)

Validation:

Account 3 exists
Account 4 exists
Account 3 balance is 10
10 < 15, invalid

No balances change.

Return value:

false

Invalid Account

Operation:

withdraw(10, 50)

Validation:

Account 10 does not exist

No balances change.

Return value:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per operation	Direct array access and constant-time validation
Space	O(n)	Stores balances for all accounts

Each operation performs only a few constant-time checks and updates. No loops or recursive calls are involved. The only memory used is the balance array itself, which stores one value per account.

Test Cases

# Provided example
bank = Bank([10, 100, 20, 50, 30])

assert bank.withdraw(3, 10) == True   # valid withdrawal
assert bank.transfer(5, 1, 20) == True   # valid transfer
assert bank.deposit(5, 20) == True   # valid deposit
assert bank.transfer(3, 4, 15) == False   # insufficient funds
assert bank.withdraw(10, 50) == False   # invalid account

# Single account
bank = Bank([100])

assert bank.deposit(1, 50) == True   # deposit into only account
assert bank.withdraw(1, 75) == True   # valid withdrawal
assert bank.withdraw(1, 100) == False   # insufficient funds

# Exact balance withdrawal
bank = Bank([200])

assert bank.withdraw(1, 200) == True   # withdraw entire balance
assert bank.balance[0] == 0

# Invalid source account
bank = Bank([10, 20])

assert bank.transfer(3, 1, 5) == False   # invalid sender

# Invalid destination account
bank = Bank([10, 20])

assert bank.transfer(1, 5, 5) == False   # invalid receiver

# Transfer entire balance
bank = Bank([50, 0])

assert bank.transfer(1, 2, 50) == True
assert bank.balance == [0, 50]

# Zero transaction amounts
bank = Bank([100])

assert bank.deposit(1, 0) == True
assert bank.withdraw(1, 0) == True

# Very large values
bank = Bank([10**12])

assert bank.deposit(1, 10**12) == True
assert bank.balance[0] == 2 * 10**12

# Multiple sequential operations
bank = Bank([100, 200, 300])

assert bank.transfer(1, 2, 50) == True
assert bank.withdraw(2, 100) == True
assert bank.deposit(3, 25) == True

assert bank.balance == [50, 150, 325]

# Invalid account boundaries
bank = Bank([10, 20, 30])

assert bank.deposit(0, 10) == False   # account numbers start at 1
assert bank.withdraw(4, 10) == False   # account out of range

Test	Why
Provided example	Verifies all required operations
Single account	Tests smallest valid bank
Exact balance withdrawal	Ensures equality check works correctly
Invalid source account	Verifies sender validation
Invalid destination account	Verifies receiver validation
Transfer entire balance	Confirms zero balance is allowed
Zero transaction amounts	Tests edge case with zero money
Very large values	Ensures large integers are handled safely
Multiple sequential operations	Verifies state consistency
Invalid account boundaries	Tests lower and upper bound validation

Edge Cases

Invalid Account Numbers

One of the easiest mistakes is forgetting that accounts are numbered from 1 to n, while arrays use indices from 0 to n - 1.

For example, account 0 and account n + 1 are invalid even though they may accidentally map to array positions in a buggy implementation.

The solution avoids this issue by validating every account before performing any operation.

Insufficient Funds

A transfer or withdrawal must fail if the account balance is smaller than the requested amount.

This is especially important because partial updates would corrupt the bank state. For example, subtracting money before validation could produce negative balances.

The implementation checks balance sufficiency first and only updates balances after validation succeeds.

Large Monetary Values

Balances and transaction amounts can be as large as 10^12.

Using a 32-bit integer type would overflow in many languages. The Go implementation explicitly uses int64, while Python automatically supports arbitrary-size integers.

This guarantees correctness even for the largest valid inputs.