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
Level of Question
Hard

Best Time to Buy and Sell Stock III LeetCode Solution
Table of Contents
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 Complexity | Space Complexity | |
C++ | O(n) | O(n) |
Java | O(n) | O(1) |
JavaScript | O(n) | O(n) |
Python | O(n) | O(n) |