Consecutive Transactions with Increasing Amounts

Hard

Asked by:

4 views

Topics:

ArraysDynamic Programming

Table: Transactions

+----------------+---------+
| Column Name    | Type    |
+----------------+---------+
| id             | int     |
| transaction_date | date    |
| amount         | int     |
+----------------+---------+
id is the primary key for this table.
Each row contains information about one transaction.

Write an SQL query to find the IDs of the users who made consecutive transactions on consecutive days and at least once have an amount greater than 1000.

Return the result table ordered by user_id in ascending order.

The result format is in the following example.

Transactions table:
+------+------------------+--------+
| id   | transaction_date | amount |
+------+------------------+--------+
| 1    | 2023-12-01       | 950    |
| 2    | 2023-12-02       | 1200   |
| 3    | 2023-12-03       | 1300   |
| 4    | 2023-12-04       | 1400   |
| 5    | 2023-12-05       | 1500   |
+------+------------------+--------+

Result table:
+---------+
| user_id |
+---------+
| 1       |
+---------+
For the sample data, the user with ID 1 made transactions on consecutive days (2023-12-01, 2023-12-02, 2023-12-03, 2023-12-04, and 2023-12-05), and at least one of the transactions was greater than $1000. So, the user ID 1 is included in the result table.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values for the transaction amounts in the input array?
Can the input array `transactions` be empty or null?
If there is no increasing consecutive subsequence, what value should I return?
Does "consecutive" mean the elements need to be adjacent in the original array, forming a subarray, or can they be a subsequence that maintains the original order but skips elements?
Is the input array read-only, or can I modify it in place?

Brute Force Solution

Approach

The brute force approach for this problem is like trying every possible combination of transactions. We check each combination to see if the amounts are increasing and if the transactions are consecutive.

Here's how the algorithm would work step-by-step:

Start by considering the first transaction alone. Is that a valid sequence?
Then, consider the first two transactions. Are they consecutive and is the second transaction amount bigger than the first?
Continue this, considering the first three, then four, and so on, checking for consecutiveness and increasing amounts each time.
Now, start at the second transaction and repeat the same process: Check just the second, then the second and third, then the second, third, and fourth, etc.
Keep doing this, starting from each transaction in the list and checking all the possible sequences that follow.
Each time you find a sequence that is consecutive and has increasing amounts, remember it.
After you've tried every possible starting point and sequence length, look at all the valid sequences you found.
The longest valid sequence you found is the answer.

Code Implementation

def find_longest_increasing_transactions(transactions):
    max_length = 0

    for start_index in range(len(transactions)):
        current_length = 1
        current_amount = transactions[start_index]
        current_index = start_index

        # Attempt to extend the sequence from the current starting point
        while True:
            next_index = -1
            for subsequent_index in range(current_index + 1, len(transactions)):
                # Find the next transaction that is both later and has a larger amount
                if transactions[subsequent_index] > current_amount:
                    next_index = subsequent_index
                    break

            if next_index == -1:
                break

            # Update state based on the next transaction
            current_length += 1
            current_amount = transactions[next_index]
            current_index = next_index

        # Keep track of the longest sequence found so far
        if current_length > max_length:
            max_length = current_length

    # Brute force search completed, so return the maximum length
    return max_length

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n transactions as a potential starting point for a sequence. The inner loop, for each starting point, iterates through the remaining transactions to build and check potential consecutive sequences. In the worst case, for each of the n starting positions, we might examine close to n subsequent transactions. Therefore, the total number of operations approximates n * n/2, leading to a time complexity of O(n²).

Space Complexity

O(N) – The provided brute force algorithm keeps track of valid sequences found. In the worst-case scenario, it might need to store all possible consecutive increasing sequences. Since there can be at most N such sequences (where N is the number of transactions), it would store a list of sequences of size N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

We want to find the longest sequence of transactions where each transaction is bigger than the one before it. The trick is to keep track of the best sequence we've seen so far as we go through the transactions, and restart the sequence whenever we find a smaller transaction.

Here's how the algorithm would work step-by-step:

Start by assuming the first transaction is the beginning of our current potential sequence.
Look at the next transaction. If it's bigger than the last one in our current sequence, add it to the sequence.
If the next transaction is smaller than or equal to the last one in our current sequence, it means we need to start a new sequence from this transaction.
As we go through all the transactions, compare the length of the current sequence with the length of the best sequence we've found so far. Update the best sequence if the current one is longer.
Once we've gone through all the transactions, the best sequence we've found is the longest sequence of consecutive transactions with increasing amounts.

Code Implementation

def find_longest_increasing_transactions(transactions):
    longest_sequence = []
    current_sequence = []

    for transaction_amount in transactions:
        # Check if the current transaction extends the existing sequence
        if not current_sequence or transaction_amount > current_sequence[-1]:
            current_sequence.append(transaction_amount)

        else:
            # Start a new sequence if the current transaction is not greater
            current_sequence = [transaction_amount]

        # Update the longest sequence found so far
        if len(current_sequence) > len(longest_sequence):
            longest_sequence = current_sequence[:]

    return longest_sequence

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the transaction amounts array once. For each transaction, it performs a constant-time comparison with the previous transaction to determine whether to extend the current increasing sequence or start a new one. The updates to the best sequence also take constant time. Therefore, the time complexity is directly proportional to the number of transactions, n, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only stores the length of the current sequence and the length of the best sequence found so far, both of which are scalar variables. These variables take up a fixed amount of memory regardless of the input size N, where N is the number of transactions. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0, as there are no transactions to form a sequence.
Array with a single transaction	Return 1, as a single transaction always forms a sequence of length 1.
Array with all transactions having the same amount	Return 1, since no consecutive transactions are strictly increasing.
Array with transactions in strictly decreasing order	Return 1, because the longest increasing consecutive subsequence will always be of length 1.
Array with very large transaction amounts that could lead to integer overflow if summed or compared incorrectly.	Ensure that the comparison and length calculation do not result in integer overflow by using appropriate data types or range checks.
Array containing a mix of positive, negative, and zero transaction amounts	The solution should correctly handle negative and zero amounts as valid transaction values.
Array with maximum allowed size by constraints	The solution's space and time complexity should be efficient enough to handle the maximum input size without exceeding memory or time limits.
Presence of duplicate transaction amounts within the input array.	The algorithm should correctly identify increasing sequences even when duplicate amounts exist at non-consecutive indices.

Empty input array

How to Handle:

Return 0, as there are no transactions to form a sequence.

Array with a single transaction

How to Handle:

Return 1, as a single transaction always forms a sequence of length 1.

Array with all transactions having the same amount

How to Handle:

Return 1, since no consecutive transactions are strictly increasing.

Array with transactions in strictly decreasing order

How to Handle:

Return 1, because the longest increasing consecutive subsequence will always be of length 1.

Array with very large transaction amounts that could lead to integer overflow if summed or compared incorrectly.

How to Handle:

Ensure that the comparison and length calculation do not result in integer overflow by using appropriate data types or range checks.

Array containing a mix of positive, negative, and zero transaction amounts

How to Handle:

The solution should correctly handle negative and zero amounts as valid transaction values.

Array with maximum allowed size by constraints

How to Handle:

The solution's space and time complexity should be efficient enough to handle the maximum input size without exceeding memory or time limits.

Presence of duplicate transaction amounts within the input array.

How to Handle:

The algorithm should correctly identify increasing sequences even when duplicate amounts exist at non-consecutive indices.