Find Third Transaction

Medium

Cisco

0 views

Topics:

Arrays

You are given an array of integers prices representing the price of a stock on each day. You are allowed to complete at most three transactions (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Find the maximum profit you can achieve.

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we do not engage in any transactions.

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

Try coding it in LeetCode

Find Third Transaction

Medium

Cisco

0 views

Topics:

Arrays

You are given an array of integers prices representing the price of a stock on each day. You are allowed to complete at most three transactions (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Find the maximum profit you can achieve.

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we do not engage in any transactions.

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

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 range of values for the stock prices in the input array? Could they be negative?
What should I return if the input array is null or empty? Should I return 0?
Is there a limit on the number of days represented in the prices array?
By 'transaction,' do you mean one buy and one sell? And can I only hold one stock at a time?
If there are multiple ways to achieve the maximum profit with three or fewer transactions, do I need to return a specific combination of transactions, or is any combination that yields the maximum profit acceptable?

Brute Force Solution

Approach

The brute force approach to finding a third transaction involves checking all possible combinations of three transactions within the given dataset. We accomplish this by exhaustively comparing every possible triplet to find the one that meets the specified criteria.

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

Start by selecting the first possible transaction from the entire list.
Then, for that first transaction, select every possible second transaction from the remaining transactions that occur after the first.
Next, for each pair of the first and second transactions, select every possible third transaction from the transactions that occur after the second.
For each combination of three transactions, check if they meet all the requirements, such as non-overlapping time periods or specific profit conditions.
If a combination meets the requirements, store it as a potential solution.
After examining every possible combination of three transactions, compare all the stored solutions.
From the stored solutions, identify the best one according to the problem's objective, such as maximizing profit.

Code Implementation

def find_third_transaction_brute_force(transactions): 
    valid_combinations = []
    number_of_transactions = len(transactions)

    for first_transaction_index in range(number_of_transactions):
        first_transaction = transactions[first_transaction_index]

        for second_transaction_index in range(number_of_transactions):
            if second_transaction_index == first_transaction_index:
                continue

            second_transaction = transactions[second_transaction_index]

            # We're looking for the third transaction here
            for third_transaction_index in range(number_of_transactions):
                if third_transaction_index == first_transaction_index or \
                   third_transaction_index == second_transaction_index:
                    continue

                third_transaction = transactions[third_transaction_index]

                # Checking if condition is met.
                # Example condition based on indices:
                if first_transaction_index < second_transaction_index < third_transaction_index:
                    valid_combinations.append((first_transaction, second_transaction, third_transaction))

    # This is for selecting the third one. 
    if len(valid_combinations) > 0:
        return valid_combinations[0]

    # Returns None if no combination exists.
    return None

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force algorithm iterates through all possible triplets of transactions. The outermost loop selects the first transaction, which takes O(n) time. The second nested loop selects the second transaction from the remaining transactions, taking O(n) time. Finally, the innermost nested loop selects the third transaction from the remaining transactions after the second, again taking O(n) time. Therefore, the overall time complexity is O(n * n * n), which simplifies to O(n^3).

Space Complexity

O(1) – The provided brute force approach stores potential solutions, implying the use of a data structure, like a list, to hold these candidate combinations. However, the problem description does not specify a fixed or variable upper bound on the number of stored solutions. The problem description says to store 'potential solutions', implying a number of solutions that is not dependent on the size of the input. Even if multiple solutions are stored, the number of solutions is still independent of the input dataset size, N. Thus, the auxiliary space is constant.

Optimal Solution

Approach

To efficiently find the third transaction, we maintain the best two transactions seen so far. Then, we iterate through the remaining transactions and identify the first one that exceeds the value of our second-best transaction, designating it as the third.

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

First, keep track of the two largest transaction amounts we've encountered so far. Think of them as our front-runners.
Next, go through each transaction, one by one, comparing it against the second-largest amount we have stored.
As soon as you find a transaction amount that is bigger than our second-largest front-runner, mark that transaction as the third largest. We've found our match!
If after going through all transactions, you haven't found one bigger than the second largest, it means a third largest doesn't exist, so indicate that.

Code Implementation

def find_third_transaction(transactions):
    first_transaction = None
    second_transaction = None
    third_transaction = None

    for transaction in transactions:
        if first_transaction is None:
            # Initialize all three to the first transaction.
            first_transaction = transaction
            second_transaction = transaction
            third_transaction = transaction

        elif second_transaction is None:
            # Initialize second to the current transaction.
            second_transaction = transaction
            
        elif third_transaction is None:
            # Now we have our first, second and third
            third_transaction = transaction

        else:
            # Replace the oldest transaction with the current.
            first_transaction = second_transaction
            second_transaction = third_transaction
            third_transaction = transaction

    return first_transaction

Big(O) Analysis

Time Complexity

O(n) – The algorithm first iterates through the array of transactions once to find the two largest transaction amounts. This initial pass takes O(n) time. Then, it iterates through the array again, comparing each transaction to the second largest transaction found in the first pass. This second pass also takes O(n) time. Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables (to store the largest and second largest transaction amounts) regardless of the number of transactions in the input. No additional data structures, such as arrays or hash maps, are created that scale with the input size N. Therefore, the auxiliary space required remains constant, irrespective of the value of N, the number of transactions. This results in a space complexity of O(1).

Edge Cases

Case	How to Handle
Null or empty prices array	Return 0 immediately, as no transactions are possible.
Prices array with length less than 2	Return 0, as at least two prices are needed for a transaction.
Prices array is sorted in descending order (always losing money)	The algorithm should correctly identify and return 0 profit.
Prices array contains all identical values	Return 0, as no profit can be made from identical prices.
Prices array contains very large numbers (potential integer overflow)	Use a data type that can hold larger values, such as long, to prevent overflow during profit calculations.
Prices array where three transactions are impossible or suboptimal (e.g., most profits can be made with one or two)	The algorithm should correctly determine the maximum profit achievable with at most three transactions, even if fewer transactions yield higher profits.
Large prices array (performance considerations)	Ensure the solution's time complexity is efficient (e.g., O(n) or O(n log n)) to handle large arrays without excessive runtime.
Prices array containing negative values (invalid stock prices)	The algorithm should ideally throw an exception or handle the negative prices gracefully as invalid input because stock prices are always non-negative, or it must handle it by taking the absolute value of the number.