Watch the video solution for Find Third Transaction, a medium level problem involving Database. This walkthrough by Everyday Data Science has 1,166 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Transactions
+------------------+----------+ | Column Name | Type | +------------------+----------+ | user_id | int | | spend | decimal | | transaction_date | datetime | +------------------+----------+ (user_id, transaction_date) is column of unique values for this table. This table contains user_id, spend, and transaction_date.
Write a solution to find the third transaction (if they have at least three transactions) of every user, where the spending on the preceding two transactions is lower than the spending on the third transaction.
Return the result table by user_id in ascending order.
The result format is in the following example.
Example 1:
Input: Transactions 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 | +---------+--------+---------------------+ Output +---------+-------------------------+------------------------+ | user_id | third_transaction_spend | third_transaction_date | +---------+-------------------------+------------------------+ | 1 | 65.56 | 2023-11-18 13:49:42 | +---------+-------------------------+------------------------+ Explanation - For user_id 1, their third transaction occurred on 2023-11-18 at 13:49:42 with an amount of $65.56, surpassing the expenditures of the previous two transactions which were $7.44 on 2023-11-02 at 12:15:23 and $49.78 on 2023-11-12 at 00:13:46. Thus, this third transaction will be included in the output table. - user_id 2 only has a total of 2 transactions, so there isn't a third transaction to consider. - For user_id 3, the amount of $7.0 for their third transaction is less than that of the preceding two transactions, so it won't be included. Output table is ordered by user_id in ascending order.
Problem Overview: The task is to return each user's third transaction based on chronological order. You need to examine a transaction table, order each user's transactions by date, and extract the row that represents the third event in that sequence.
Approach 1: Self Join Counting (O(n²) time, O(1) extra space)
This approach compares each transaction with all other transactions from the same user. For a given row, count how many transactions occurred earlier using a self join on user_id with a condition like t2.transaction_date <= t1.transaction_date. If exactly three transactions exist up to that point, the row represents the third transaction. While this works in plain SQL without analytic functions, the join produces a quadratic comparison pattern and becomes slow on large tables.
Approach 2: Window Function with ROW_NUMBER (O(n log n) time, O(n) space)
The efficient solution uses a SQL window function. Partition the table by user_id and order rows by transaction_date. Apply ROW_NUMBER() to assign a sequential rank to each transaction within the user's history. Once numbered, filter rows where row_number = 3. The database engine sorts transactions per user and computes the ranking in a single pass, which is significantly more efficient than repeated joins.
This pattern is common in SQL interview questions involving ordered events or user activity streams. Window functions like ROW_NUMBER, RANK, and DENSE_RANK are designed exactly for problems where you need the kth record inside a group.
Recommended for interviews: The window function solution is what interviewers expect for modern SQL engines. It clearly expresses the intent: rank transactions per user and pick the third one. Understanding the self-join counting method shows you grasp the underlying logic, but using ROW_NUMBER() demonstrates fluency with analytic queries and scalable database operations. Many production analytics pipelines rely on similar patterns built with window functions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self Join Transaction Counting | O(n²) | O(1) | When window functions are unavailable or when demonstrating the underlying logic |
| Window Function with ROW_NUMBER | O(n log n) | O(n) | Best general solution for modern SQL databases and interview settings |
