Best Time to Buy and Sell Stock III

Hard

Best Time to Buy and Sell Stock III

Hard

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 maximum number of transactions allowed (is it strictly 2, or can it be a variable number up to a maximum of 2)?
Can the input `prices` array be empty, or contain only one day's price?
If no transactions are profitable (i.e., all prices are decreasing), what should the function return: 0, null, or throw an exception?
Are the prices guaranteed to be non-negative integers?
If there are multiple ways to achieve the maximum profit with two transactions, is any valid combination acceptable?

Brute Force Solution

Approach

The problem wants us to find the maximum profit we can make by buying and selling a stock at most two times. The brute force way is to try every single possible pair of buy and sell days, and see which combination gives us the most profit.

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

First, imagine you don't do any transactions at all. Your profit is zero. This is a baseline to compare against.
Next, consider all possible single transactions. Try buying on the first day and selling on every day after that. Then try buying on the second day and selling on every day after that, and so on. Calculate the profit for each of these single transactions.
Now, for every possible single transaction, consider doing a second transaction. For each of the single transactions you calculated earlier, try buying again on any day *after* the sell day of the first transaction and selling again on any day after that second buy day. Calculate the total profit for each pair of transactions.
Compare the profit from all possible single transactions, all possible pairs of transactions, and doing no transactions at all.
The largest profit you find among all these possibilities is the answer.

Code Implementation

def max_profit_two_transactions_brute_force(prices):
    number_of_days = len(prices)
    max_overall_profit = 0

    # Consider no transactions.

    # Consider all single transactions.
    for buy_day_one in range(number_of_days):
        for sell_day_one in range(buy_day_one + 1, number_of_days):
            profit_one = prices[sell_day_one] - prices[buy_day_one]

            # If the first transaction results in a loss, continue to the next one
            if profit_one <= 0:
                continue

            max_overall_profit = max(max_overall_profit, profit_one)

            # Consider all pairs of transactions.
            for buy_day_two in range(sell_day_one + 1, number_of_days):
                for sell_day_two in range(buy_day_two + 1, number_of_days):

                    # Calculate profit from the second transaction.
                    profit_two = prices[sell_day_two] - prices[buy_day_two]

                    # Total profit from both transactions.
                    total_profit = profit_one + profit_two
                    max_overall_profit = max(max_overall_profit, total_profit)

    return max_overall_profit

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm first considers all single transactions, which involves iterating through the array of prices to find the best buy and sell days for one transaction. This takes O(n^2) time (nested loops). For each of these single transactions, the algorithm then considers all possible second transactions occurring after the first one, which requires another nested loop within the first pair, hence O(n^3). Therefore, the overall time complexity is dominated by the triple nested loops resulting in O(n^3).

Space Complexity

O(1) – The described brute force approach iterates through the input array 'prices' of size N to find the best buy and sell days. It primarily uses a few variables to store the best profit found so far and indices for buy and sell days. No auxiliary data structures like arrays or hash maps are created that scale with the input size N. Therefore, the space complexity is constant, O(1).

Optimal Solution

Approach

This problem wants us to find the maximum profit we can make by buying and selling a stock at most twice. The clever approach is to break the problem into smaller, manageable parts by figuring out the best buy/sell points separately and then combining the best results.

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

First, imagine you're only allowed one transaction. Figure out, for each day, what the maximum profit would be if you had to sell on that specific day. This gives you the best profit you can get up to any given day.
Next, do the same thing but in reverse. Figure out, for each day, what the maximum profit would be if you had to buy on that specific day. This gives you the best profit you can get after any given day.
Now, for every possible day, add the 'best profit before that day' and the 'best profit after that day'. This represents the maximum profit if you made one transaction before and one transaction after that chosen day.
Finally, pick the largest sum you calculated in the previous step. This is the maximum profit you can achieve with at most two transactions. Remember to also consider the case where you only do one transaction if that yields a higher profit than two.

Code Implementation

def max_profit(prices):
    number_of_days = len(prices)
    if number_of_days < 2:
        return 0

    left_profit = [0] * number_of_days
    min_price_so_far = prices[0]

    # Calculate max profit if selling on each day with one transaction
    for day in range(1, number_of_days):
        min_price_so_far = min(min_price_so_far, prices[day])
        left_profit[day] = max(left_profit[day - 1], prices[day] - min_price_so_far)

    right_profit = [0] * number_of_days
    max_price_so_far = prices[number_of_days - 1]

    # Calculate max profit if buying on each day with one transaction, backwards
    for day in range(number_of_days - 2, -1, -1):
        max_price_so_far = max(max_price_so_far, prices[day])
        right_profit[day] = max(right_profit[day + 1], max_price_so_far - prices[day])

    max_total_profit = 0
    #Find best split point for the two transactions
    for day in range(number_of_days):
        max_total_profit = max(max_total_profit, left_profit[day] + right_profit[day])

    return max_total_profit

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the prices array a fixed number of times (three times). The first iteration calculates the maximum profit achievable before each day. The second iteration calculates the maximum profit achievable after each day. The final iteration calculates the maximum profit from combining the two transactions, by adding the profits achieved before and after each day, and comparing the results. Since each iteration loops through the n elements of the prices array independently, the time complexity is proportional to n. Therefore the overall time complexity is O(n).

Space Complexity

O(N) – The provided solution uses two arrays, 'profit_before' and 'profit_after', to store the maximum profit achievable up to each day and after each day respectively. Since the size of each of these arrays scales linearly with the number of days (N, the size of the input prices array), the auxiliary space used is proportional to N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty price array	Return 0 as no profit can be made with no prices.
Array with only one price	Return 0 as buying and selling on the same day yields no profit.
Prices are monotonically decreasing (always losing money)	The algorithm should return 0 as no profitable transaction is possible.
Prices are monotonically increasing (always making money)	The algorithm should correctly calculate the maximum profit by buying at the lowest price and selling at the highest twice, if possible.
Large price fluctuations leading to integer overflow	Use `long` or a similar data type to store profit to prevent overflow.
Prices include negative values or zero values	The algorithm should work correctly as negative prices are not inherently problematic, but they must be handled correctly during profit calculations.
Maximum number of allowed transactions is zero	Return 0, since no transactions are possible and hence no profit.
All prices are the same	Return 0, because no transaction can yield profit