Problem

Table: Transactions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

+-------------+------+
| Column Name | Type |
+-------------+------+
| account_id  | int  |
| day         | date |
| type        | ENUM |
| amount      | int  |
+-------------+------+
(account_id, day) is the primary key 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 of the type ('Deposit','Withdraw')

Write an SQL query 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 query result format is in the following example.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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.

Solution

Method 1 – Using Window Functions

Intuition

The key idea is to compute the running balance for each account after every transaction. We can use SQL window functions to calculate a cumulative sum, adding for deposits and subtracting for withdrawals, ordered by transaction date.

Approach

  1. For each transaction, assign a signed amount: positive for ‘Deposit’, negative for ‘Withdraw’.
  2. Use the SUM() window function with PARTITION BY account_id and ORDER BY day to compute the running total (balance) after each transaction.
  3. Select account_id, day, and the computed balance.
  4. Order the results by account_id and day as required.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

Complexity:

  • ⏰ Time complexity: O(n log n) (due to ordering within each partition)
  • 🧺 Space complexity: O(n) (for storing intermediate results per account)