Watch the video solution for Account Balance, a medium level problem involving Database. This walkthrough by Everyday Data Science has 4,574 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Correlated Subquery | O(n^2) | O(1) | When window functions are unavailable or for understanding the baseline cumulative logic |
| Window Function Running Sum | O(n log n) | O(n) | Best choice for SQL databases that support window functions like MySQL, PostgreSQL, or SQL Server |