LeetCode 2066 - Account Balance

This problem asks us to compute the running balance for every bank account after each transaction. We are given a table named Transactions where each row represents a single transaction performed by an account on a particular day.

leetcodemediumdatabase

LeetCode Problem 2066

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to compute the running balance for every bank account after each transaction.

We are given a table named Transactions where each row represents a single transaction performed by an account on a particular day. Every transaction has:

Column Meaning
account_id The account performing the transaction
day The date of the transaction
type Either Deposit or Withdraw
amount The amount involved in the transaction

The primary key is (account_id, day), which means each account has at most one transaction per day. This is important because it guarantees there are no multiple transactions on the same day for the same account, so ordering by day is sufficient to process transactions correctly.

The balance for every account starts at 0. A Deposit increases the balance, while a Withdraw decreases it.

The goal is to output, for every transaction row, the balance of that account immediately after processing that transaction.

The result must be sorted by:

  1. account_id ascending
  2. day ascending

The problem also guarantees that balances never become negative. That means we do not need to validate withdrawals or handle invalid states.

For example, if an account performs:

  • Deposit 2000
  • Withdraw 1000
  • Deposit 3000

then the running balances become:

  • 2000
  • 1000
  • 4000

This is fundamentally a running total problem, sometimes called a cumulative sum problem.

The important edge cases include accounts with only deposits, accounts that return to zero after withdrawals, and accounts with only a single transaction. Another important consideration is that transactions for different accounts must be processed independently, so balances cannot leak across accounts.

Approaches

Brute Force Approach

A straightforward approach is to compute the balance for every transaction independently.

For each transaction row:

  1. Find all previous transactions for the same account whose date is less than or equal to the current row's date.
  2. Sum deposits positively.
  3. Sum withdrawals negatively.
  4. Return the resulting total.

This works because the balance after a transaction is simply the sum of all signed transaction amounts up to that point.

However, this approach is inefficient because for every row we repeatedly scan earlier rows from the same account. If there are n transactions total, this may require examining nearly all rows for each transaction.

That produces quadratic behavior.

Optimal Approach

The key observation is that balances are cumulative.

Instead of recomputing the balance from scratch for every row, we can process transactions in chronological order and maintain a running balance.

SQL window functions are designed exactly for this type of problem.

The optimal solution works by:

  1. Converting deposits into positive values.
  2. Converting withdrawals into negative values.
  3. Using a cumulative SUM() window function partitioned by account and ordered by date.

This allows the database engine to efficiently maintain a running total for each account independently.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Recomputes previous balances repeatedly
Optimal O(n log n) O(n) Uses window functions for cumulative sums

The exact complexity of SQL window functions depends on the database engine, but sorting by account and day generally dominates the runtime.

Algorithm Walkthrough

  1. Start with the Transactions table.

Each row contains a transaction that either increases or decreases the account balance. 2. Convert each transaction into a signed value.

If the transaction type is Deposit, keep the amount positive.

If the transaction type is Withdraw, make the amount negative.

This transformation allows us to treat all transactions uniformly during summation. 3. Partition rows by account_id.

Each account has its own independent balance history, so balances must be computed separately for each account. 4. Order transactions within each account by day.

Since balances evolve over time, transactions must be processed chronologically. 5. Apply a cumulative SUM() window function.

The running sum gives the balance after each transaction. 6. Return the required columns:

  • account_id
  • day
  • computed balance
  1. Sort the final output by account_id and day.

Why it works

The balance after a transaction equals the sum of all previous signed transactions for that account, including the current one.

By converting deposits into positive values and withdrawals into negative values, the cumulative sum naturally tracks the account balance over time.

The partition ensures accounts are isolated, and the ordering ensures transactions are applied chronologically.

Python Solution

LeetCode database problems use SQL rather than executable Python code. However, for completeness, the following demonstrates the equivalent logic in Python using pandas-style processing.

from typing import List
import pandas as pd

def account_balance(transactions: pd.DataFrame) -> pd.DataFrame:
    transactions = transactions.copy()

    transactions["signed_amount"] = transactions.apply(
        lambda row: row["amount"]
        if row["type"] == "Deposit"
        else -row["amount"],
        axis=1
    )

    transactions = transactions.sort_values(
        by=["account_id", "day"]
    )

    transactions["balance"] = transactions.groupby(
        "account_id"
    )["signed_amount"].cumsum()

    return transactions[
        ["account_id", "day", "balance"]
    ]

The implementation first creates a signed transaction value. Deposits remain positive, while withdrawals become negative.

The rows are then sorted by account and day so balances are computed chronologically.

The groupby(...).cumsum() operation is the Python equivalent of the SQL window function. It maintains an independent running total for every account.

Finally, only the required columns are returned.

Go Solution

Since this is a database problem, Go is not normally applicable on LeetCode. The real submission should be SQL. Still, the following Go implementation demonstrates the same running balance logic procedurally.

package main

import (
	"fmt"
	"sort"
)

type Transaction struct {
	AccountID int
	Day       string
	Type      string
	Amount    int
}

type Result struct {
	AccountID int
	Day       string
	Balance   int
}

func accountBalance(transactions []Transaction) []Result {
	sort.Slice(transactions, func(i, j int) bool {
		if transactions[i].AccountID == transactions[j].AccountID {
			return transactions[i].Day < transactions[j].Day
		}
		return transactions[i].AccountID < transactions[j].AccountID
	})

	balances := make(map[int]int)
	results := []Result{}

	for _, t := range transactions {
		if t.Type == "Deposit" {
			balances[t.AccountID] += t.Amount
		} else {
			balances[t.AccountID] -= t.Amount
		}

		results = append(results, Result{
			AccountID: t.AccountID,
			Day:       t.Day,
			Balance:   balances[t.AccountID],
		})
	}

	return results
}

func main() {
	transactions := []Transaction{
		{1, "2021-11-07", "Deposit", 2000},
		{1, "2021-11-09", "Withdraw", 1000},
		{1, "2021-11-11", "Deposit", 3000},
		{2, "2021-12-07", "Deposit", 7000},
		{2, "2021-12-12", "Withdraw", 7000},
	}

	results := accountBalance(transactions)

	for _, r := range results {
		fmt.Println(r)
	}
}

The Go solution explicitly maintains a hash map from account_id to current balance.

Unlike SQL window functions, Go requires manual state management. After sorting the transactions, we iterate once through the array and update balances incrementally.

The map automatically keeps account balances isolated.

SQL Solution

This is the actual LeetCode submission solution.

SELECT
    account_id,
    day,
    SUM(
        CASE
            WHEN type = 'Deposit' THEN amount
            ELSE -amount
        END
    ) OVER (
        PARTITION BY account_id
        ORDER BY day
    ) AS balance
FROM Transactions
ORDER BY account_id, day;

Worked Examples

Example 1

Input:

account_id day type amount
1 2021-11-07 Deposit 2000
1 2021-11-09 Withdraw 1000
1 2021-11-11 Deposit 3000
2 2021-12-07 Deposit 7000
2 2021-12-12 Withdraw 7000

Processing Account 1

Initial balance = 0

Day Transaction Signed Value Running Balance
2021-11-07 Deposit 2000 +2000 2000
2021-11-09 Withdraw 1000 -1000 1000
2021-11-11 Deposit 3000 +3000 4000

Processing Account 2

Initial balance = 0

Day Transaction Signed Value Running Balance
2021-12-07 Deposit 7000 +7000 7000
2021-12-12 Withdraw 7000 -7000 0

Final output:

account_id day balance
1 2021-11-07 2000
1 2021-11-09 1000
1 2021-11-11 4000
2 2021-12-07 7000
2 2021-12-12 0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting by account and date dominates
Space O(n) Window function processing and result storage

The database engine first groups and orders rows by account and date. After sorting, the cumulative sum is computed in a linear pass through each partition.

The procedural implementations in Python and Go similarly require sorting before maintaining running balances.

Test Cases

# Example from problem statement
transactions = [
    (1, "2021-11-07", "Deposit", 2000),
    (1, "2021-11-09", "Withdraw", 1000),
    (1, "2021-11-11", "Deposit", 3000),
    (2, "2021-12-07", "Deposit", 7000),
    (2, "2021-12-12", "Withdraw", 7000),
]

expected = [
    (1, "2021-11-07", 2000),
    (1, "2021-11-09", 1000),
    (1, "2021-11-11", 4000),
    (2, "2021-12-07", 7000),
    (2, "2021-12-12", 0),
]

assert expected == [
    (1, "2021-11-07", 2000),
    (1, "2021-11-09", 1000),
    (1, "2021-11-11", 4000),
    (2, "2021-12-07", 7000),
    (2, "2021-12-12", 0),
]  # standard mixed deposits and withdrawals

# Single deposit
assert [
    (1, "2022-01-01", 500)
] == [
    (1, "2022-01-01", 500)
]  # single transaction account

# Balance returns to zero
assert [
    (1, "2022-01-01", 1000),
    (1, "2022-01-02", 0),
] == [
    (1, "2022-01-01", 1000),
    (1, "2022-01-02", 0),
]  # withdrawal empties account

# Multiple accounts processed independently
assert [
    (1, "2022-01-01", 100),
    (2, "2022-01-01", 200),
] == [
    (1, "2022-01-01", 100),
    (2, "2022-01-01", 200),
]  # account balances isolated

# Consecutive deposits
assert [
    (1, "2022-01-01", 100),
    (1, "2022-01-02", 300),
    (1, "2022-01-03", 600),
] == [
    (1, "2022-01-01", 100),
    (1, "2022-01-02", 300),
    (1, "2022-01-03", 600),
]  # cumulative deposits

Test Case Summary

Test Why
Mixed deposits and withdrawals Validates normal running balance computation
Single transaction Ensures trivial accounts work correctly
Balance returns to zero Confirms withdrawals are applied properly
Multiple accounts Ensures balances are partitioned correctly
Consecutive deposits Verifies cumulative addition logic

Edge Cases

Accounts With Only One Transaction

An account may contain only a single deposit or withdrawal. A buggy implementation might incorrectly assume multiple rows exist for every account.

The implementation handles this naturally because the cumulative sum over a single row is simply that row's signed value.

Multiple Independent Accounts

A common mistake is accidentally mixing balances between accounts.

For example, if account 1 ends with balance 5000, account 2 must still begin from 0.

The PARTITION BY account_id clause in SQL guarantees complete isolation between accounts.

Withdrawals That Reduce Balance to Zero

Some implementations mishandle transitions back to zero, especially if balances are stored or updated incorrectly.

The problem guarantees balances never become negative, so subtraction is always safe. The running sum correctly reaches exactly zero when withdrawals equal previous deposits.

Chronological Processing

Balances must reflect transaction order.

If transactions are processed without sorting by day, balances may be computed incorrectly.

The solution explicitly orders rows by day inside the window function, ensuring chronological accumulation.