Problem

Table: Transactions

1
2
3
4
5
6
7
8
9

+----------------+----------+
| Column Name    | Type     |
+----------------+----------+
| transaction_id | int      |
| day            | datetime |
| amount         | int      |
+----------------+----------+
transaction_id is the column with unique values for this table.
Each row contains information about one transaction.

Write a solution to report the IDs of the transactions with the maximum amount on their respective day. If in one day there are multiple such transactions, return all of them.

Return the result table ordered by transaction_id in ascending order.

The 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

Input: 
Transactions table:
+----------------+--------------------+--------+
| transaction_id | day                | amount |
+----------------+--------------------+--------+
| 8              | 2021-4-3 15:57:28  | 57     |
| 9              | 2021-4-28 08:47:25 | 21     |
| 1              | 2021-4-29 13:28:30 | 58     |
| 5              | 2021-4-28 16:39:59 | 40     |
| 6              | 2021-4-29 23:39:28 | 58     |
+----------------+--------------------+--------+
Output: 
+----------------+
| transaction_id |
+----------------+
| 1              |
| 5              |
| 6              |
| 8              |
+----------------+
Explanation: 
"2021-4-3"  --> We have one transaction with ID 8, so we add 8 to the result table.
"2021-4-28" --> We have two transactions with IDs 5 and 9. The transaction with ID 5 has an amount of 40, while the transaction with ID 9 has an amount of 21. We only include the transaction with ID 5 as it has the maximum amount this day.
"2021-4-29" --> We have two transactions with IDs 1 and 6. Both transactions have the same amount of 58, so we include both in the result table.
We order the result table by transaction_id after collecting these IDs.
**Follow up:** Could you solve it without using the `MAX()` function?

Solution

Method 1 – Window Function (SQL), Group By (MySQL/PostgreSQL), Pandas

Intuition

To find transactions with the maximum amount for each day, we need to compare each transaction’s amount to the maximum amount for its day. Window functions or group by queries can efficiently achieve this.

Approach

  1. For each day, find the maximum transaction amount.
  2. Select all transaction IDs where the amount equals the maximum for that day.
  3. Return all such transaction IDs (multiple per day if tied).

Complexity

  • ⏰ Time complexity: O(n) — Each row is scanned once.
  • 🧺 Space complexity: O(n) — For intermediate results.

Code

1
2
3
4
5
6
7

SELECT transaction_id
FROM Transactions
WHERE (day, amount) IN (
    SELECT day, MAX(amount)
    FROM Transactions
    GROUP BY day
);
1
2
3
4
5
6
7

SELECT transaction_id
FROM Transactions
WHERE (day, amount) IN (
    SELECT day, MAX(amount)
    FROM Transactions
    GROUP BY day
);
1
2
3

def max_transaction_each_day(transactions: 'pd.DataFrame') -> 'pd.DataFrame':
    idx = transactions.groupby('day')['amount'].transform('max') == transactions['amount']
    return transactions.loc[idx, ['transaction_id']]