Skip to main content
Talentd

Account Balance - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase4 min read
Practice this problem

Problem Statement

Table: Transactions

+-------------+------+
| Column Name | Type |
+-------------+------+
| account_id  | int  |
| day         | date |
| type        | ENUM |
| amount      | int  |
+-------------+------+
(account_id, day) is the primary key (combination of columns with unique values) for this table.
Each row contains information about one transaction, including the transaction type, the day it occurred on, and the amount.
type is an ENUM (category) of the type ('Deposit','Withdraw')

 

Write a solution to report the balance of each user after each transaction. You may assume that the balance of each account before any transaction is 0 and that the balance will never be below 0 at any moment.

Return the result table in ascending order by account_id, then by day in case of a tie.

The result format is in the following example.

 

Example 1:

Input: 
Transactions table:
+------------+------------+----------+--------+
| 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   |
+------------+------------+----------+--------+
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       |
+------------+------------+---------+
Explanation: 
Account 1:
- Initial balance is 0.
- 2021-11-07 --> deposit 2000. Balance is 0 + 2000 = 2000.
- 2021-11-09 --> withdraw 1000. Balance is 2000 - 1000 = 1000.
- 2021-11-11 --> deposit 3000. Balance is 1000 + 3000 = 4000.
Account 2:
- Initial balance is 0.
- 2021-12-07 --> deposit 7000. Balance is 0 + 7000 = 7000.
- 2021-12-12 --> withdraw 7000. Balance is 7000 - 7000 = 0.

Approach Overview

Problem Overview: The table stores transactions for different accounts. Each row records the account_id, transaction day, transaction type (Deposit or Withdraw), and amount. You must compute the running balance for each account after every transaction day.

Approach 1: Correlated Subquery (O(n^2) time, O(1) extra space)

A straightforward way is to compute the balance for each row by summing all previous transactions of the same account. For every transaction, run a subquery that filters rows with the same account_id and day less than or equal to the current row. Deposits contribute a positive value while withdrawals subtract from the total using a CASE expression. This works but performs repeated scans of the table, leading to quadratic behavior as the dataset grows. It is mainly useful when window functions are unavailable.

Approach 2: Window Function Running Sum (O(n log n) time, O(n) space)

The efficient solution uses a SQL window function to compute a running balance. Convert each transaction into a signed value using CASE WHEN type = 'Deposit' THEN amount ELSE -amount END. Then apply SUM() with OVER(PARTITION BY account_id ORDER BY day). The partition groups rows by account, while the ordering ensures transactions accumulate chronologically. Each row automatically receives the cumulative sum of all prior rows in that account partition. The database engine performs a single pass after sorting by account and day, which is significantly faster than repeated subqueries.

This pattern is essentially a prefix-sum calculation implemented directly in SQL. Window functions are designed exactly for problems like running totals, ranking, and rolling aggregates. If you work frequently with analytics-style queries in database problems or advanced SQL queries, mastering window functions gives you the cleanest and most performant solution.

Recommended for interviews: The window function approach is the expected answer. It demonstrates strong SQL knowledge and avoids inefficient repeated scans. Mentioning the correlated subquery approach shows you understand the baseline idea of accumulating prior transactions, but the window function solution proves you know how to implement running aggregates efficiently.

Solution

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Correlated SubqueryO(n^2)O(1)When window functions are unavailable or for understanding the baseline cumulative logic
Window Function Running SumO(n log n)O(n)Best choice for SQL databases that support window functions like MySQL, PostgreSQL, or SQL Server

Video Solution

LeetCode Medium 2066 Interview SQL Question with Detailed Explanation • Everyday Data Science • 4,574 views views

Frequently Asked Questions

Is Account Balance easy or hard?
Account Balance is rated Medium because it requires familiarity with SQL window functions and cumulative calculations. Developers comfortable with analytic SQL queries typically solve it quickly, while those unfamiliar with window functions may struggle.
Account Balance Python/Java solution
This problem is a database query challenge, so the expected solution is written in SQL (commonly MySQL). The core idea is computing a running sum using SUM() OVER with a CASE expression that converts transaction types into signed amounts.
How to solve Account Balance in O(n)?
Pure O(n) is difficult in SQL because databases typically sort rows when evaluating ordered window functions. The closest practical solution uses SUM() OVER with PARTITION BY and ORDER BY, which runs in O(n log n) due to sorting but processes the cumulative balance in a single pass afterward.
What is the best approach for Account Balance?
The best approach uses a SQL window function with SUM() OVER(PARTITION BY account_id ORDER BY day). Each transaction amount is converted to a signed value using CASE (positive for deposits, negative for withdrawals). The window function computes a running total for every account efficiently in a single query.
Is Account Balance asked at Google/Amazon/Meta?
Running total and cumulative sum problems appear frequently in SQL interviews at companies like Amazon, Meta, and fintech firms. Variations often involve transaction histories, balance tracking, or rolling aggregates using window functions.
What data structure is used in Account Balance?
The solution relies on SQL window functions rather than traditional data structures. Conceptually it behaves like a prefix sum over ordered transactions within each account partition.
What is the time complexity of Account Balance?
The optimal window function solution runs in O(n log n) time due to sorting by account_id and day within each partition. After sorting, the cumulative SUM calculation is linear. Space complexity is O(n) for the intermediate query result.

Ready to solve this problem?

Practice Account Balance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary