Best Time to Buy and Sell Stock III solution and explanation
Google
9 more videos on this problem
Best Time to Buy and Sell Stock III | Leetcode #123Techdose · 35:40 · 80K views
Leetcode 123. Best Time to Buy and Sell Stock III [ Algorithm + Code Explained]jayati tiwari · 11:37 · 30K views
Leetcode 123. Best Time to Buy and Sell Stock IIIFraz · 6:20 · 13K views
Best Time to Buy and Sell Stock III | Leet code 123 | Theory explained + Python codeSai Anish Malla · 15:22 · 10K views
Best Time to Buy and Sell Stock III | Live Coding with Explanation | Leetcode - 123Algorithms Made Easy · 26:03 · 9K views
Leetcode - Best Time to Buy and Sell Stock III (Python)Timothy H Chang · 11:28 · 8K views
Best Time to Buy and Sell Stock III | leetcode 123 | HindiCodebix · 21:40 · 6K views
LeetCode 123 | Best Time to Buy and Sell Stock III | Solution Explained (Java + Whiteboard)Xavier Elon · 10:20 · 4K views
best time to buy and sell stock iii leetcode | best time to buy and sell stock 3 | leetcode 123Naresh Gupta · 14:02 · 2K views
DP 37. Buy and Sell Stocks III | Recursion to Space Optimisationtake U forward · 31:50 · 317K views
The problem
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.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 105
Approach overview
Problem Overview: You are given an array where prices[i] represents the stock price on day i. You can complete at most two transactions (buy then sell). The goal is to compute the maximum profit possible without holding more than one stock at a time.
Approach 1: Dynamic Programming with 4 State Variables (O(n) time, O(1) space)
This approach models the trading process as four states: first buy, first sell, second buy, and second sell. Each state represents the best profit achievable after that operation. While iterating through the price array, update the states using simple max comparisons such as firstBuy = max(firstBuy, -price) and firstSell = max(firstSell, firstBuy + price). The key insight is that every transaction builds on the previous one, so the second buy depends on the profit from the first sell. This reduces the entire dynamic programming formulation into four running variables, giving an optimal O(n) solution with constant memory.
Approach 2: Two Arrays for Tracking Left and Right Profits (O(n) time, O(n) space)
This strategy splits the problem into two independent subproblems. First, traverse the array from left to right and compute leftProfit[i], the maximum profit achievable with one transaction in the range [0, i]. Then traverse from right to left to compute rightProfit[i], the best profit for one transaction in [i, n-1]. Combining these two arrays lets you evaluate every possible split point where the first transaction happens before the second. The final answer is the maximum value of leftProfit[i] + rightProfit[i]. This technique works well when reasoning about prefix and suffix profits in array problems.
Recommended for interviews: The 4‑state dynamic programming solution is usually expected in interviews because it demonstrates strong understanding of dynamic programming state transitions and optimization. The two‑array method is easier to reason about conceptually, but the constant‑space DP version shows deeper algorithmic skill and cleaner implementation.
Approach 1: Approach 1: Dynamic Programming with 4 State Variables
This approach utilizes dynamic programming with four state variables to track the profit in various stages of transactions: before the first buy, after the first buy (before the sell), after the first sell (before the second buy), and after the second buy (before the final sell). By iterating over the prices array, we update these states with the maximum profit achievable at each step.
def maxProfit(prices):
first_buy, first_sell = float('-inf'), 0
second_buy, second_sell = float('-inf'), 0
for price in prices:
first_buy = max(first_buy, -price)
first_sell = max(first_sell, first_buy + price)
second_buy = max(second_buy, first_sell - price)
second_sell = max(second_sell, second_buy + price)
return second_sell
prices = [3, 3, 5, 0, 0, 3, 1, 4]
print(f'Max Profit: {maxProfit(prices)}')public class StockProfit {
public static int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
int firstBuy = Integer.MIN_VALUE, firstSell = 0, secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int price : prices) {
firstBuy = Math.max(firstBuy, -price);
firstSell = Math.max(firstSell, firstBuy + price);
secondBuy = Math.max(secondBuy, firstSell - price);
secondSell = Math.max(secondSell, secondBuy + price);
}
return secondSell;
}
public static void main(String[] args) {
int[] prices = {3, 3, 5, 0, 0, 3, 1, 4};
System.out.println("Max Profit: " + maxProfit(prices));
}
}#include <vector>
#include <algorithm>
#include <iostream>
int maxProfit(std::vector<int>& prices) {
if (prices.empty()) return 0;
int firstBuy = INT_MIN, firstSell = 0, secondBuy = INT_MIN, secondSell = 0;
for (int price : prices) {
firstBuy = std::max(firstBuy, -price);
firstSell = std::max(firstSell, firstBuy + price);
secondBuy = std::max(secondBuy, firstSell - price);
secondSell = std::max(secondSell, secondBuy + price);
}
return secondSell;
}
int main() {
std::vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
std::cout << "Max Profit: " << maxProfit(prices) << std::endl;
return 0;
}function maxProfit(prices) {
let firstBuy = -Infinity, firstSell = 0, secondBuy = -Infinity, secondSell = 0;
for (let price of prices) {
firstBuy = Math.max(firstBuy, -price);
firstSell = Math.max(firstSell, firstBuy + price);
secondBuy = Math.max(secondBuy, firstSell - price);
secondSell = Math.max(secondSell, secondBuy + price);
}
return secondSell;
}
const prices = [3, 3, 5, 0, 0, 3, 1, 4];
console.log("Max Profit: " + maxProfit(prices));#include <stdio.h>
int maxProfit(int* prices, int pricesSize) {
if (pricesSize <= 1) return 0;
int firstBuy = -1000000, firstSell = 0, secondBuy = -1000000, secondSell = 0;
for (int i = 0; i < pricesSize; i++) {
firstBuy = firstBuy > -prices[i] ? firstBuy : -prices[i];
firstSell = firstSell > firstBuy + prices[i] ? firstSell : firstBuy + prices[i];
secondBuy = secondBuy > firstSell - prices[i] ? secondBuy : firstSell - prices[i];
secondSell = secondSell > secondBuy + prices[i] ? secondSell : secondBuy + prices[i];
}
return secondSell;
}
int main() {
int prices[] = {3, 3, 5, 0, 0, 3, 1, 4};
int size = sizeof(prices) / sizeof(prices[0]);
printf("Max Profit: %d\n", maxProfit(prices, size));
return 0;
}using System;
public class StockProfit {
public static int MaxProfit(int[] prices) {
int firstBuy = int.MinValue, firstSell = 0, secondBuy = int.MinValue, secondSell = 0;
foreach (int price in prices) {
firstBuy = Math.Max(firstBuy, -price);
firstSell = Math.Max(firstSell, firstBuy + price);
secondBuy = Math.Max(secondBuy, firstSell - price);
secondSell = Math.Max(secondSell, secondBuy + price);
}
return secondSell;
}
public static void Main() {
int[] prices = new int[] { 3, 3, 5, 0, 0, 3, 1, 4 };
Console.WriteLine("Max Profit: " + MaxProfit(prices));
}
}In Python, we use four main variables to track the transaction stages, adjusting for maximum profit. This approach efficiently computes the desired output with a simple loop.
Time Complexity: O(n), one loop traversal.
Space Complexity: O(1), minimal extra space used.
Approach 2: Approach 2: Two Arrays for Tracking Left and Right Profits
This approach involves creating two arrays that store the maximum profit achievable from the left side to each index and from each index to the right in the prices array. Combining these two arrays helps derive the total maximum profit achievable through two transactions.
def maxProfit(prices):
if len(prices) <= 1:
return 0
n = len(prices)
leftProfit = [0] * n
rightProfit = [0] * (n + 1)
minPrice = prices[0]
for i in range(1, n):
leftProfit[i] = max(leftProfit[i - 1], prices[i] - minPrice)
minPrice = min(minPrice, prices[i])
maxPrice = prices[n - 1]
for i in range(n - 2, -1, -1):
rightProfit[i] = max(rightProfit[i + 1], maxPrice - prices[i])
maxPrice = max(maxPrice, prices[i])
maxProfit = max(leftProfit[i] + rightProfit[i] for i in range(n))
return maxProfit
prices = [3, 3, 5, 0, 0, 3, 1, 4]
print(f'Max Profit: {maxProfit(prices)}')public class StockProfit {
public static int maxProfit(int[] prices) {
if (prices.length <= 1) return 0;
int n = prices.length;
int[] leftProfit = new int[n];
int[] rightProfit = new int[n + 1];
// Left-to-right pass
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
leftProfit[i] = Math.max(leftProfit[i - 1], prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
// Right-to-left pass
int maxPrice = prices[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightProfit[i] = Math.max(rightProfit[i + 1], maxPrice - prices[i]);
maxPrice = Math.max(maxPrice, prices[i]);
}
int maxProfit = 0;
for (int i = 0; i < n; i++) {
maxProfit = Math.max(maxProfit, leftProfit[i] + rightProfit[i]);
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = {3, 3, 5, 0, 0, 3, 1, 4};
System.out.println("Max Profit: " + maxProfit(prices));
}
}#include <vector>
#include <iostream>
#include <algorithm>
int maxProfit(std::vector<int>& prices) {
if (prices.empty()) return 0;
int n = prices.size();
std::vector<int> leftProfit(n), rightProfit(n);
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
leftProfit[i] = std::max(leftProfit[i - 1], prices[i] - minPrice);
minPrice = std::min(minPrice, prices[i]);
}
int maxPrice = prices[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightProfit[i] = std::max(rightProfit[i + 1], maxPrice - prices[i]);
maxPrice = std::max(maxPrice, prices[i]);
}
int maxProfit = 0;
for (int i = 0; i < n; i++) {
maxProfit = std::max(maxProfit, leftProfit[i] + rightProfit[i]);
}
return maxProfit;
}
int main() {
std::vector<int> prices = {3, 3, 5, 0, 0, 3, 1, 4};
std::cout << "Max Profit: " << maxProfit(prices) << std::endl;
return 0;
}function maxProfit(prices) {
if (prices.length <= 1) return 0;
const n = prices.length;
const leftProfit = new Array(n).fill(0);
const rightProfit = new Array(n + 1).fill(0);
let minPrice = prices[0];
for (let i = 1; i < n; i++) {
leftProfit[i] = Math.max(leftProfit[i - 1], prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
let maxPrice = prices[n - 1];
for (let i = n - 2; i >= 0; i--) {
rightProfit[i] = Math.max(rightProfit[i + 1], maxPrice - prices[i]);
maxPrice = Math.max(maxPrice, prices[i]);
}
let maxProfit = 0;
for (let i = 0; i < n; i++) {
maxProfit = Math.max(maxProfit, leftProfit[i] + rightProfit[i]);
}
return maxProfit;
}
const prices = [3, 3, 5, 0, 0, 3, 1, 4];
console.log("Max Profit: " + maxProfit(prices));#include <stdio.h>
#include <stdlib.h>
int maxProfit(int* prices, int pricesSize) {
if (pricesSize <= 1) return 0;
int* leftProfit = (int*)calloc(pricesSize, sizeof(int));
int* rightProfit = (int*)calloc(pricesSize + 1, sizeof(int)); // rightProfit has one extra space for convenience
int minPrice = prices[0];
for (int i = 1; i < pricesSize; i++) {
leftProfit[i] = prices[i] < minPrice ? leftProfit[i - 1] : max(leftProfit[i - 1], prices[i] - minPrice);
minPrice = prices[i] < minPrice ? prices[i] : minPrice;
}
int maxPrice = prices[pricesSize - 1];
for (int i = pricesSize - 2; i >= 0; i--) {
rightProfit[i] = prices[i] > maxPrice ? rightProfit[i + 1] : max(rightProfit[i + 1], maxPrice - prices[i]);
maxPrice = prices[i] > maxPrice ? prices[i] : maxPrice;
}
int maxProfit = 0;
for (int i = 0; i < pricesSize; i++) {
maxProfit = leftProfit[i] + rightProfit[i] > maxProfit ? leftProfit[i] + rightProfit[i] : maxProfit;
}
free(leftProfit);
free(rightProfit);
return maxProfit;
}
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int prices[] = {3, 3, 5, 0, 0, 3, 1, 4};
int size = sizeof(prices) / sizeof(prices[0]);
printf("Max Profit: %d\n", maxProfit(prices, size));
return 0;
}using System;
public class StockProfit {
public static int MaxProfit(int[] prices) {
int n = prices.Length;
if (n <= 1) return 0;
int[] leftProfit = new int[n];
int[] rightProfit = new int[n + 1];
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
leftProfit[i] = Math.Max(leftProfit[i - 1], prices[i] - minPrice);
minPrice = Math.Min(minPrice, prices[i]);
}
int maxPrice = prices[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightProfit[i] = Math.Max(rightProfit[i + 1], maxPrice - prices[i]);
maxPrice = Math.Max(maxPrice, prices[i]);
}
int maxProfit = 0;
for (int i = 0; i < n; i++) {
maxProfit = Math.Max(maxProfit, leftProfit[i] + rightProfit[i]);
}
return maxProfit;
}
public static void Main() {
int[] prices = new int[] { 3, 3, 5, 0, 0, 3, 1, 4 };
Console.WriteLine("Max Profit: " + MaxProfit(prices));
}
}Python implementation utilizes dual lists for combining profitability potential by progressing and reversing through the data. This sums to establish the best reachable figures.
Time Complexity: O(n), including both directional analyses across prices.
Space Complexity: O(n), two arrays convey temporary profit information.
Approach 3: Dynamic Programming
We define the following variables:
f1represents the maximum profit after the first purchase of the stock;f2represents the maximum profit after the first sale of the stock;f3represents the maximum profit after the second purchase of the stock;f4represents the maximum profit after the second sale of the stock.
During the traversal, we directly calculate f1, f2, f3, f4. We consider that buying and selling on the same day will result in a profit of 0, which will not affect the answer.
Finally, return f4.
The time complexity is O(n), where n is the length of the prices array. The space complexity is O(1).
function maxProfit(prices: number[]): number {
let [f1, f2, f3, f4] = [-prices[0], 0, -prices[0], 0];
for (let i = 1; i < prices.length; ++i) {
f1 = Math.max(f1, -prices[i]);
f2 = Math.max(f2, f1 + prices[i]);
f3 = Math.max(f3, f2 - prices[i]);
f4 = Math.max(f4, f3 + prices[i]);
}
return f4;
}func maxProfit(prices []int) int {
f1, f2, f3, f4 := -prices[0], 0, -prices[0], 0
for i := 1; i < len(prices); i++ {
f1 = max(f1, -prices[i])
f2 = max(f2, f1+prices[i])
f3 = max(f3, f2-prices[i])
f4 = max(f4, f3+prices[i])
}
return f4
}impl Solution {
#[allow(dead_code)]
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut f1 = -prices[0];
let mut f2 = 0;
let mut f3 = -prices[0];
let mut f4 = 0;
let n = prices.len();
for i in 1..n {
f1 = std::cmp::max(f1, -prices[i]);
f2 = std::cmp::max(f2, f1 + prices[i]);
f3 = std::cmp::max(f3, f2 - prices[i]);
f4 = std::cmp::max(f4, f3 + prices[i]);
}
f4
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with 4 State Variables | Time Complexity: O(n), one loop traversal. |
| Approach 2: Two Arrays for Tracking Left and Right Profits | Time Complexity: O(n), including both directional analyses across prices. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with 4 State Variables | O(n) | O(1) | Best overall solution. Preferred in interviews due to optimal space usage and clean DP transitions. |
| Two Arrays for Left and Right Profits | O(n) | O(n) | Useful for understanding the split of two transactions and easier to visualize prefix/suffix profits. |
Frequently asked questions
Is Best Time to Buy and Sell Stock III easy or hard?
LeetCode classifies this problem as Hard because it extends earlier stock problems with a two‑transaction constraint. The challenge is modeling the correct dynamic programming states and updating them in the right order.
Best Time to Buy and Sell Stock III Python/Java solution
Python and Java implementations typically follow the four‑state DP pattern. Maintain variables for firstBuy, firstSell, secondBuy, and secondSell and update them while iterating through the prices array. The logic stays identical across languages with O(n) time and O(1) space.
How to solve Best Time to Buy and Sell Stock III in O(n)?
Track four DP states while iterating through prices: firstBuy, firstSell, secondBuy, and secondSell. Update them sequentially using max comparisons based on the current price. This models two transactions directly and produces the maximum profit in a single pass with constant space.
What is the best approach for Best Time to Buy and Sell Stock III?
The most efficient approach uses dynamic programming with four state variables representing first buy, first sell, second buy, and second sell. Each state tracks the maximum profit achievable after that step. Iterating through the price array once updates these states, producing the optimal answer in O(n) time and O(1) space.
Is Best Time to Buy and Sell Stock III asked at Google/Amazon/Meta?
Best Time to Buy and Sell Stock variations frequently appear in interviews at companies like Amazon, Google, and Meta. Interviewers use this problem to test dynamic programming skills, state transitions, and understanding of transaction constraints.
What data structure is used in Best Time to Buy and Sell Stock III?
The main data structure is a simple array of stock prices. The optimal solution uses dynamic programming variables to track state transitions, while an alternative solution uses two auxiliary arrays to store prefix and suffix profits.
What is the time complexity of Best Time to Buy and Sell Stock III?
The optimal algorithms run in O(n) time where n is the number of days in the price array. Both the 4‑state dynamic programming method and the left/right profit array technique require a single linear pass (or two linear passes) through the array.