Jobs

Interviews

Discussions

Best Time to Buy and Sell Stock III #4 Most Asked

Hard

Bolt

1 view

Topics:

ArraysDynamic Programming

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

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: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

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

Try coding it in LeetCode

Best Time to Buy and Sell Stock III #4 Most Asked

Hard

Bolt

1 view

Topics:

ArraysDynamic Programming

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

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: In this case, no transaction is done, i.e. max profit = 0.

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 should be returned if the `prices` array is empty or contains only one element?
Can the stock prices be zero? Are they always non-negative integers?
To clarify the transaction rule: does 'sell before you buy again' mean the second buy must happen on a day strictly after the first sell day?
What are the constraints on the size of the `prices` array and the range of values for the stock prices?
Is it possible that the optimal strategy involves completing only one transaction, or even zero transactions if all prices are decreasing?

Brute Force Solution

Approach

To find the best possible profit from at most two trades, the most straightforward approach is to try every single possible combination of two trades. We'll simply divide the entire history of stock prices into two separate periods and find the best single trade we could have made in each period.

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

Imagine splitting the entire timeline of stock prices at some point. This split creates a 'before' period and an 'after' period.
For the 'before' period, figure out the maximum profit you could make from a single buy and sell transaction.
Then, do the same for the 'after' period: find the maximum profit you could get from one transaction in that timeframe.
Add the best profit from the 'before' period to the best profit from the 'after' period. This total is your potential maximum profit for that specific split point.
Now, repeat this entire process for every possible place you could split the timeline. For instance, first split after day one, then after day two, and so on, until you've tried all possible split points.
Keep track of the total profit you calculate for each split.
After checking every single possible way to divide the timeline, the highest total profit you found is the answer.

Code Implementation

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

    def max_profit_one_transaction(price_history):
        if not price_history:
            return 0
        
        lowest_price_so_far = float('inf')
        max_profit_found = 0
        for current_price in price_history:
            profit = current_price - lowest_price_so_far
            max_profit_found = max(max_profit_found, profit)
            lowest_price_so_far = min(lowest_price_so_far, current_price)
        return max_profit_found

    max_total_profit = 0

    # The main loop iterates through every possible day to split the timeline into two periods.
    for split_index in range(number_of_days + 1):
        first_period_prices = prices[0:split_index]
        second_period_prices = prices[split_index:number_of_days]

        # We calculate the max profit for a single trade in the first period.
        max_profit_first_period = max_profit_one_transaction(first_period_prices)
        
        # Then, we do the same for the second period to find its best single trade profit.
        max_profit_second_period = max_profit_one_transaction(second_period_prices)

        # The total profit for this specific split is the sum of profits from both periods.
        current_total_profit = max_profit_first_period + max_profit_second_period
        max_total_profit = max(max_total_profit, current_total_profit)

    return max_total_profit

Big(O) Analysis

Time Complexity

O(n²) – The core of this approach is iterating through every possible day to split the timeline. Let's say there are n days. This main loop runs n times. For each of these n splits, we must calculate the maximum profit for a single transaction in both the 'before' and 'after' subarrays. Finding the max profit in a subarray of size k takes O(k) time. Since the 'before' and 'after' subarrays collectively have n elements, each split requires O(n) work. Performing O(n) work for each of the n possible split points results in a total of approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(N) – The solution described involves splitting the price history and calculating the maximum profit for the period before the split and the period after the split. To do this efficiently for all possible split points, we need to pre-calculate and store the maximum single-transaction profit possible up to each day `i` in an auxiliary array. A second auxiliary array is also needed to store the maximum single-transaction profit possible from day `i` to the end. Since each of these arrays must store a value for every day, they both require space proportional to the number of prices, N, leading to O(N) auxiliary space.

Optimal Solution

Approach

Imagine you have to complete at most two round trips of buying and then selling a stock. The clever approach is to track the most money you could have after each of the four possible actions (your first buy, first sell, second buy, and second sell) as you go through the daily prices one by one.

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

First, let's think about the four actions in order: buying for the first time, selling for the first time, buying for the second time, and finally selling for the second time.
As we look at each day's price, we'll keep four running totals representing the best possible outcome after each of these four actions.
For the first purchase, we want to find the cheapest price so far. Our 'profit' after this first buy is actually a loss, so we want the smallest loss possible.
For the first sale, we consider the current day's price. We can either sell today for a profit, or stick with the best profit we've already made from a previous sale. We choose whichever is better.
For the second purchase, we imagine taking the profit from our first sale and immediately using it to buy again on the current day. We want to find the point where we have the most money left over after this second buy.
Finally, for the second sale, we see if selling today (using the stock from our second purchase) gives us a better final total than any previous second sale. We update our best final profit with the higher amount.
By moving through the days and constantly updating the best possible financial position after each of the four steps, we ensure that by the last day, we know the absolute maximum profit we could have made from two trades.

Code Implementation

def maxProfit(prices):
    if not prices:
        return 0

    # Initialize states representing the max money after each of the four actions.
    profit_after_first_buy = -prices[0]
    profit_after_first_sell = 0
    profit_after_second_buy = -prices[0]
    profit_after_second_sell = 0

    for current_price in prices:
        # We want the smallest loss, so we choose the minimum of the previous state and buying now.
        profit_after_first_buy = max(profit_after_first_buy, -current_price)

        # For the first sale, we either stick with our previous best sale or sell today.
        profit_after_first_sell = max(profit_after_first_sell, profit_after_first_buy + current_price)

        # For the second buy, we use profits from the first sale to 'invest' in this new stock.
        profit_after_second_buy = max(profit_after_second_buy, profit_after_first_sell - current_price)

        # The final profit is the max of the previous best second sale or selling our second stock today.
        profit_after_second_sell = max(profit_after_second_sell, profit_after_second_buy + current_price)

    return profit_after_second_sell

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the need to process each stock price once. The algorithm iterates through the input array of n daily prices a single time. During each iteration, it performs a constant number of calculations to update the four state variables representing the best possible profit after each buy and sell action. Since the work done for each of the n prices is constant, the total number of operations grows linearly with the size of the input array, resulting in an O(n) time complexity.

Space Complexity

O(1) – The algorithm processes the stock prices by maintaining only four variables to track the best possible financial state after each of the four potential actions: first buy, first sell, second buy, and second sell. These four variables occupy a fixed amount of memory. Since the space required does not grow with the number of prices (N) in the input array, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty input array	The profit is zero as no transactions can be made.
Input array with only one element	The profit must be zero since a buy and a sell operation requires at least two days.
Prices are in strictly decreasing order (e.g., [5, 4, 3, 2, 1])	The maximum profit is zero because buying on any day and selling later will always result in a loss.
Prices are in strictly increasing order (e.g., [1, 2, 3, 4, 5])	The algorithm should correctly identify that two transactions are better than one, splitting the single long profit trend.
All prices in the array are identical (e.g., [7, 7, 7, 7])	The profit is zero as no profitable transaction is possible.
The optimal solution involves only one transaction, not two	The algorithm must correctly determine that using only one of the two allowed transactions yields the maximum profit.
Input array contains zero as a price	Zero is a valid price and should be handled like any other non-negative integer in profit calculations.
Very large input array size (e.g., 10^5 elements)	The solution should be O(n) in time and O(1) in space to avoid timeout or memory limit errors.

Empty input array

How to Handle:

The profit is zero as no transactions can be made.

Input array with only one element

How to Handle:

The profit must be zero since a buy and a sell operation requires at least two days.

Prices are in strictly decreasing order (e.g., [5, 4, 3, 2, 1])

How to Handle:

The maximum profit is zero because buying on any day and selling later will always result in a loss.

Prices are in strictly increasing order (e.g., [1, 2, 3, 4, 5])

How to Handle:

The algorithm should correctly identify that two transactions are better than one, splitting the single long profit trend.

All prices in the array are identical (e.g., [7, 7, 7, 7])

How to Handle:

The profit is zero as no profitable transaction is possible.

The optimal solution involves only one transaction, not two

How to Handle:

The algorithm must correctly determine that using only one of the two allowed transactions yields the maximum profit.

Input array contains zero as a price

How to Handle:

Zero is a valid price and should be handled like any other non-negative integer in profit calculations.

Very large input array size (e.g., 10^5 elements)

How to Handle:

The solution should be O(n) in time and O(1) in space to avoid timeout or memory limit errors.

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 should be returned if the `prices` array is empty or contains only one element?
Can the stock prices be zero? Are they always non-negative integers?
To clarify the transaction rule: does 'sell before you buy again' mean the second buy must happen on a day strictly after the first sell day?
What are the constraints on the size of the `prices` array and the range of values for the stock prices?
Is it possible that the optimal strategy involves completing only one transaction, or even zero transactions if all prices are decreasing?

Brute Force Solution

Approach

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

Imagine splitting the entire timeline of stock prices at some point. This split creates a 'before' period and an 'after' period.
For the 'before' period, figure out the maximum profit you could make from a single buy and sell transaction.
Then, do the same for the 'after' period: find the maximum profit you could get from one transaction in that timeframe.
Add the best profit from the 'before' period to the best profit from the 'after' period. This total is your potential maximum profit for that specific split point.
Now, repeat this entire process for every possible place you could split the timeline. For instance, first split after day one, then after day two, and so on, until you've tried all possible split points.
Keep track of the total profit you calculate for each split.
After checking every single possible way to divide the timeline, the highest total profit you found is the answer.

Code Implementation

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

    def max_profit_one_transaction(price_history):
        if not price_history:
            return 0
        
        lowest_price_so_far = float('inf')
        max_profit_found = 0
        for current_price in price_history:
            profit = current_price - lowest_price_so_far
            max_profit_found = max(max_profit_found, profit)
            lowest_price_so_far = min(lowest_price_so_far, current_price)
        return max_profit_found

    max_total_profit = 0

    # The main loop iterates through every possible day to split the timeline into two periods.
    for split_index in range(number_of_days + 1):
        first_period_prices = prices[0:split_index]
        second_period_prices = prices[split_index:number_of_days]

        # We calculate the max profit for a single trade in the first period.
        max_profit_first_period = max_profit_one_transaction(first_period_prices)
        
        # Then, we do the same for the second period to find its best single trade profit.
        max_profit_second_period = max_profit_one_transaction(second_period_prices)

        # The total profit for this specific split is the sum of profits from both periods.
        current_total_profit = max_profit_first_period + max_profit_second_period
        max_total_profit = max(max_total_profit, current_total_profit)

    return max_total_profit

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, let's think about the four actions in order: buying for the first time, selling for the first time, buying for the second time, and finally selling for the second time.
As we look at each day's price, we'll keep four running totals representing the best possible outcome after each of these four actions.
For the first purchase, we want to find the cheapest price so far. Our 'profit' after this first buy is actually a loss, so we want the smallest loss possible.
For the first sale, we consider the current day's price. We can either sell today for a profit, or stick with the best profit we've already made from a previous sale. We choose whichever is better.
For the second purchase, we imagine taking the profit from our first sale and immediately using it to buy again on the current day. We want to find the point where we have the most money left over after this second buy.
Finally, for the second sale, we see if selling today (using the stock from our second purchase) gives us a better final total than any previous second sale. We update our best final profit with the higher amount.
By moving through the days and constantly updating the best possible financial position after each of the four steps, we ensure that by the last day, we know the absolute maximum profit we could have made from two trades.

Code Implementation

def maxProfit(prices):
    if not prices:
        return 0

    # Initialize states representing the max money after each of the four actions.
    profit_after_first_buy = -prices[0]
    profit_after_first_sell = 0
    profit_after_second_buy = -prices[0]
    profit_after_second_sell = 0

    for current_price in prices:
        # We want the smallest loss, so we choose the minimum of the previous state and buying now.
        profit_after_first_buy = max(profit_after_first_buy, -current_price)

        # For the first sale, we either stick with our previous best sale or sell today.
        profit_after_first_sell = max(profit_after_first_sell, profit_after_first_buy + current_price)

        # For the second buy, we use profits from the first sale to 'invest' in this new stock.
        profit_after_second_buy = max(profit_after_second_buy, profit_after_first_sell - current_price)

        # The final profit is the max of the previous best second sale or selling our second stock today.
        profit_after_second_sell = max(profit_after_second_sell, profit_after_second_buy + current_price)

    return profit_after_second_sell

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	The profit is zero as no transactions can be made.
Input array with only one element	The profit must be zero since a buy and a sell operation requires at least two days.
Prices are in strictly decreasing order (e.g., [5, 4, 3, 2, 1])	The maximum profit is zero because buying on any day and selling later will always result in a loss.
Prices are in strictly increasing order (e.g., [1, 2, 3, 4, 5])	The algorithm should correctly identify that two transactions are better than one, splitting the single long profit trend.
All prices in the array are identical (e.g., [7, 7, 7, 7])	The profit is zero as no profitable transaction is possible.
The optimal solution involves only one transaction, not two	The algorithm must correctly determine that using only one of the two allowed transactions yields the maximum profit.
Input array contains zero as a price	Zero is a valid price and should be handled like any other non-negative integer in profit calculations.
Very large input array size (e.g., 10^5 elements)	The solution should be O(n) in time and O(1) in space to avoid timeout or memory limit errors.

Empty input array

How to Handle:

The profit is zero as no transactions can be made.

Input array with only one element

How to Handle:

The profit must be zero since a buy and a sell operation requires at least two days.

Prices are in strictly decreasing order (e.g., [5, 4, 3, 2, 1])

How to Handle:

The maximum profit is zero because buying on any day and selling later will always result in a loss.

Prices are in strictly increasing order (e.g., [1, 2, 3, 4, 5])

How to Handle:

The algorithm should correctly identify that two transactions are better than one, splitting the single long profit trend.

All prices in the array are identical (e.g., [7, 7, 7, 7])

How to Handle:

The profit is zero as no profitable transaction is possible.

The optimal solution involves only one transaction, not two

How to Handle:

The algorithm must correctly determine that using only one of the two allowed transactions yields the maximum profit.

Input array contains zero as a price

How to Handle:

Zero is a valid price and should be handled like any other non-negative integer in profit calculations.

Very large input array size (e.g., 10^5 elements)

How to Handle:

The solution should be O(n) in time and O(1) in space to avoid timeout or memory limit errors.

0/0 Bolt questions completed

0/0 completed