LeetCode 2986 - Find Third Transaction

The problem gives us a Transactions table that stores three pieces of information for every transaction: - userid, which identifies the user - spend, which represents the transaction amount - transactiondate, which represents when the transaction occurred The pair (userid…

leetcodemediumdatabase

LeetCode Problem 2986

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem gives us a Transactions table that stores three pieces of information for every transaction:

  • user_id, which identifies the user
  • spend, which represents the transaction amount
  • transaction_date, which represents when the transaction occurred

The pair (user_id, transaction_date) is guaranteed to be unique, which means a user cannot have two transactions at the exact same timestamp.

We need to identify the third transaction for every user, but only under a specific condition. The amount spent on the third transaction must be strictly greater than the amounts spent on both of the previous two transactions.

To solve this correctly, transactions must first be ordered chronologically for each user. The phrase "third transaction" refers to the third transaction in time order, not the third row in the table.

For every user:

  • Sort their transactions by transaction_date
  • Find the third transaction, if it exists
  • Compare its spend value with the spend values of the first and second transactions
  • Include the user in the result only if the third transaction amount is greater than both previous amounts

The output should contain:

  • user_id
  • third_transaction_spend
  • third_transaction_date

The result must be ordered by user_id in ascending order.

This is fundamentally a ranking and comparison problem over ordered rows inside each user partition. Since we need to access previous rows relative to the current row, SQL window functions are the natural tool for the job.

An important observation is that we only care about the third transaction. We do not need to evaluate fourth, fifth, or later transactions.

Several edge cases are important:

  • A user with fewer than three transactions should not appear in the result.
  • If the third transaction spend is equal to either of the previous spends, it should not qualify because the condition requires strictly greater values.
  • Transactions may not be stored in chronological order in the table, so explicit ordering by transaction_date is necessary.
  • Different users must be processed independently.

Approaches

Brute Force Approach

A brute force solution would process each user independently by first collecting all of their transactions, sorting them chronologically, and then checking the third transaction manually.

The algorithm would work like this:

  1. Group all rows by user_id
  2. Sort each user's transactions by transaction_date
  3. If the user has at least three transactions:
  • Extract the first, second, and third transactions
  • Compare the third spend value against the first two
  1. Add qualifying users to the result

This approach is correct because it directly follows the problem definition. However, it becomes inefficient when implemented outside SQL optimization mechanisms because it requires explicit grouping and sorting logic.

In SQL, manually simulating previous-row access using self joins or correlated subqueries would also be more verbose and less efficient.

Optimal Approach

The key insight is that SQL window functions are designed specifically for problems involving ordered rows within partitions.

We can use:

  • ROW_NUMBER() to determine the transaction order for each user
  • LAG() to access the previous two transaction amounts

The process becomes straightforward:

  1. Partition transactions by user_id
  2. Order them by transaction_date
  3. Assign row numbers
  4. Retrieve the two previous spend values
  5. Filter only rows where:
  • row number equals 3
  • current spend is greater than both previous spends

This avoids complicated joins and keeps the solution clean and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Requires grouping and sorting transactions manually
Optimal O(n log n) O(n) Uses window functions for efficient ordered row access

Algorithm Walkthrough

  1. Start by partitioning the table by user_id.

Each user's transaction history must be processed independently. Partitioning ensures that rankings and previous-row calculations do not mix transactions from different users. 2. Order transactions chronologically within each user partition.

The problem defines transaction order using transaction_date, so every user's transactions must be sorted by time ascending. 3. Assign a sequential row number using ROW_NUMBER().

This allows us to identify which transaction is the first, second, third, and so on for every user. 4. Use LAG(spend, 1) to retrieve the spend value of the immediately previous transaction.

This gives access to the second transaction amount when evaluating the third transaction. 5. Use LAG(spend, 2) to retrieve the spend value from two transactions earlier.

This gives access to the first transaction amount when evaluating the third transaction. 6. Filter rows where the row number equals 3.

The problem only asks about the third transaction, so all other rows can be ignored. 7. Check whether the current spend is greater than both previous spend values.

The row qualifies only if:

current_spend > previous_spend_1
AND current_spend > previous_spend_2
  1. Return the required columns ordered by user_id.

Why it works

The correctness comes from the fact that window functions preserve row-level information while still allowing access to neighboring rows inside an ordered partition.

ROW_NUMBER() guarantees that we identify the actual third chronological transaction for each user. LAG() guarantees that we compare against the exact two preceding transactions. Since every condition directly matches the problem statement, the query produces the correct result.

Python Solution

Although this is a database problem, LeetCode database problems are solved using SQL. The following is the correct SQL solution formatted inside a Python block as requested.

SELECT
    user_id,
    spend AS third_transaction_spend,
    transaction_date AS third_transaction_date
FROM (
    SELECT
        user_id,
        spend,
        transaction_date,
        ROW_NUMBER() OVER (
            PARTITION BY user_id
            ORDER BY transaction_date
        ) AS transaction_rank,
        LAG(spend, 1) OVER (
            PARTITION BY user_id
            ORDER BY transaction_date
        ) AS prev_spend_1,
        LAG(spend, 2) OVER (
            PARTITION BY user_id
            ORDER BY transaction_date
        ) AS prev_spend_2
    FROM Transactions
) ranked_transactions
WHERE transaction_rank = 3
    AND spend > prev_spend_1
    AND spend > prev_spend_2
ORDER BY user_id;

The query begins by creating a derived table named ranked_transactions.

Inside this derived table:

  • ROW_NUMBER() assigns chronological positions to each transaction within a user.
  • LAG(spend, 1) retrieves the immediately previous transaction amount.
  • LAG(spend, 2) retrieves the transaction amount two positions earlier.

Once this information is available, the outer query filters only the third transaction for each user.

The final condition ensures that the third transaction spend is strictly larger than both previous spends.

Finally, the output is sorted by user_id in ascending order as required.

Go Solution

LeetCode database problems are language independent because the submission is SQL. The same SQL solution is shown below inside a Go code block for consistency with the requested format.

SELECT
    user_id,
    spend AS third_transaction_spend,
    transaction_date AS third_transaction_date
FROM (
    SELECT
        user_id,
        spend,
        transaction_date,
        ROW_NUMBER() OVER (
            PARTITION BY user_id
            ORDER BY transaction_date
        ) AS transaction_rank,
        LAG(spend, 1) OVER (
            PARTITION BY user_id
            ORDER BY transaction_date
        ) AS prev_spend_1,
        LAG(spend, 2) OVER (
            PARTITION BY user_id
            ORDER BY transaction_date
        ) AS prev_spend_2
    FROM Transactions
) ranked_transactions
WHERE transaction_rank = 3
    AND spend > prev_spend_1
    AND spend > prev_spend_2
ORDER BY user_id;

There are no Go-specific implementation differences because this problem is solved entirely in SQL. The database engine handles ordering, partitioning, and window function execution internally.

Worked Examples

Example 1

Input table:

user_id spend transaction_date
1 65.56 2023-11-18 13:49:42
1 96.0 2023-11-30 02:47:26
1 7.44 2023-11-02 12:15:23
1 49.78 2023-11-12 00:13:46
2 40.89 2023-11-21 04:39:15
2 100.44 2023-11-20 07:39:34
3 37.33 2023-11-03 06:22:02
3 13.89 2023-11-11 16:00:14
3 7.0 2023-11-29 22:32:36

User 1 Processing

After sorting by date:

Rank Spend Date
1 7.44 2023-11-02
2 49.78 2023-11-12
3 65.56 2023-11-18
4 96.00 2023-11-30

For the third transaction:

  • Current spend = 65.56
  • Previous spend 1 = 49.78
  • Previous spend 2 = 7.44

Condition check:

Comparison Result
65.56 > 49.78 True
65.56 > 7.44 True

User 1 qualifies.

User 2 Processing

After sorting by date:

Rank Spend Date
1 100.44 2023-11-20
2 40.89 2023-11-21

User 2 has only two transactions, so there is no third transaction.

User 2 does not qualify.

User 3 Processing

After sorting by date:

Rank Spend Date
1 37.33 2023-11-03
2 13.89 2023-11-11
3 7.00 2023-11-29

For the third transaction:

  • Current spend = 7.00
  • Previous spend 1 = 13.89
  • Previous spend 2 = 37.33

Condition check:

Comparison Result
7.00 > 13.89 False
7.00 > 37.33 False

User 3 does not qualify.

Final output:

user_id third_transaction_spend third_transaction_date
1 65.56 2023-11-18 13:49:42

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Window functions require sorting transactions by user and date
Space O(n) Database engine stores intermediate window function results

The dominant cost comes from sorting transactions inside each user partition. Window functions are typically implemented on top of sorted data, so the runtime is effectively determined by the sorting phase.

The space complexity comes from temporary storage used internally by the database engine during window function evaluation.

Test Cases

# Example 1 from the problem statement
# User 1 qualifies, user 2 lacks 3 transactions, user 3 fails comparison
assert solution == [
    [1, 65.56, "2023-11-18 13:49:42"]
]

# Exactly three transactions, valid increasing third transaction
assert solution == [
    [1, 30.0, "2023-01-03 00:00:00"]
]

# Exactly three transactions, third transaction equal to previous
# Should fail because comparison must be strictly greater
assert solution == []

# User with fewer than three transactions
assert solution == []

# Multiple users with mixed validity
assert solution == [
    [2, 50.0, "2023-05-03 00:00:00"]
]

# Transactions inserted out of chronological order
# Sorting by transaction_date must still work correctly
assert solution == [
    [1, 100.0, "2023-01-03 00:00:00"]
]

# Third transaction smaller than one previous transaction
assert solution == []

# Third transaction greater than first but not second
assert solution == []

# Negative and decimal spend values
assert solution == [
    [1, 0.5, "2023-01-03 00:00:00"]
]

# Multiple qualifying users
assert solution == [
    [1, 30.0, "2023-01-03 00:00:00"],
    [2, 100.0, "2023-02-03 00:00:00"]
]
Test Why
Problem example Validates the official scenario
Exactly three valid transactions Tests minimum qualifying case
Equal transaction values Verifies strict comparison
Fewer than three transactions Ensures insufficient users are excluded
Multiple mixed users Confirms independent partition handling
Unsorted input rows Verifies chronological ordering logic
Third transaction smaller Tests rejection logic
Third transaction partially larger Ensures both comparisons are required
Decimal and negative values Confirms numeric comparison correctness
Multiple valid users Ensures multiple outputs are handled correctly

Edge Cases

One important edge case occurs when a user has fewer than three transactions. A naive implementation might attempt to compare nonexistent previous transactions or accidentally include incomplete transaction histories. The implementation handles this naturally because only rows with ROW_NUMBER() = 3 are considered. Users with fewer than three transactions never generate such a row.

Another important case is when the third transaction spend equals one of the previous spends. The problem requires the third transaction to be strictly greater than both earlier transactions. Using > instead of >= ensures that equal values are rejected correctly.

A subtle edge case involves transactions appearing in random insertion order inside the table. Without explicitly sorting by transaction_date, the wrong transaction could be labeled as the third transaction. The implementation avoids this issue by using ORDER BY transaction_date inside every window function.

A final edge case involves users with more than three transactions. The problem only asks whether the third transaction satisfies the condition. Later transactions should not affect the result. The query handles this correctly by filtering specifically for transaction_rank = 3.