We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Best Time to Buy and Sell Stock III

Number: 123

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Meta, Microsoft, Citadel, Visa, Bolt, Adobe, Bloomberg, Uber, TikTok, Snap, PhonePe

Problem Description

Given an array of stock prices where prices[i] is the price on the iᵗʰ day, determine the maximum profit obtainable with at most two transactions. Note that you cannot hold multiple stocks at once; you must sell the stock before buying again.

Key Insights

  • The problem requires the optimal selection of at most two buy-sell transactions.
  • One effective strategy is to split the problem into two parts:
    • For each day i, calculate the maximum profit obtainable from day 0 to i with one transaction.
    • For each day i, calculate the maximum profit obtainable from day i to the end with one transaction.
  • Finally, for each day, the sum of these two profits (left and right) gives a candidate answer.
  • Alternatively, a state-based dynamic programming approach can track 4 states corresponding to the two transactions.

Space and Time Complexity

Time Complexity: O(n) where n is the number of days
Space Complexity: O(n) due to extra arrays used for forward and backward computations (this can be optimized to O(1) with a state variable approach)

Solution

We use a two-pass dynamic programming approach. In the first pass (forward), we compute an array "leftProfits" where leftProfits[i] is the maximum profit from day 0 to day i with one transaction. We do this by keeping track of the minimum price observed so far and calculating the profit if sold on day i. In the second pass (backward), we compute an array "rightProfits" where rightProfits[i] is the maximum profit obtainable from day i to the last day with one transaction by tracking the maximum price seen in reverse order. Finally, for every index i, the sum leftProfits[i] + rightProfits[i] represents the maximum profit achievable by completing the first transaction on or before day i and the second transaction starting from day i. The answer is the maximum sum over all i.

Code Solutions

# Python solution for Best Time to Buy and Sell Stock III

def max_profit(prices):
    # If there are less than 2 days, no transaction can be made.
    if not prices or len(prices) < 2:
        return 0

    n = len(prices)
    # Initialize left and right profit arrays with zeros.
    left_profits = [0] * n  
    right_profits = [0] * n  

    # Forward pass: compute max profit until day i with one transaction.
    min_price = prices[0]
    for i in range(1, n):
        # Update the min price encountered so far.
        min_price = min(min_price, prices[i])
        # Maximum profit if sold on day i.
        left_profits[i] = max(left_profits[i - 1], prices[i] - min_price)

    # Backward pass: compute max profit from day i to end with one transaction.
    max_price = prices[-1]
    for i in range(n - 2, -1, -1):
        # Update max price seen from the right.
        max_price = max(max_price, prices[i])
        # Maximum profit possible starting from day i.
        right_profits[i] = max(right_profits[i + 1], max_price - prices[i])

    # Combine the two profits to find the maximum total profit.
    max_total_profit = 0
    for i in range(n):
        max_total_profit = max(max_total_profit, left_profits[i] + right_profits[i])
        
    return max_total_profit

# Example usage:
prices = [3,3,5,0,0,3,1,4]
print(max_profit(prices))  # Expected output: 6
← Back to All Questions