Tejav
#123

Best Time to Buy and Sell Stock III

Hard
ArrayDynamic ProgrammingDynamic ProgrammingGreedy Algorithms
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(1)
💡

Intuition

Time O(n)Space O(1)

The optimal solution uses dynamic programming to keep track of profits at each day for up to two transactions. This method reduces the number of calculations by storing intermediate results, allowing us to build up the solution efficiently.

⚙️

Algorithm

3 steps
  1. 1Step 1: Initialize an array to store profits for each transaction (up to 2 transactions).
  2. 2Step 2: For each day, update the maximum profit for each transaction by considering buying and selling on that day.
  3. 3Step 3: Return the maximum profit after processing all days.
solution.py13 lines
1def maxProfit(prices):
2    if not prices:
3        return 0
4    first_buy = float('-inf')
5    first_sell = 0
6    second_buy = float('-inf')
7    second_sell = 0
8    for price in prices:
9        first_buy = max(first_buy, -price)
10        first_sell = max(first_sell, first_buy + price)
11        second_buy = max(second_buy, first_sell - price)
12        second_sell = max(second_sell, second_buy + price)
13    return second_sell
ℹ

Complexity note: This complexity is linear because we only traverse the prices array once, updating our profit variables in constant time.

  • 1Understanding the need for multiple transactions
  • 2Dynamic programming can optimize repetitive calculations

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.