Find Third Transaction - Solution & Explanation

Q: Is Find Third Transaction easy or hard?

The problem is rated Medium because it requires familiarity with SQL analytic functions like ROW_NUMBER and grouping logic. Developers comfortable with window functions usually solve it quickly.

Q: Find Third Transaction Python/Java solution

This is a database problem typically solved using SQL rather than Python or Java. In application code, the equivalent logic would involve grouping transactions by user, sorting them by date, and selecting the third element from each sorted list.

Q: How to solve Find Third Transaction in O(n)?

Pure O(n) solutions are uncommon in SQL because ordering by transaction date requires sorting. The closest practical solution uses ROW_NUMBER() with PARTITION BY and ORDER BY, which most database engines implement with O(n log n) sorting internally.

Q: What is the best approach for Find Third Transaction?

The most efficient solution uses the SQL window function ROW_NUMBER(). Partition transactions by user_id, order them by transaction_date, and select rows where row_number equals 3. This approach runs in O(n log n) due to sorting and clearly expresses the logic in a single query.

Q: Is Find Third Transaction asked at Google/Amazon/Meta?

SQL ranking and event-order queries are common in data engineering and analytics interviews at companies like Amazon, Google, and Meta. Variants such as finding the first, second, or nth event per user frequently appear in SQL interview rounds.

Q: What data structure is used in Find Third Transaction?

The problem relies on SQL window functions rather than traditional data structures. Conceptually, the database groups rows by user_id and assigns ordered rankings using ROW_NUMBER over each partition.

Q: What is the time complexity of Find Third Transaction?

The optimal window function solution runs in O(n log n) time because the database must sort transactions within each user partition. Space complexity is O(n) for maintaining ranking information during query execution.

MediumPremiumFree on FleetCodeDatabase4 min readAsked at: Cisco

Practice this problem

Problem Statement

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.

Approach Overview

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.

Solution

Code

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

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

Video Solution

Leetcode MEDIUM 2986 - Find Third Transaction RANK() WINDOW - Explained by Everyday Data Science • Everyday Data Science • 1,196 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Find Third Transaction easy or hard?

The problem is rated Medium because it requires familiarity with SQL analytic functions like ROW_NUMBER and grouping logic. Developers comfortable with window functions usually solve it quickly.

Find Third Transaction Python/Java solution

This is a database problem typically solved using SQL rather than Python or Java. In application code, the equivalent logic would involve grouping transactions by user, sorting them by date, and selecting the third element from each sorted list.

How to solve Find Third Transaction in O(n)?

Pure O(n) solutions are uncommon in SQL because ordering by transaction date requires sorting. The closest practical solution uses ROW_NUMBER() with PARTITION BY and ORDER BY, which most database engines implement with O(n log n) sorting internally.

What is the best approach for Find Third Transaction?

The most efficient solution uses the SQL window function ROW_NUMBER(). Partition transactions by user_id, order them by transaction_date, and select rows where row_number equals 3. This approach runs in O(n log n) due to sorting and clearly expresses the logic in a single query.

Is Find Third Transaction asked at Google/Amazon/Meta?

SQL ranking and event-order queries are common in data engineering and analytics interviews at companies like Amazon, Google, and Meta. Variants such as finding the first, second, or nth event per user frequently appear in SQL interview rounds.

What data structure is used in Find Third Transaction?

The problem relies on SQL window functions rather than traditional data structures. Conceptually, the database groups rows by user_id and assigns ordered rankings using ROW_NUMBER over each partition.

What is the time complexity of Find Third Transaction?

The optimal window function solution runs in O(n log n) time because the database must sort transactions within each user partition. Space complexity is O(n) for maintaining ranking information during query execution.

Ready to solve this problem?

Practice Find Third Transaction with our built-in code editor and test cases.

Practice on FleetCode

Combine Two Tables

Second Highest Salary

Problem Info

DifficultyMedium

Acceptance53.0%

Approaches1

Reading time4 min

Asked at

Cisco