Best Time to Buy and Sell Stock III LeetCode Solution

Last updated on January 29th, 2025 at 02:12 am

Here, we see a Best Time to Buy and Sell Stock III LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Dynamic Programming

Companies

Google

Level of Question

Hard

Best Time to Buy and Sell Stock III LeetCode Solution

Best Time to Buy and Sell Stock III LeetCode Solution

1. Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith 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.

2. Coding Pattern Used in Solution

The problem being solved in all the provided code snippets is a variation of the “Stock Buy and Sell” problem, specifically for at most two transactions. The coding pattern used here is Dynamic Programming (DP). This pattern is used to break the problem into smaller overlapping subproblems and solve them efficiently by storing intermediate results.

3. Code Implementation in Different Languages

3.1 Best Time to Buy and Sell Stock III C++

class Solution {
public:
    unordered_map<string, int> memo;
    int profit(vector<int> prices, int i, int isBuy, int k){
        if(i == prices.size() || k == 2)
            return 0;
        string key = to_string(i) + "-" + to_string(isBuy) + "-" + to_string(k);
        if(memo.find(key)!=memo.end())
            return memo[key];
        int a,b;
        if(isBuy){
            a = profit(prices, i + 1, 1, k);
            b = profit(prices, i + 1, 0, k) - prices[i];
        }  
        else{
            a = profit(prices, i + 1, 0, k);
            b = profit(prices, i + 1, 1, k + 1) + prices[i];
        }   
        return memo[key] = max(a, b);
    }
    
    int maxProfit(vector<int>& prices) {
        return profit(prices, 0, 1, 0);
    }
};

3.2 Best Time to Buy and Sell Stock III Java

class Solution {
public int maxProfit(int[] prices) {
		int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
		for (int i = 0; i < prices.length; i++) {
			buy1 = Math.max(buy1, -prices[i]);
			sell1 = Math.max(sell1, buy1 + prices[i]);
			buy2 = Math.max(buy2, sell1 - prices[i]);
			sell2 = Math.max(sell2, buy2 + prices[i]);
		}
		return sell2;
	}
}

3.3 Best Time to Buy and Sell Stock III JavaScript

var maxProfit = function(prices) {
  if(prices.length == 0) return 0
  let dp = new Array(prices.length).fill(0);
  let min = prices[0];
  let max = 0;
  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    max = Math.max(max, prices[i] - min);
    dp[i] = max;
  }
  min = prices[0];
  max = 0;
  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i] - dp[i]);
    max = Math.max(max, prices[i] - min);
    dp[i] = max;
  }
  return dp.pop();
};

3.4 Best Time to Buy and Sell Stock III Python

class Solution(object):
    def maxProfit(self, prices):
        if not prices:
            return 0
        profits = []
        max_profit = 0
        current_min = prices[0]
        for price in prices:
            current_min = min(current_min, price)
            max_profit = max(max_profit, price - current_min)
            profits.append(max_profit)
        total_max = 0    
        max_profit = 0
        current_max = prices[-1]
        for i in range(len(prices) - 1, -1, -1):
            current_max = max(current_max, prices[i])
            max_profit = max(max_profit, current_max - prices[i])
            total_max = max(total_max, max_profit + profits[i])
        return total_max

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n)O(n)
JavaO(n)O(1)
JavaScriptO(n)O(n)
PythonO(n)O(n)
Scroll to Top