LeetCode 1831 - Maximum Transaction Each Day

The problem gives us a table named Transactions where each row represents a financial transaction. Every transaction has a unique transactionid, a timestamp stored in the day column, and an integer amount.

leetcodemediumdatabase

LeetCode Problem 1831

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem gives us a table named Transactions where each row represents a financial transaction. Every transaction has a unique transaction_id, a timestamp stored in the day column, and an integer amount.

The goal is to find the transaction IDs whose amount is the highest for their respective calendar day. The important detail is that the day column includes both the date and time, but the comparison must be done only by calendar date. For example, 2021-04-29 13:28:30 and 2021-04-29 23:39:28 belong to the same day, 2021-04-29.

If multiple transactions on the same day share the maximum amount, all of them must be included in the result. After collecting all qualifying transaction IDs, the final output must be sorted by transaction_id in ascending order.

The input table can contain multiple transactions per day, single transactions for a day, or ties for the maximum amount. Since transaction IDs are unique, duplicates in the output are never possible.

A naive implementation could make mistakes in several places. One common issue is grouping by the full datetime instead of extracting the date portion, which would incorrectly treat transactions occurring at different times on the same day as separate groups. Another issue is failing to include ties, returning only one transaction even when multiple transactions share the same maximum amount for the day.

The follow up asks whether the problem can be solved without using the MAX() aggregation function. This hints that alternative SQL patterns, such as self joins or window functions, are also valid ways to solve the problem.

Approaches

Brute Force Approach

The brute force approach checks every transaction against every other transaction from the same day.

For each transaction:

  1. Extract its calendar date.
  2. Scan the entire table again.
  3. Find the largest amount for that same date.
  4. If the current transaction's amount equals that maximum, include its ID.

This works because every transaction independently verifies whether it is the largest transaction for its day. However, it is inefficient because every row potentially compares itself with all other rows.

If there are n transactions, the nested scanning produces O(n²) time complexity.

Optimal Approach

The key insight is that the problem naturally breaks into two steps:

  1. Compute the maximum transaction amount for each calendar day.
  2. Retrieve all transactions whose amount matches that daily maximum.

SQL aggregation is ideal for this type of grouped computation. We can first group transactions by date and calculate the maximum amount for each group. Then we join this result back with the original table to find all matching rows.

This avoids repeated rescanning of the table and allows the database engine to optimize grouping and joins efficiently.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compares every transaction with all others from the same day
Optimal O(n log n) typically O(k) Uses grouping and joining, where k is the number of distinct days

Algorithm Walkthrough

  1. Extract the calendar date from the day column.

The day column contains both date and time information, but the problem groups transactions only by date. We therefore use DATE(day) to isolate the date portion. 2. Group transactions by calendar date.

For every distinct date, collect all transactions belonging to that day. 3. Compute the maximum amount for each day.

Using MAX(amount), determine the largest transaction amount within each date group. 4. Join the grouped result back to the original table.

After identifying the maximum amount for each date, compare every original transaction against its day's maximum value. 5. Keep only matching transactions.

If a transaction's amount equals the computed maximum for that day, include its transaction_id. 6. Sort the result.

Order the final output by transaction_id in ascending order, as required by the problem statement.

Why it works

The grouped subquery guarantees that every calendar day is associated with exactly one maximum amount. By joining this information back to the original table and selecting transactions whose amount matches the maximum, we ensure that every qualifying transaction is included, including ties. Since every transaction is checked against the correct daily maximum, the result is complete and correct.

Python Solution

Although this is a database problem, LeetCode database solutions are written in SQL. The following query is the correct submission.

# This problem is solved using SQL, not Python.

SELECT t.transaction_id
FROM Transactions t
JOIN (
    SELECT DATE(day) AS transaction_day,
           MAX(amount) AS max_amount
    FROM Transactions
    GROUP BY DATE(day)
) daily_max
ON DATE(t.day) = daily_max.transaction_day
AND t.amount = daily_max.max_amount
ORDER BY t.transaction_id;

The solution starts by creating a derived table named daily_max. This subquery groups transactions by their calendar date and computes the maximum amount for each day.

The outer query joins the original Transactions table with this grouped result. The join condition ensures two things:

  1. The transaction belongs to the same calendar day.
  2. The transaction amount equals that day's maximum amount.

Any transaction satisfying both conditions is part of the final answer.

Finally, the result is ordered by transaction_id in ascending order.

Go Solution

LeetCode database problems do not require Go code submissions because the execution environment expects SQL queries. However, the equivalent SQL solution is shown below.

// SQL solution for the database problem

SELECT t.transaction_id
FROM Transactions t
JOIN (
    SELECT DATE(day) AS transaction_day,
           MAX(amount) AS max_amount
    FROM Transactions
    GROUP BY DATE(day)
) daily_max
ON DATE(t.day) = daily_max.transaction_day
AND t.amount = daily_max.max_amount
ORDER BY t.transaction_id;

Unlike standard algorithmic problems, there is no Go runtime implementation here because the platform executes SQL directly against the provided database tables. The logic remains identical regardless of language bindings.

Worked Examples

Example 1

Input table:

transaction_id day amount
8 2021-04-03 15:57:28 57
9 2021-04-28 08:47:25 21
1 2021-04-29 13:28:30 58
5 2021-04-28 16:39:59 40
6 2021-04-29 23:39:28 58

Step 1: Group by calendar date

Date Transactions
2021-04-03 (8, 57)
2021-04-28 (9, 21), (5, 40)
2021-04-29 (1, 58), (6, 58)

Step 2: Compute daily maximums

Date Maximum Amount
2021-04-03 57
2021-04-28 40
2021-04-29 58

Step 3: Match transactions with daily maximums

transaction_id amount Daily Maximum Included?
8 57 57 Yes
9 21 40 No
1 58 58 Yes
5 40 40 Yes
6 58 58 Yes

Final sorted result

transaction_id
1
5
6
8

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) typically Grouping and joining operations dominate
Space O(k) Stores grouped maximums for k distinct dates

The exact runtime depends on the database engine and indexing strategy. Most SQL engines implement grouping using sorting or hashing. The grouped subquery processes all rows once, and the join operation efficiently matches rows against computed maximums.

The auxiliary space depends on the number of distinct calendar days because the grouped result stores one maximum value per day.

Test Cases

# Example case with tie on one day
# Expected output: [1, 5, 6, 8]

# Single transaction day
# Input:
# (10, "2022-01-01 10:00:00", 100)
# Expected output: [10]

# Multiple days with unique maximums
# Day 1: max = 50
# Day 2: max = 70
# Expected output IDs correspond to those maximums

# Multiple ties on same day
# Transactions:
# (1, ..., 100)
# (2, ..., 100)
# (3, ..., 50)
# Expected output: [1, 2]

# All transactions same amount
# Every transaction should be returned

# Different timestamps on same date
# Ensures grouping uses DATE(day) rather than full datetime

# Large number of rows
# Ensures grouping and joining scale correctly

Test Summary

Test Why
Example with ties Verifies standard behavior and tie handling
Single transaction day Ensures isolated days are handled correctly
Unique maximums Confirms correct maximum selection
Multiple equal maximums Ensures all tied rows are returned
All same amount Verifies every row can qualify
Different timestamps same day Confirms correct date extraction
Large dataset Validates scalability

Edge Cases

Multiple transactions sharing the maximum amount

One of the most important edge cases occurs when several transactions on the same day have exactly the same maximum amount. A flawed implementation might accidentally return only one transaction by using LIMIT 1 or another restrictive technique.

This solution handles the situation correctly because the join condition checks equality with the daily maximum. Every matching transaction is included automatically.

Only one transaction on a day

A day may contain only a single transaction. In that case, that transaction is trivially the maximum for the day and must appear in the result.

The grouping logic naturally handles this because the maximum of a single-element group is simply that element itself.

Different timestamps on the same date

Transactions can occur at different times during the same day. If an implementation groups by the full datetime value instead of the extracted date, each timestamp would incorrectly become its own group.

Using DATE(day) ensures that all timestamps belonging to the same calendar day are grouped together correctly.